On the degree of non-regularity of context-free languages

Abstract

We investigate the influence of the six AFL operations (taken in the form union, intersection, and right concatenation with regular sets, Kleene-closure, homomorphisms, and inverse homomorphisms) on the degree of non-regularity of context-free languages, measured by the parameters m and m _λ introduced in [6] by Mäkinen and by the parameter Nreg considered in [7] by Paun. All these operations can induce arbitrary decrease of non-regularity, the intersection with regular sets and the inverse homomorphisms can induce arbitrary increase for all the three measures, whereas the homomorphisms can induce arbitrary increase for parameters m and m _λ only. Finally, the three measures are compared with each other and arbitrary large differences are shown

Keywords:

• Measures of non-regularity
• operations on languages

^∗The research of this author was partially suppoted by the Finnish Nevanlinna Foundation while he visited the University of Turku in April 1989

^†The work of this author was partially done during his stay at the Magbeburg University of Technology, September 1989

^∗The research of this author was partially suppoted by the Finnish Nevanlinna Foundation while he visited the University of Turku in April 1989

^†The work of this author was partially done during his stay at the Magbeburg University of Technology, September 1989

Notes

^∗The research of this author was partially suppoted by the Finnish Nevanlinna Foundation while he visited the University of Turku in April 1989

^†The work of this author was partially done during his stay at the Magbeburg University of Technology, September 1989