Regular-like expressions for some irregular languages
Janusz Brzozowski · 1968
In this paper we study some classes of irregular languages which can be denoted by regularlike expressions. It is shown that a set of regular expressions can be used to characterize every language which is generated by a non-expansive context-free grammar, i.e. which is a standard matching-choice set as defined by Yntema. Characterizations are given for the linear, metalinear and ultralinear languages. Some known results are presented in a simpler and more intuitive fashion by using the notion of a finite automaton with a folded tape. It is next shown that the model used can be naturally extended to a subfamily of contextsensitive languages.