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
∗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