Свойства замкнутости регулярных языков.

Рассмотрим операции для регулярных языков. Пусть есть два языка L и M, где LÍ∑* и МÍ∑*-подмн-ва одного и того же алфавита, но если LÍ∑_L и МÍ∑_М, то можно сказать что ∑=(∑_LÈ∑_М), т.е. деделаем новый алфавит, в котором эти два языка.

LÈM-объединение-мн-во всех цепочек принадлежащих L или М.

LÇM-пересечение-мн-во всех цепочек, принадлежащих и L, и М.

L-M-мн-во всех цепочек, принадлежащих L, одновременно не принадлежащих М.

Ḹ=∑*-L- дополнение

Теорема: LÈM-регулярный язык для регулярных языков L и М, т.е. L=L(R), M=L(S), где L(R) и M(S) –регулярные выражения от языков R и S, тогда LÈM=L(R+S).

Если L-регулярный язык, то Ḹ-тоже. Т.е. есть такой конечный автомат допускающий цепочки из L. Все допускающие состояния объявим, как недопускающие, а недопускающие преобразуем в допускающие.

Пересечение всех цепочек тоже является регулярным языком:

Обращение цепочки-это цепочка выписанная в обратном порядке:

w=a₁…a_n

w^R=a_n…a₁

Тогда если L-регулярный язык, то L^R-тоже. L^R={w^R|wÎL}

Гомоморфизм цепочки-ф-ция на мн-ве цепочек, которая вместо каждого символа цепочки подставляет другую цепочку, т.е. есть некоторое отображение h, которое каждому символу алфавита ставит в соответствие цепочку h:∑→∑*

w=a₁…a_n

h(w)=h(a₁)h(a₂)…h(a_n)

h(L)={V|V=h(w), wÎL}

Теорема: если L-регулярный язык, то h(L) также.

Обратный гомоморфизм также сохраняет регулярность языков, т.е. если h:∑→Т и L-регулярный язык над Т, то h(L)-регулярный язык от ∑.

Деревья разбора.

Дерево разбора для грамматики G это дерево, обладающее след. свойствами: каждая внутренняя вершина дерева помечена переменной из N. Каждый лист отличен либо переменной либо терминалом либо e(пустой строкой), причем вершина e должна быть единственным наследником у своего родителя. Если вершина А-внутренняя вершина, а его сыновья слева направо x₁,x₂,…,x_n, то значит существует продукция вида A→ x₁,x₂,…,x_n.

Листья любого дерева разбора при их просмотре слева направо образуют цепочку которая называется кроной дерева. Кроной дерева разбора яв-ся выводимая цепочка.

Равносильно след. утверждение: 1) процедура рекурсивного вывода определяет, что цепочка принадлежит языку переменной А; 2) A=>w; 3) A =>^L w; 4)A =>^R w; 5) существует дерево разбора с корнем А и кроной w.

Нормальная форма Хомского контекстно-свободных грамматик.

Покажем, что каждый КС-язык, не содержащий пустой цепочки, порождается грамматикой, все продукции которой имеют вид: А→ВС, А→а, где большие буквы-переменные, а малые-терминал.

Представление грамматики в таком виде называется нормальной формой Хомского. Для приведения грамматики к такому виду необходимо: 1) удалить бесполезные символы, т.е. все переменные и терминалы, которые не встречаются порождением терминала цепочек из стартового символа; 2) удалить продукции вида А→e, т.е. порождения пустых цепочек; 3) удалить цепные продукции вида А→В, где А и В-переменные.