On a Class of Regular-Like Expressions for Linear Languages
José M. Sempere · Universitätsbibliothek Gießen · 2000
Regular expressions define regular languages, so, there exist algorithms that can solve some important problems concerning regular languages such as finite automata synthesis or analysis by using regular expressions. In this work, we propose an extension of regular expressions to characterize a larger language class, linear languages. Linear languages form a class which is properly included in the context-free language class and which also properly includes the regular language class. From the definition proposed in this paper, an algorithm which obtains linear grammars from linear expressions (and vice versa) is formulated in a way similar to the one for regular expressions. We also review some problems concerning linear grammars such as the equivalence and the structural equivalence problem.