Нормальная форма Хомского — различия между версиями
(ё) |
м (rollbackEdits.php mass rollback) |
||
(не показано 35 промежуточных версий 9 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
{{Определение | {{Определение | ||
− | |definition=Грамматикой в '''нормальной форме Хомского''' (''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут | + | |definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида: |
− | <tex>A \rightarrow B C </tex>, | + | :<tex>A \rightarrow B C </tex>, |
− | <tex>A \rightarrow a </tex>, | + | :<tex>A \rightarrow a </tex>, |
− | <tex>S \rightarrow \varepsilon </tex>, | + | :<tex>S \rightarrow \varepsilon </tex>, |
где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил. | где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил. | ||
Строка 20: | Строка 18: | ||
# Уберём длинные правила. | # Уберём длинные правила. | ||
− | #: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины 0, 1 и 2. | + | #: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 |
+ | </tex>, эквивалентную исходной, содержащую правила длины <tex>0, 1</tex> и <tex>2</tex>. | ||
# Удаление <tex> \varepsilon </tex>-правил. | # Удаление <tex> \varepsilon </tex>-правил. | ||
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил. | #:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил. | ||
# Удаление цепных правил. | # Удаление цепных правил. | ||
− | #:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \ | + | #:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </tex>. |
# Удалим бесполезные символы. | # Удалим бесполезные символы. | ||
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться. | #:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться. | ||
# Уберём ситуации, когда в правиле встречаются несколько терминалов. | # Уберём ситуации, когда в правиле встречаются несколько терминалов. | ||
− | #:Для всех правил вида <tex> A \rightarrow u_1 u_2 | + | #:Для всех правил вида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на новые нетерминалы <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов. |
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>. | Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>. | ||
− | + | ||
+ | Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы. | ||
+ | |||
+ | При таком порядке действий размеры грамматики возрастают полиномиально. | ||
+ | |||
+ | После удалении длинных правил из каждого правила длины <tex> k \geqslant 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое. | ||
+ | |||
+ | При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины <tex>0, 1</tex> и <tex>2</tex>, размеры грамматики могли вырасти не больше, чем в <tex>3</tex> раза. | ||
+ | |||
+ | Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики возрастет не больше, чем на <tex> k \cdot n^2 </tex>. | ||
+ | |||
+ | Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины <tex>1</tex>. | ||
}} | }} | ||
− | == | + | == Пример == |
− | + | {| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;" | |
+ | !style="background:#41aef0"|Текущий шаг | ||
+ | !style="background:#41aef0"|Грамматика после применения правила | ||
+ | |- | ||
+ | |''0. Исходная грамматика'' | ||
+ | |<tex>S\rightarrow aXbX|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex><br> <tex>Z\rightarrow ZX</tex> | ||
+ | |- | ||
+ | |''1. Удаление длинных правил'' | ||
+ | |<tex>S\rightarrow aS_{1}|aZ</tex> <br> <tex>X\rightarrow aY|bY|\varepsilon</tex> <br> <tex>Y\rightarrow X|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}</tex> <br> <tex>S_{2}\rightarrow yX</tex> | ||
+ | |- | ||
+ | |''2. Удаление <tex>\varepsilon</tex>-правил'' | ||
+ | |<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{2}</tex> <br> <tex>S_{2}\rightarrow yX|y</tex> | ||
+ | |- | ||
+ | |''3. Удаление цепных правил'' | ||
+ | |<tex>S\rightarrow aS_{1}|aZ</tex><br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>Z\rightarrow ZX</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex> | ||
+ | |- | ||
+ | |''4. Удаление бесполезных символов'' | ||
+ | |<tex>S\rightarrow aS_{1}</tex> <br> <tex>X\rightarrow aY|bY</tex> <br> <tex>Y\rightarrow aY|bY|cc</tex> <br> <tex>S_{1}\rightarrow XS_{2}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex> | ||
+ | |- | ||
+ | |''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.'' | ||
+ | |<tex>S\rightarrow S_{3}S_{1}</tex><br> <tex>X\rightarrow S_{3}Y|X_{1}Y</tex> <br> <tex>Y\rightarrow S_{3}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{4}X|y</tex> <br> <tex>S_{2}\rightarrow S_{4}X|y</tex> <br> <tex>S_{3}\rightarrow a</tex> <br> <tex>S_{4}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex> <br> <tex>Y_{1}\rightarrow c</tex> | ||
+ | |} | ||
+ | <div style="clear:both;"></div> | ||
+ | |||
+ | == См. также == | ||
+ | * [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]] | ||
+ | * [[Нормальная_форма_Куроды | Нормальная форма Куроды]] | ||
+ | * [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах | Приведение грамматики к ослабленной нормальной форме Грейбах]] | ||
+ | |||
+ | ==Источники информации== | ||
+ | * [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]] | ||
+ | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528с. : ISBN 5-8459-0261-4 (рус.) | ||
+ | |||
+ | |||
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Нормальные формы КС-грамматик]] |
Текущая версия на 19:17, 4 сентября 2022
Определение: |
Грамматикой в нормальной форме Хомского (англ. Chomsky normal form) называется контекстно-свободная грамматика, в которой могут содержаться правила только следующего вида:
|
Приведение грамматики к нормальной форме Хомского
Теорема: |
Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. |
Доказательство: |
Рассмотрим контекстно-свободную грамматику . Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую , которая допускает тот же язык, что и .
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и .Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до . Третье правило идет после второго, потому что после удаления -правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы.При таком порядке действий размеры грамматики возрастают полиномиально. После удалении длинных правил из каждого правила длины могло появиться новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.При удалении -правил из грамматики, содержащей правила длины и , размеры грамматики могли вырасти не больше, чем в раза.Всего цепных правил в грамматике не больше, чем Наконец, на последнем шаге может произойти добавление не более, чем , где — число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна , то размер грамматики возрастет не больше, чем на . ( — алфавит грамматики) новых правил, причем все они будут длины . |
Пример
Текущий шаг | Грамматика после применения правила |
---|---|
0. Исходная грамматика | |
1. Удаление длинных правил | |
2. Удаление | -правил|
3. Удаление цепных правил | |
4. Удаление бесполезных символов | |
5. Уберём ситуации, когда в правиле встречаются несколько терминалов. |
См. также
Источники информации
- Wikipedia — Chomsky normal form
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528с. : ISBN 5-8459-0261-4 (рус.)