Приведение грамматики к ослабленной нормальной форме Грейбах — различия между версиями
Zernov (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 22 промежуточные версии 5 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition=Грамматикой в '''нормальной форме Грейбах''' (''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов: | + | |definition=Грамматикой в '''нормальной форме Грейбах''' (англ. ''Greibach normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов: |
− | + | :<tex> A \rightarrow a\gamma </tex> | |
− | + | ||
− | где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал, <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из не более, чем двух нетерминалов. | + | :<tex> S \rightarrow \varepsilon </tex> |
+ | где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал (возможно, стартовый), <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из не более, чем двух нетерминалов. | ||
}} | }} | ||
{{Определение | {{Определение | ||
− | |definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (''Greibach weak normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов: | + | |definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (англ. ''Greibach weak normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться только правила одного из следующих типов: |
− | + | :<tex> A \rightarrow a\gamma </tex> | |
− | + | ||
− | где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал, <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из произвольного числа терминалов и нетерминалов. | + | :<tex> S \rightarrow \varepsilon </tex> |
+ | где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал (возможно, стартовый), <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из произвольного числа терминалов и нетерминалов. | ||
}} | }} | ||
+ | |||
== Приведение грамматики к ослабленной нормальной форме Грейбах == | == Приведение грамматики к ослабленной нормальной форме Грейбах == | ||
Строка 19: | Строка 22: | ||
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и <tex> \Gamma </tex>. | Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и <tex> \Gamma </tex>. | ||
− | + | #Избавимся от <tex> \varepsilon </tex>-правил. Для этого воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. | |
− | + | #Воспользуемся [[Устранение_левой_рекурсии|алгоритмом устранения левой рекурсии]].Получим грамматику, все правила которой будут иметь следующий вид: | |
− | Для этого воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. | + | #* <tex> A_i \rightarrow a \gamma </tex>, |
− | + | #* <tex> A_i \rightarrow A_j \gamma </tex>, где <tex> A_i </tex>, <tex> A_j </tex> {{---}} нетерминалы, <tex> a </tex> {{---}} терминал, <tex> \gamma </tex> {{---}} произвольная последовательность из терминалов и нетерминалов, <tex> i < j </tex>. | |
− | + | #Воспользуемся следующей функцией для придания грамматике нужного вида: | |
− | Получим грамматику, все правила которой будут иметь следующий вид: | + | '''function''' greibah(правила <tex>A_1 \dots A_n</tex> из контекстно-свободной грамматики <tex> \Gamma </tex>): |
− | + | '''for''' i = n .. 1 | |
− | + | '''for''' j = i + 1 .. n | |
− | + | Для каждого правила вывода из <tex> A_j </tex> вида <tex> A_j \rightarrow \delta_1 | \ldots | \delta_k </tex> заменить каждое правило <tex> A_i \rightarrow A_j \gamma </tex> на <tex> A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma </tex>. | |
− | |||
− | где <tex> A_i </tex>, <tex> A_j </tex> {{---}} нетерминалы, <tex> a </tex> {{---}} терминал, <tex> \gamma </tex> {{---}} произвольная последовательность из терминалов и нетерминалов, <tex> i < j </tex>. | ||
− | |||
− | |||
− | Воспользуемся следующей | ||
− | < | ||
− | |||
− | |||
− | |||
− | |||
− | После каждой итерации главного цикла все правила для <tex> A_k </tex> (где <tex>k \ | + | После каждой итерации главного цикла все правила для <tex> A_k </tex> (где <tex>k \geqslant i</tex>) будут иметь вид <tex> A_k \rightarrow a \gamma </tex>. |
Значит, после применения процедуры все правила грамматики будут иметь вид <tex> A \rightarrow a \gamma </tex>. | Значит, после применения процедуры все правила грамматики будут иметь вид <tex> A \rightarrow a \gamma </tex>. | ||
− | |||
− | |||
Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная. | Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная. | ||
}} | }} | ||
+ | |||
+ | == Пример == | ||
+ | {| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;" | ||
+ | !style="background:#41aef0"|Текущий шаг | ||
+ | !style="background:#41aef0"|Грамматика после применения правила | ||
+ | |- | ||
+ | |''0. Исходная грамматика'' | ||
+ | |<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow b|SB</tex> <br> <tex>X\rightarrow b</tex><br> <tex>A\rightarrow a</tex> | ||
+ | |- | ||
+ | |''1. Удаление <tex>\varepsilon</tex>-правил'' | ||
+ | |<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow b|SB</tex> <br> <tex>X\rightarrow b</tex><br> <tex>A\rightarrow a</tex> | ||
+ | |- | ||
+ | |''2. Удаление стартового нетерминала из правых частей правил | ||
+ | |<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow bAB|BBB|b</tex> <br> <tex>X\rightarrow b</tex><br> <tex>A\rightarrow a</tex> | ||
+ | |- | ||
+ | |''3. Удаление левой рекурсии | ||
+ | |<tex>S\rightarrow XA|BB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow BB|BBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex> | ||
+ | |- | ||
+ | |''4. Выполняем функцию '''greibah''' для правила <tex>S\rightarrow XA|BB</tex> | ||
+ | |<tex>S\rightarrow bA|bABB|bB|bABZB|bZB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow BB|BBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex> | ||
+ | |- | ||
+ | |''5. Выполняем функцию '''greibah''' для правила <tex>Z\rightarrow BB|BBZ</tex> | ||
+ | |<tex>S\rightarrow bA|bABB|bB|bABZB|bZB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow bABB|bB|bABZB|bZB|bABBZ|bBZ|bABZBZ|bZBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex> | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
+ | |||
=== Асимптотика === | === Асимптотика === | ||
Строка 51: | Строка 68: | ||
Алгоритм состоит из трех шагов, сложность первого и последнего шага равны <tex>O(\left| \Gamma \right|)</tex> и <tex>O(\left| \Gamma \right| ^ 2)</tex> соответственно. Таким обзом, сложность алгоритма является <tex>O(\left| \Gamma \right| ^ 2) + O\left(n\sum\limits_{i=1}^n a_j\right)</tex>, где второй член {{---}} сложность алгоритма удаления левой рекурсии. | Алгоритм состоит из трех шагов, сложность первого и последнего шага равны <tex>O(\left| \Gamma \right|)</tex> и <tex>O(\left| \Gamma \right| ^ 2)</tex> соответственно. Таким обзом, сложность алгоритма является <tex>O(\left| \Gamma \right| ^ 2) + O\left(n\sum\limits_{i=1}^n a_j\right)</tex>, где второй член {{---}} сложность алгоритма удаления левой рекурсии. | ||
− | + | == Применение == | |
'''Простота доказательств''' | '''Простота доказательств''' | ||
− | Использование нормальных форм существенно упрощает доказательство теорем. Например, использование нормальной формы Грейбах позволяет доказать, что для каждого контекстно-свободного языка (не содержащего <tex>\varepsilon</tex>) существует автомат с магазинной памятью без переходов по <tex>\varepsilon</tex>. | + | Использование нормальных форм существенно упрощает доказательство теорем. Например, использование нормальной формы Грейбах позволяет доказать, что для каждого контекстно-свободного языка (не содержащего <tex>\varepsilon</tex>) существует автомат с магазинной памятью без переходов по <tex>\varepsilon</tex>. <ref>[http://www.cis.upenn.edu/~jean/old511/html/cis51108sl4b.pdf Jean Gallier {{---}} Discrete Mathematics]</ref> |
'''Разбор грамматики''' | '''Разбор грамматики''' | ||
− | Нормальная форма | + | Нормальная форма Хомского позволяет производить разбор грамматики. Например, с помощью [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритма Кока-Янгера-Касами]]. В свою очередь, нормальная форма Грейбах позволяет использовать метод рекурсивного спуска, сложность которого является линейной, несмотря на возвраты. |
+ | |||
+ | == См. также == | ||
+ | * [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]] | ||
+ | * [[Нормальная_форма_Куроды | Нормальная форма Куроды]] | ||
+ | * [[Нормальная_форма_Хомского | Нормальная форма Хомского]] | ||
+ | |||
+ | ==Примечания== | ||
+ | |||
+ | <references /> | ||
==Источники информации== | ==Источники информации== | ||
* [[wikipedia:en:Greibach normal form | Wikipedia {{---}} Greibach normal form]] | * [[wikipedia:en:Greibach normal form | Wikipedia {{---}} Greibach normal form]] | ||
+ | * [http://www.iitg.ernet.in/gkd/ma513/oct/oct18/note.pdf MA513: Formal Languages and Automata Theory] | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Нормальные формы КС-грамматик]] |
Текущая версия на 19:27, 4 сентября 2022
Определение: |
Грамматикой в нормальной форме Грейбах (англ. Greibach normal form) называется контекстно-свободная грамматика, в которой могут содержаться только правила одного из следующих типов:
|
Определение: |
Грамматикой в ослабленной нормальной форме Грейбах (англ. Greibach weak normal form) называется контекстно-свободная грамматика, в которой могут содержаться только правила одного из следующих типов:
|
Приведение грамматики к ослабленной нормальной форме Грейбах
Теорема: |
Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах. |
Доказательство: |
Рассмотрим контекстно-свободную грамматику . Для приведения её к нормальной ослабленной форме Грейбах нужно выполнить три шага. На каждом шаге мы строим новую грамматику, допускающую тот же язык, что и .
function greibah(правилаиз контекстно-свободной грамматики ): for i = n .. 1 for j = i + 1 .. n Для каждого правила вывода из вида заменить каждое правило на . После каждой итерации главного цикла все правила для Таким образом, мы получили грамматику в ослабленной нормальной форме Грейбах, которая допускает тот же язык, что и исходная. (где ) будут иметь вид . Значит, после применения процедуры все правила грамматики будут иметь вид . |
Пример
Текущий шаг | Грамматика после применения правила |
---|---|
0. Исходная грамматика | |
1. Удаление | -правил|
2. Удаление стартового нетерминала из правых частей правил | |
3. Удаление левой рекурсии | |
4. Выполняем функцию greibah для правила | |
5. Выполняем функцию greibah для правила |
Асимптотика
Алгоритм состоит из трех шагов, сложность первого и последнего шага равны
и соответственно. Таким обзом, сложность алгоритма является , где второй член — сложность алгоритма удаления левой рекурсии.Применение
Простота доказательств
Использование нормальных форм существенно упрощает доказательство теорем. Например, использование нормальной формы Грейбах позволяет доказать, что для каждого контекстно-свободного языка (не содержащего [1]
) существует автомат с магазинной памятью без переходов по .Разбор грамматики
Нормальная форма Хомского позволяет производить разбор грамматики. Например, с помощью алгоритма Кока-Янгера-Касами. В свою очередь, нормальная форма Грейбах позволяет использовать метод рекурсивного спуска, сложность которого является линейной, несмотря на возвраты.