2. Характеризация праволинейных языков

Теорема 10.2.1. Каждый автоматный язык является праволинейным.

Доказательство. Пусть автоматный язык L(M) определяется конечным автоматом М=<Q, A, D, I, F>, где QA=, и I={q₀}. Положим N=Q, S=q₀, P={pxq : <p, x, q>D}{p : 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)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, TaS, TbF, EaF, EbS, FaE, FbD}.

Диаграмма переходов конечного автомата M₃, порождающего этот же язык имеет вид:

Рис. 10.2.1. Диаграмма конечного автомата М₃

Определение 10.2.1. Праволинейная грамматика, в которой каждое правило имеет вид T, 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, xyp, xyz=w, xyⁱzL (для всех i0).

Пример 10.2.2. Пусть язык L={abⁿaⁿ: n0} задан над алфавитом A={a, b}.

Пусть p – произвольное натуральное число. Положим w=ab^pa^p_.

Если положить x=, то возможны следующие варианты:

y	Z	w	xyyz
a	b^pa^p	xyz	aab^pa^pL
ab^k(0<k<p)	b^p-ka^p	xyz	ab^kab^pa^pL
ab^p	a^p	xyz	ab^pab^pa^pL
ab^pa^k(0<kp)	a^p-k	xyz	ab^pa^k+1b^pa^pL

Как видно из приведенной таблицы, при любом натуральном p и x= слово xyyzL. С помощью аналогичных выкладок можно придти к выводу о том, что при любом натуральном p и при x=a слово xyyzL. Этот же вывод оказывается верен и при x=ab^k, x=ab^pa^k. В свою очередь, это означает, что условие теоремы 10.2.6 не выполняется, а потому язык L не является автоматным.

Лекция № 11. Контекстно-свободные языки

1 Степанов А.Н. Информатика: Учебник для вузов. 4-е изд. – СПб.: Питер, 2005. – С. 41.

1Этой теории будут посвящены следующие лекции.

1В теории нормальных алгорифмов пустое слово обозначается символом .

2  – подслово слова .

1В ряде источников, например в [], стандартным считается то положение, при котором головка «обозревает» ячейку, в которой записана первая буква слова, т.е. крайне левую ячейку.

1 Здесь и далее в соответствии с тезисами теории алгоритмов под вычислимыми функциями подразумеваются частично рекурсивные функции. Соответственно под всюду определенными вычислимыми функциями – общерекурсивные функции.

2 Эти программы могут, например, располагаться в порядке возрастания их длины.

1 Если в классе А отсутствует нигде не определенная функция, то можно взять произвольную функцию из класса А, а нигде не определенную функцию из его дополнения.

2Не тривиальным в том плане, что класс всех вычислимых функций разбивается на два непустых подкласса функций, обладающих и не обладающих этим свойством.

51