Покажем, что язык определяется праволинейной грамматикой, m и mm, когда он явдяеься регулярным множеством.

Пусть Е-конечный алфавит.

ЛЕмма)Множества  пустое, {E}, {a} для всех a принадлежащих E

ДОК-ВО

G=(N,T,P,S) N={S} T=E, P=непустое S-аксиома L(G)=пустое.

G=(N,T,P,S) N={S} T=E, p: S::=E S-аксиома L(G)={E}.

G=(N,T,P,S) N={S} T=E, p: S::=a S-аксиома L(G)={a}.

Лемма2) Если L1 и L2 праволинейные языки, то языки

L1 U L2

L1L2

L*

так же праволинейные.

 

ТЕОРЕМА) Язык является регулярным множеством тогда и только тогда, когда он праволинейный.