Математическая теория формальных языков
Теорема Парика
Замечание 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. Является ли контекстно-свободным язык
