帰納的に可算な言語の同長線形文脈自由言語による特徴付けについて

概要

論文の詳細を見る
For a linear context-free grammar G, if every non-terminating rule of G is of the form A→αBβ with |α|=|β|, it is called an even-linear grammar and the language generated by G, L (G), is called an even-linear language. In this note, we give two characterization results of recursively enumerable languages using even-linear languages and homomorphisms : i) For each recursively enumerable language L, we can find two even-linear languages L_1,L_2 and two homomorphisms h, h_1 such that L=h(h_1(L_1)∩L_2). ii) For each recursively enumerable language L, we can find an even-linear language L_E and three homomorphisms h, h_1,h_2 such that L=h(h_1(L_E)∩h_2(L_E)).
八戸工業大学の論文
1990-03-31