Contextual grammars
Solomon Marcus · 1969
xtual grammar G which generates Proposition 1. _E.er finite lanMuage is a contextual lau- Proof. Let V be a ocabulary and let be a finite lan. guage on V. It is obvious Chat the'contextual grammar where . denotes the void set of contexts, generaOes the lan- guage L 1. The same language may be generated by mews of the contextual grammar (,L tg, where is formed by the null- cont ex only. Two contextual grammars are called _eQuivalent if they gene- rate the same language. The'gramma,,s (V,LI, O ) and (V,I%., are equivalent, since they both generate the'language . The converse of Proposition i is not true. Inded, we have Propositio._nn 2. The universal language is a contextual lan- guageo Poof. Le V = [al_a2,...s. Denote by .L the univer. sal language'o .'Let us pu ' = and L- ,.[ ,.m_, ,...,,ia It is easy to see that the'gzma (, generates the universal language on V. Remarks. If we put, in the proof Of Proposition 2, .L1TV instead oZ then the rmar oes herate the universal langu