Теорема 10.2.1. Каждый автоматный язык является праволинейным.
Доказательство. Пусть автоматный язык L (M) определяется конечным автоматом М=< Q, A, D, I, F >, где QÇA=Æ, и I ={ q0 }. Положим N=Q, S=q0, P ={ p®xq: < p, x, q >Î D }È{ p®e: p Î F }. Тогда G=< N, A, P, S > – праволинейная грамматика (грамматика типа 3), порождающая язык L (M).
Теорема доказана.
Теорема 10.2.2. Каждый праволинейный язык является автоматным.
Доказательство. Без ограничения общности можно считать, что праволинейный язык L задан праволинейной грамматикой, не содержащей правил вида T®u, где uÎA+. Положим:
Q=N, I= { S }, F ={ TÎN: (T®e) ÎP }, D ={< T, u, B >: (T®uB) ÎP }.
Тогда конечный автомат М=< Q, A, D, I, F > порождает такой язык L (M), что L=L (M).
Теорема доказана.
Пример 10.2.1. Праволинейный язык
L ={ w Î{ a, b } *: ç w ç amod 2 =0, ç w ç bmod 2 =0}
порождается грамматикой G=< N, A, P, S >, где N ={ S, T, E, F }, A={ a, b }, P ={ S®aT, S®bE, S®e, T®aS, T®bF, E®aF, E®bS, F®aE, F®bD }.
Диаграмма переходов конечного автомата M3, порождающего этот же язык имеет вид:
Рис. 10.2.1. Диаграмма конечного автомата М3
|
|
Определение 10.2.1. Праволинейная грамматика, в которой каждое правило имеет вид T®e, T®a, T®aU, где T, UÎN, aÎA, называется праволинейной грамматикой в нормальной форме (автоматной грамматикой, регулярной грамматикой).
Теорема 10.2.3. Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.
Теорема 10.2.4. Классправолинейныхязыков замкнутотносительно итерации, конкатенации и объединения.
Теорема 10.2.5. Классправолинейныхязыков замкнутотносительно дополнения и пересечения.
Теорема 10.2.6. Пусть L – праволинейный язык над алфавитом А. Тогда найдется такое натуральное p >0, что для любого слова wÎL ç w ç³ p можноподобрать слова x, y, zÎA*, длякоторых справедливы соотношения :y¹e, ç xy ç£ p, xyz=w, xyizÎL (для всех i ³0).
Пример 10.2.2. Пустьязык L= { abnan: n ³0} задан над алфавитом A={a, b}.
Пусть p – произвольноенатуральное число. Положим w=abpap.
Если положить x=e, то возможны следующие варианты:
y | Z | w | xyyz |
a | bpap | xyz | aabpapÏL |
abk(0<k<p) | bp-kap | xyz | abkabpapÏL |
abp | ap | xyz | abpabpapÏL |
abpak(0<k£p) | ap-k | xyz | abpak+1bpapÏL |
Как видно из приведенной таблицы, при любом натуральном p и x=e слово xyyzÏL. С помощью а налогичных выкладок можно придти к выводу о том, что при любом натуральном p и при x=a слово xyyzÏL. Этотже вывод оказываетсяверен и при x=abk, x=abpak. В свою очередь, это означает, что условие теоремы 10.2.6 не выполняется, а потому язык L не является автоматным.