Математическая теория формальных языков



         

Теорема Парика


Замечание 9.1.7.

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

Определение 9.7.2.

Через

будем обозначать функцию из

в , определенную следующим образом: . Аналогично, каждому языку

ставится в соответствие множество , определенное следующим образом:

Пример 9.7.3.

Пусть

и L = {a1,a1a2a2,a2a2a1}. Тогда .

Определение 9.7.4.

Пусть

и . Тогда через

обозначается множество

При этом множество B называется системой предпериодов множества L(B,P). Множество P называется системой периодов множества L(B,P).

Определение 9.7.5.

Множество

называется линейным (linear), если A = L(B,P) для некоторых конечных множеств B и P.

Определение 9.7.6.

Множество

называется полулинейным (semilinear), если оно является объединением конечного числа линейных множеств.

Теорема 9.7.7 (Теорема Парика).

Если язык

является контекстно-свободным, то множество

является полулинейным.

Доказательство можно найти в [Гин, с. 207-211].

Пример 9.7.8.

Пусть . Рассмотрим язык . Можно проверить, что множество

не является полулинейным. Следовательно, язык L не является контекстно-свободным.

Теорема 9.7.9.

Если множество

является полулинейным, то существует такой автоматный язык L, что .

Доказательство. Докажем это для произвольного линейного множества A = L(B,P) (на полулинейные множества утверждение распространяется по теореме 3.1.1). Рассмотрим конечный автомат , где Q = {1,2}, I = {1}, F = {2} и

Очевидно, что .

Замечание 9.7.10.

Теорема 9.3.1 является следствием теорем 9.7.7 и 9.7.9.

Упражнение 9.7.11. Является ли контекстно-свободным язык




Содержание  Назад