Labelled Stratified Graphs can Generate Formal Languages

摘要

Various mechanisms to define and generate formal languages are known. The concept of labelled stratified graph was introduced in [9]. Since then various applications of this concept were presented. In this paper we present another application of this structure: we show that we can generate formal languages by means of labelled stratified graphs. Moreover, we give an example of regular language and an example of context sensitive language, but not a context-free language, which can be generated by labelled stratified graphs. The concepts introduced in this paper can initiate a possible research line concerning the generative power of the formal languages generated by labelled stratified graphs. Several open problems are described in the last section of this paper.