Formal languages : structure preserving maps and decidability properties
Raphael Haskell · Spiral (Imperial College London) · 1970
Structure preserving maps or morphisms as they are called, are defined on both the class of (phrase structure) grammars and the class of (two stack acceptor) automata.Properties of the class M(B) of all grammars (automata) which can be mapped by a morphism into a given grammar (automata) B, and the class LM(B), of languages generated (accepted) by members of M(B), are developed.Briefly, if G is an unambiguous phrase structure grammar, then LM(G) is closed under union and intersection.If in addition G is context free, then every language in LM(G) is generated by an unambiguous grammar in M(G), and LM(G) is closed under difference.It is thus shown that, given an unambiguous context free grammar G, and grammars Gl, G2 in M(G); then it can be effectively decided whether or not L(G1) C L(G2), L(G1) = L(G2), or L(G1) n L(G2) = 0.As a corollary, the above closure and decidability properties are established for the class of left linear, parenthesis, balanded, and functional grammars.As regards automata, if A is a deterministic automata, then every language in LM(A) is accepted by a deterministic automata in A and the class of languages LM(A) is closed under union, intersection and difference.Applications of this result to finite state automata are discussed.