Редактирование: Нормальная форма Хомского

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
Строка 18: Строка 18:
  
 
# Уберём длинные правила.
 
# Уберём длинные правила.
#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1  
+
#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины 0, 1 и 2.
</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>-правил.
Строка 30: Строка 29:
 
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
 
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
  
Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьего и второго, так как они могут порождать бесполезные символы.
+
Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально.
  
При таком порядке действий размеры грамматики возрастают полиномиально.
+
При удалении длинных правил из каждого правила длины  <tex> k \ge 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.
  
После удалении длинных правил из каждого правила длины  <tex> k \geqslant 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.
+
При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза.
 
 
При удалении <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> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики возрастет не больше, чем на <tex> k \cdot n^2 </tex>.
  
Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины <tex>1</tex>.
+
Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины 1.
 
}}
 
}}
  
 
== Пример ==
 
== Пример ==
{| border="1" class="wikitable" style="width: 500px; height: 500px; float: left;"
+
Рассмотрим грамматику для языка правильных скобочных последовательностей: <tex>S\rightarrow \varepsilon|(S)|SS</tex>.
!style="background:#41aef0"|Текущий шаг
+
# Удалим длинные правила и получим грамматику <tex>
!style="background:#41aef0"|Грамматика после применения правила
+
\begin{array}{l l}  
|-
+
    S\rightarrow \varepsilon|A)|SS\\
|''0. Исходная грамматика''
+
    A\rightarrow (S
|<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>
+
\end{array}
|-
+
</tex>.
|''1. Удаление длинных правил''
+
# Удалим &epsilon; правила - <tex>
|<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>
+
\begin{array}{l l}  
|-
+
    S\rightarrow \varepsilon|S'\\
|''2. Удаление <tex>\varepsilon</tex>-правил''
+
    S'\rightarrow A)|S'S'\\
|<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>
+
    A\rightarrow (S'|(
|-
+
\end{array}
|''3. Удаление цепных правил''
+
</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}|yX|y</tex> <br> <tex>S_{2}\rightarrow yX|y</tex>  
+
# Удалим цепные правила - <tex>
|-
+
\begin{array}{l l}  
|''4. Удаление бесполезных символов''
+
    S\rightarrow \varepsilon|A)|S'S'\\
|<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>
+
    S'\rightarrow A)|S'S'\\
|-
+
    A\rightarrow (S'|(
|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''
+
\end{array}
|<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>
+
</tex>.
|}
+
# Заменим терминалы на нетерминалы - <tex>
<div style="clear:both;"></div>
+
\begin{array}{l l}  
 +
    S\rightarrow \varepsilon|AB|S'S'\\
 +
    S'\rightarrow AB|S'S'\\
 +
    A\rightarrow CS'|(\\
 +
    C\rightarrow (\\
 +
    B\rightarrow )
 +
\end{array}
 +
</tex>.
  
 
== См. также  ==
 
== См. также  ==
 
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
 
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Куроды | Нормальная форма Куроды]]
+
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
* [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах | Приведение грамматики к ослабленной нормальной форме Грейбах]]
 
 
 
==Источники информации==
 
* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528с. : ISBN 5-8459-0261-4 (рус.)
 
  
 +
==Литература==
 +
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: