ТМВ-2020-Лекция-18.02.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Формальные грамматики. Автоматные грамматики. Контекстно-свободные грамматики. Алгоритм Кока – Янгера – Касами

Формальные грамматики

Грамматика - способ описания формального языка. Грамматики основываются на операциях над подстроками.

Формально грамматика - четвёрка \((N,T,S,P)\):

\(N\) - вспомагательные (нетерминальные) символы

\(T\) - основные (терминальные) символы

\(S \in N\) - аксиома

\(P\) - правила вывода

\(\Sigma = N \cup T\)

\(P: \Sigma^+ \to \Sigma^*\)

Пример 1:

Опишем грамматику, порождающую нерегулярный язык вида \(a^nb^n\)

\(S \to \lambda\) (строка длины n)

\(S \to aSb\)

\(S \to aSb \to aaSbb \to aaaSbbb \to aaabbb\)

С помощью грамматик можно описать нерегулярные языки, соответственно, можно считать, что грамматики намного мощнее автоматов.

Пример 2:

Пусть язык задан регулярным выражением вида \(aabc*ab\) (напоминаем, что * означает наличие 0 или более предыдущего символа).

\(S \to aabAab\)

\(A \to cA\)

\(A \to \lambda\)

В целом, грамматики специального вида эквивалентны конечным автоматам.

Пример 3 (правильная скобочная последовательность):

Существует множество способов описания формальной грамматики (приведем в примере 2 грамматики, они эквивалентны):

1) \(S \to (S)S\)

\(S \to \lambda\)

2) \(S \to SS\)

\(S \to \lambda\)

\(S \to (S)\)

Любую скобочную скобочную последовательность можно разделить на более мелкую скобочную последовательность. Далее опускаемся на уровень ниже и повторяем данные выше утверждения до точки остановы.

Пример 4 (арифметические выражения):

Ограничимся наличием целых чисел, операций +- и скобок:

\(S \to N\)

\(N \to N'_0\)

\(N \to N'_9\)

\(N' \to +\)

\(N' \to -\)

\(N' \to N'_0\)

\(N' \to N'_9\)

\(N' \to \lambda\)

\(S \to S + S\)

\(S \to S - S\)

\(S \to (S)\)

Автоматные грамматики

Терминал - состояние автомата.

Нетерминал - состояние автомата.

Ребро - правило

Грамматика порождает язык, состоящий из всех строчек, содержащих только нетерминальные символы, выводимые из аксиом.

Лево-контекстная грамматика

\(A \to aB\) (разрешено приписывать слева ровно один символ)

\(B \to a\)

\(B \to \lambda\)

\(где A,B \in N, a \in T\)

Пример 1 (лево-контекстная грамматика)

aabc*ab

\(S \to aA\)

\(A \to bC\)

\(C \to cC\)

\(C \to aD\)

\(D \to b\)

Право-контекстная грамматика

\(A \to Ba\) (разрешено приписывать справа ровно один символ)

\(B \to a\)

\(B \to \lambda\)

\(где A,B \in N, a \in T\)

Пример 2 (право-контекстная грамматика)

aabc*ab

\(S \to Ab\)

\(A \to Ba\)

\(B \to Cb\)

\(C \to Da\)

\(D \to a\)

Утверждение об эквивалентности

Утверждение Лево-контекстные грамматики эквивалентны конечным автоматам.

Доказательство:

Строим конечный автомат по лево-контекстной грамматике.

Состояние автомата \(Q = N \cup {\sigma}\)

\(T = {A \in N: (A \to a \in P, a \in T)} \)

Алфавит: \(\Sigma = T\)

Начальное состояние: \(S=S\)

Правила перехода:

\(\delta(A,a) = B ↔ (A \to aB) \in P\)

\(\delta(A,a) = \sigma ↔ (A \to a) \in P\)

Множество, которое выразимо через данную грамматику шире, чем множество регулярных языков. \(∎\)

Контекстно-свободные грамматики

Контекстно-свободные грамматики - грамматики, в которых правила имеют вид: \(P:N \to \Sigma^*\) (В ЛЧ только один нетерминал)

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

Нормальная форма Хомского – свойство формальной грамматики, описывающееся правилами:

\(A \to BC\)

\(A \to a\)

\(S \to \lambda\)

где \(B,C \notin S\), \(a \in T\), \(A \in N\) ,\(S\) - аксиома

Алгоритм приведения в нормальную форму

1) Удаляем длинные правила (длина \(k\), вводим \(k-1\) нетерминалы)

\(A \to \alpha_1, \cdots, \alpha_k; \alpha_i \in \Sigma\)

\(A \to \alpha_1A_1\)

\(A_1 \to \alpha_2A_2\)

\( \cdots \)

\(A_{k-1} \to \alpha_{k-1}\alpha_k\)

2) Устранение (удаление) \(\lambda\) - правила

- Найдем все правила вида \(A \to \lambda, A \neq S\). пометим их

- Затем найдем все правила вида \(A \to BC, где B \to \lambda, c \to \lambda\). Далее по рекурсии повторим это.

В итоге получаем набор нетерминалов, из которого выводится \(\lambda\).

- Если есть правило \(A \to BC\), где из \(C\) выводится \(\lambda\), то добавим правила \(A \to B\).

- Удалим все правила, в правых частях которых стоит \(\lambda\)

3) Цепные правила вида \(A \to B\)

Если \(A \to B\), а \(B \to \alpha_1 \cdots \alpha_k\), то добавим правило \(A \to alpha_1, \cdots, \alpha_k\), а правило \(A \to B\) удалим.

4) Удаление бесполезных правил

- Если \(A \to a\), то \(A\) - полезный нетерминал.

- Если \(A \to BC\) и \(B\) и \(C\) - полезные, то и \(A\) - полезный. //Пример с бесполезным правилом \(S \to a, B \to C\), 2 правило бесполезное

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

5) Удаление цепочки терминалов

\(A \to ab\), то

\(A \to Bb\)

\(B \to a\)

// \(A \to Ba\), тогда \(A \to BC, C \to a\)

Конец алгоритма

Эквивалентность КСГ и КСГ в нормальной форме

Утверждение Контекстно-свободные грамматики и контекстно-свободные грамматики в нормальной форме эквивалентны.

Алгоритм Кока - Янгера - Касами (КЯК)

Алгоритм Кока - Янгера - Касами - алгоритм динамического программирования, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.

Есть ли функция для нетерминала \(A\):

$$ f(A,i,j) = \begin{cases} 1, & \mbox{если } A^* \to a_i, \cdots, a_j \\ 0, & \mbox{иначе } \end{cases} $$

$$ f(A,i,j) = \begin{cases} 1, & \mbox{если } A^* \to a_i, \\ 0, & \mbox{иначе } \end{cases}$$

Правило пересчёта:

\(f(A,i,j)=\sum_{i \le k \le j} \sum_{B,C \in N} f(B,i,k)f(C,k+1,j)\)

\(|N|n^2n|N|^2 = |N|^3n^3\) - оценка сложности (полиноминальная)