Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Терминальные символы, нетерминальные символы, правила (левая часть (одллжна содерждать один нетерминал), правая часть (может быть пустой)), выделенный нетерминал (аксиома), отношение выводимости. Если в конце получили терпинальную (или пустую строчку), то мы её породили. Множество порожлаемых строк — язык.

Классификация грамматик

Введена Хомским. Называется иерархией по Хомскому.

0. Выделяют нулевой уровень (грамматики типа ноль) — грамматики без ограничений на вывод, грамматики общего вида.

1. Дальше определяются неукорачивающие грамматики:

• α → β |α| ≤ |β|
• Отдельно допускается правило S → ε, но при этом S не должна входить ни в одну правую часть

Это неукорачивающие, или контекстно-зависимые грамматики.

2. Грамматики контекстно свободные. Все правила имеют такой вид:

• A → α, α ∈ (N ∪ T)*

Кроме того, в правой части разрешается иметь ε, и формально КС-грамматики не являются укорачивающими. Но позднее будет доказываться теорема, что любая КС-грамматика порождается грамматикой первого типа.

3. A → wB, w ∈ T*. Если w = ε, то такое правило называется цепным. Или правила могут иметь такой вид: A → w. Это праволинейные грамматики. Или грамматики типа 3 по Хомскому.

'Определение. В соответствии с тем, как поделили грамматики, можно поделить языки. Если для некоего языка существует грамматика соотв уровня, то и язык такого уровня. Ясно, что если язык является праволинейным, то он же является КС. Язык является уровнем i, если существует грамматика уровня i и не существует грамматики уровня (i + 1).

Если мы обозначим Z₀ ≥ Z₁ ≥ Z₂ ≥ Z₃. То, что такой порядок, очевидно исходя из определений. На самом деле, вложение строгое.

Теорема. Каждый КС-язык может быть порождён неукорачивающей грамматикой.
Доказательство. У нас есть КС-грамматика.

1. Предположим, что мы умеем определять нетерминалы, из которых выводится ε.
2. Тогда сделаем следующую вещь: рассмотрим все правила грамматики A → α, и альфу запишем след образом: выделим в α все нетерминалы, из которых выводится ε: α = α1B1α2B2 ... Bkα(k+1). И заменим такое правило группой правил на правила, где B мигает: α1α2B2 ... Bkα(k+1), α₁B₁α₂α₃ ... B_kα_(k+1). Таких правил будет 2^k.
3. Второе преобразование: удалим все правила A → ε.
4. Четвёртое: Если из S выводится ε, то добавляем S': S' → ε, S' → S. Тогда мы все укорачивающие правила удалили, поэтому она КС. S' делаем аксиомой.

5.Остаётся доказать, что эта грамматика порождает тот же язык. Есть у нас какой-то вывод. На каком-то этапе B обращается в ε. тогда мы это правило заменяем на правило, где этого B нет. И можем найти в новой грамматике то правило, которое соотв тому, что B вывелось в ε

Определение. Две грамматики называются эквивалентными, если они порождают один и тот же язык.

Как определить множество:

• N0 = {Ai}, Ai → ε
• Ni = N(i−1) объединение {Ai &alpha, α = Ni&minus1*}

Основным механизмом распознавания для нас будет машина Тьюринга (МТ).

Механизм синт анализа – Машина тьюринга, применённая к КС-грамматике. Конеч автомат – МТ, применённая к гр 3-го типа.

Определение: МТ: T_m = (Q (конеч множ-во состояний), Г(конеч множество ленточных символов), Σ (входной алфавит), D (функция перехода), q0, F (множество конеч состояний)) D: (Q/F) × Г → Q × Г × {l, R} q0 ∈ Q; F ∈= Q

Есть лента, бесконечная с одной стороны, разбитая на ячейки. На ленте начало занято, а дальше в каждой ячейке символ B (Blank). Для машины времени принципиально важно, что цисло занятых ячеек конечно. Второй важный комментарий — можно определить ленту двустороннюю. Но, так как мы требуем, что число занятых ячеек конечно, то мы можем сделать преобразование ленты.

Занумеруем все ячейки, начиная с единицы.

Что делает МТ: у неё в начале работы на ленту помещается вход w = a1 ... an, w &in Σ*. Есть понятие головки — указатель, смотрит на одну из занятых ячеек ленты, есть состояние, с котором машина находится. В начале она находится в q0. Тройку (q, w, i) будем называть конфигурации машины Тьюринга. Такая конфигурация (q0, w, 1) называется начальной. Далее МТ смотрит, определена ли на данной комбинации функция перехода. На основании текущего состояния и символа она может принимать новое состояние, пишет символ и двигается вправо/вдево.

Отношение на множестве конфигураций, и будем говорить, что МТ начинает работать на начальной окнфигурации, попали в конфигурации (q, y, i), и каждая конфигурации получается путём предыдущей путём применения функция перехода. Дальше говорят, что если q ∈ F, то есть мы попали в закл состояние, то говорят, что w принадлежит языку, опред машиной Тьюринга L(Tm) = {w | (q0, w, 1) ⇒* (q, y, i)}. Тем самым, мы определяем язык, допускаемый (распознаваемый) МТ.

Любой вычислительный процесс может быть сформулирован в терминах МТ.

Такая МТ называется детерминированной, так как переход только один. Если функция перехода оперделена как D: (Q/F) × Г → 2^{Q × Г × {l, R}}, то это недетрминированная МТ.

Существует теорема, которая утверждает, что нельзя по произв МТ и цепочке нельзя сказать, остановится она или нет.

Недетрм работает следующим образом: в некоторых из своих конфигнураций может перейти в разные конфигурации. То есть область значений это функции является множеством. В результате получается дерево возм конфигураций. Если есть хотя бы один путь, который ведёт от начальной цепочки к заключительной, то определение допускается.

Универсальная МТ — МТ, которая эмулирует любую МТ. У неё на ленте записывается входная информация и описание МТ.

Теорема. Класс языков, допускаемых МТ, эквивалентен классу языков, порождаемых грамматиками класса 0. Доказательство. Пусть дана грамматика типа 0: L(L), L = (N, T, P, S). Возьмём такую МТ: Tm = (Q, T, N объединение T объединение {B, #, x}, q0, F)

Устроена машина просто. Подали ей на вход w. Она пищет на вход аксиому и заключает её в маркеры: w

S

Далее она просматривает w и справа пишет текущее слово w

γ

МТ обязательно должна быть недетерм, иначе не все определения она сможет отсечь. Детерм МТ для недерм существует, но она работает за экспоненту времени.

Если цепочка принадлежит языку, то мы рано или поздно закончим, а если не принадлежит, то она может не остановиться.

Обратно (придётся повозиться): Пусть дана МТ Tm = (Q, Σ, Г, D, q0, F) L = (N, Σ, P, A1), N = ([Σ объединение {ε}] × Г) объединение Q объединение {A1, A2, A3}.