Приведение грамматики к ослабленной нормальной форме Грейбах

Материал из Викиконспекты
Версия от 09:23, 2 ноября 2011; Vincent (обсуждение | вклад) (Приведение грамматики к ослабленной нормальной форме Грейбах)
Перейти к: навигация, поиск

Определение

Определение:
Грамматикой в ослабленной нормальной форме Грейбах (Greibach weaked normal form) называется контекстно-свободная грамматика, в которой могут содержатся правила только следующего вида:

[math] A \rightarrow a\gamma [/math],

[math] S \rightarrow \varepsilon [/math],

где [math] a [/math] — терминал, [math] A [/math] — нетерминал, [math] S [/math] — стартовая вершина, [math] \varepsilon [/math] — пустая строка, [math] \gamma [/math] — строка из произвольного количества терминалов и нетерминалов, стартовая вершина не содержится в правых частях правил.


Приведение грамматики к ослабленной нормальной форме Грейбах

Теорема:
Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.
Доказательство:
[math]\triangleright[/math]

Рассмотрим контекстно-свободную грамматику [math] \Gamma [/math]. Для приведения ее к нормальной ослабленной форме Грейбах нужно выполнить несколько шагов. На каждом шаге мы строим новую [math] \Gamma_i [/math], которая допускает тот же язык, что и [math] \Gamma [/math].

  1. Избавимся от [math] \varepsilon [/math]-правил.
    Для этого воспользуемся алгоритмом удаления ε-правил. Получим грамматику [math] \Gamma_1 [/math].
  2. Воспользуемся алгоритмом устранения левой рекурсии.
    Получим грамматику [math] \Gamma_2 [/math], все правила которой будут иметь следующий вид:
    • [math] A_i \rightarrow a \gamma [/math],
    • [math] A_i \rightarrow A_j \gamma [/math],
    где [math] A_i [/math], [math] A_j [/math] — нетерминалы, [math] a [/math] — терминал, [math] \gamma [/math] — произвольная последовательность из терминалов и нетерминалов, [math] i \lt j [/math].
  3. Воспользуемся следующей процедурой для придания грамматике нужного вида.
    for i = n downto 1
    for j = i + 1 to n
    Для каждого правила вывода из [math] A_j \rightarrow \delta_1 | \ldots | \delta_k [/math] заменить каждое правило [math] A_i \rightarrow A_j \gamma [/math] на [math] A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma [/math].
    Получим грамматику [math] \Gamma_3 [/math].
    После каждой итерации главного цикла все правила для [math] A_k, \, k \ge i [/math] будут иметь вид [math] A_k \rightarrow a \alpha [/math].
    Значит, после применения процедуры все правила грамматики будут иметь вид [math] A \rightarrow a \alpha [/math].
  4. Если [math] \varepsilon [/math] присутствовал в языке старой грамматики, то добавим новый стартовый символ [math] S' [/math] и правила [math] S' \rightarrow S | \varepsilon [/math] в [math] \Gamma_3 [/math].
Таким образом мы получили грамматику [math] \Gamma_3 [/math] в ослабленной нормальной форме Грейбах, которая допускает то же язык, что и [math] \Gamma [/math].
[math]\triangleleft[/math]