Иерархия Хомского формальных грамматик — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 35 промежуточных версий 9 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Иерархия Хомского''' классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
+
'''Иерархия Хомского''' (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
 
}}
 
}}
 
== Класс 0 ==
 
== Класс 0 ==
К нулевому классу относятся все формальные грамматики. Элементы этого класса называются '''неограниченные грамматики''', поскольку не накладывается никаких ограничений. Практического применения в силу своей сложности такие грамматики не имеют.
+
К нулевому классу относятся все [[Формальные_грамматики|формальные грамматики]]. Элементы этого класса называются '''неограниченными грамматиками''' (англ. ''unrestricted grammars''), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны [[Машина_Тьюринга|машиной Тьюринга]]. Эти языки также известны как '''[[Перечислимые_языки|рекурсивно перечислимые]]''' (англ. ''recursively enumerable'').
 +
 
 +
Правила можно записать в виде:
 +
 
 +
<tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha</tex> — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а <tex>\beta</tex> — любая цепочка символов из алфавита.
 +
 
 +
Практического применения в силу своей сложности такие грамматики не имеют.
 +
 
 +
===Пример===
 +
Продукции:
 +
 
 +
<tex>
 +
S \rightarrow aBcc \\
 +
B \rightarrow A \\
 +
BAA \rightarrow d \\
 +
Ac \rightarrow B \\
 +
A \rightarrow AAA\ |\ dB \\
 +
</tex>
 +
 
 +
Выведем в данной грамматике строку <tex>addd</tex>:
 +
 
 +
<tex>\boldsymbol{S} \Rightarrow a\boldsymbol{B}cc \Rightarrow a\boldsymbol{Ac}c \Rightarrow a\boldsymbol{B}c \Rightarrow a\boldsymbol{Ac} \Rightarrow a\boldsymbol{B} \Rightarrow a\boldsymbol{A} \Rightarrow ad\boldsymbol{B} \Rightarrow ad\boldsymbol{A} \Rightarrow ad\boldsymbol{A}AA \Rightarrow add\boldsymbol{BAA} \Rightarrow addd</tex>
  
 
== Класс 1 ==
 
== Класс 1 ==
 
Первый класс представлен '''неукорачивающими''' и '''контекстно-зависимыми''' грамматиками.
 
Первый класс представлен '''неукорачивающими''' и '''контекстно-зависимыми''' грамматиками.
 
{{Определение
 
{{Определение
 +
|id = Неукорачивающие грамматики
 
|definition =
 
|definition =
'''Неукорачивающие грамматики''' это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha|\leq|\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).}}
+
'''Неукорачивающая грамматика''' (англ. ''noncontracting grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha| \leqslant |\beta|</tex> (возможно правило <tex>S  \rightarrow \varepsilon</tex>, но тогда <tex>S</tex> не встречается в правых частях правил).
 
+
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Контекстно-зависимые грамматики''' это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha A \beta\rightarrow\alpha\gamma\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{*}</tex>, <tex>A \in N</tex> и <tex>\gamma \in \{\Sigma\cup N\}^{+}</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).}}
+
'''Контекстно-зависимая грамматика''' (англ. ''context-sensitive grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>\alpha A \beta\rightarrow\alpha\gamma\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{*}</tex>, <tex>A \in N</tex> и <tex>\gamma \in \{\Sigma\cup N\}^{+}</tex> (возможно правило <tex>S  \rightarrow \varepsilon</tex>, но тогда <tex>S</tex> не встречается в правых частях правил).
 +
}}
 +
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
 +
 
 +
[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Известно]], что неукорачивающие грамматики эквивалентны контекстно-зависимым.
 +
 
 +
===Пример===
 +
<tex>L=\{w \in \Sigma^* \mid w = 0^n1^n2^n, n \geqslant 1\}</tex>
 +
 
 +
Продукции:
  
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]] неукорачивающие грамматики эквивалентны контекстно-зависимым.
+
<tex>
 +
S \rightarrow 012 \\
 +
S \rightarrow 0AS2 \\
 +
A0 \rightarrow 0A \\
 +
A1 \rightarrow 11
 +
</tex>
  
 
== Класс 2 ==
 
== Класс 2 ==
Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]].
+
Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]], которые задают контекстно-свободные языки. Эти языки распознаются с помощью [[Автоматы_с_магазинной_памятью|автоматов с магазинной памятью]].
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Контекстно-свободные грамматики''' это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>A \rightarrow\beta</tex>, где <tex>A\in N </tex>, <tex>\beta \in \{\Sigma \cup N\}^{+}</tex>.}}
+
'''Контекстно-свободная грамматика''' (англ. ''context-free grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>A \rightarrow\beta</tex>, где <tex>A\in N </tex>, <tex>\beta \in \{\Sigma \cup N\}^{+}</tex>.
 +
}}
 +
То есть грамматика допускает появление в левой части правила только одного нетерминального символа.
 +
 
 +
===Пример===
 +
<tex>L=\{w \in \Sigma^* \mid w = w^R\}</tex> (язык палиндромов).
 +
 
 +
Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>
  
 
== Класс 3 ==
 
== Класс 3 ==
Элементами третьего класса являются '''праволинейные (автоматные)''' грамматики.
+
К третьему типу относятся '''автоматные''' или '''регулярные грамматики''' (англ. ''regular grammars'') {{---}} самые простые из формальных грамматик, которые задают [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярные языки]]. Они являются контекстно-свободными, но с ограниченными возможностями.
 +
 
 +
Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Праволинейные (автоматные) грамматики''' это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>A \rightarrow tB</tex> либо <tex>A \rightarrow t</tex>, где <tex>A\in N</tex>,<tex>B\in N</tex>, <tex>t\in \Sigma </tex>.}}
+
'''Леволинейная грамматика''' (англ. ''left-regular grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>A \rightarrow B\gamma</tex> или <tex>A \rightarrow \gamma</tex>, где <tex>\gamma \in \Sigma, A, B \in N</tex>.
 +
}}
 +
{{Определение
 +
|definition =
 +
'''Праволинейная грамматика''' (англ. ''right-regular grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>A \rightarrow \gamma B</tex>; или <tex>A \rightarrow \gamma</tex>, где <tex>\gamma \in \Sigma, A, B \in N</tex>.
 +
}}
 +
Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык уже не обязан быть регулярным.
 +
 
 +
Также можно [[Правоконтекстные_грамматики,_эквивалентность_автоматам|показать]], что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]].
 +
 
 +
===Пример===
 +
<tex>L</tex> для регулярного выражения <tex>a^*bc^*</tex>.
 +
 
 +
Продукции:
 +
 
 +
<tex>
 +
S \rightarrow aS\ |\ bA \\
 +
A \rightarrow \varepsilon\ |\ cA
 +
</tex>
 +
 
 +
== См. также ==
 +
* [[Правоконтекстные грамматики, эквивалентность автоматам]]
 +
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
  
== Распознавание ==
+
==Источники информации==
Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица обощает классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.
+
* ''А. Ахо, Дж. Ульман.'' Теория синтаксического анализа, перевода и компиляции. Синтаксический анализ. Том 2. Пер. с англ. — М.: Книга по Требованию, 2012. — ISBN 978-5-458-27407-4
{| class="wikitable"
+
* [[wikipedia:Chomsky_hierarchy|Wikipedia {{---}} Chomsky hierarchy]]
|-
+
* [[wikipedia:ru:Иерархия_Хомского|Википедия {{---}} Иерархия Хомского]]
! Грамматика
 
! Языки
 
! Машина
 
|-
 
| Класс 0
 
| [[ Перечислимые языки | рекурсивно перечислимые ]]
 
| [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 машина Тьюринга]
 
|-
 
| Класс 1
 
| контектно-зависимые
 
| [http://en.wikipedia.org/wiki/Linear_bounded_automaton ЛПА]
 
|-
 
| Класс 2
 
| контекстно-свободные
 
| [[Автоматы с магазинной памятью|автоматы с магазинной памятью]]
 
|-
 
| Класс 3
 
| [[Регулярные языки: два определения и их эквивалентность|регулярные]]
 
| [[Детерминированные конечные автоматы|конечные автоматы]]
 
|}
 
  
== Источники ==
+
[[Категория: Теория формальных языков]]
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. - Т. 1,2.
+
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Базовые понятия о грамматиках]]

Текущая версия на 19:18, 4 сентября 2022

Определение:
Иерархия Хомского (англ. Chomsky hierarchy) — классификация формальных грамматик и задаваемых ими языков, согласно которой они делятся на 4 класса по их условной сложности.

Класс 0

К нулевому классу относятся все формальные грамматики. Элементы этого класса называются неограниченными грамматиками (англ. unrestricted grammars), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны машиной Тьюринга. Эти языки также известны как рекурсивно перечислимые (англ. recursively enumerable).

Правила можно записать в виде:

[math]\alpha \rightarrow \beta[/math], где [math]\alpha[/math] — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а [math]\beta[/math] — любая цепочка символов из алфавита.

Практического применения в силу своей сложности такие грамматики не имеют.

Пример

Продукции:

[math] S \rightarrow aBcc \\ B \rightarrow A \\ BAA \rightarrow d \\ Ac \rightarrow B \\ A \rightarrow AAA\ |\ dB \\ [/math]

Выведем в данной грамматике строку [math]addd[/math]:

[math]\boldsymbol{S} \Rightarrow a\boldsymbol{B}cc \Rightarrow a\boldsymbol{Ac}c \Rightarrow a\boldsymbol{B}c \Rightarrow a\boldsymbol{Ac} \Rightarrow a\boldsymbol{B} \Rightarrow a\boldsymbol{A} \Rightarrow ad\boldsymbol{B} \Rightarrow ad\boldsymbol{A} \Rightarrow ad\boldsymbol{A}AA \Rightarrow add\boldsymbol{BAA} \Rightarrow addd[/math]

Класс 1

Первый класс представлен неукорачивающими и контекстно-зависимыми грамматиками.

Определение:
Неукорачивающая грамматика (англ. noncontracting grammar) — это формальная грамматика, всякое правило из [math]P[/math] которой имеет вид [math]\alpha\rightarrow\beta[/math], где [math]\alpha , \beta \in \{\Sigma\cup N\}^{+}[/math] и [math]|\alpha| \leqslant |\beta|[/math] (возможно правило [math]S \rightarrow \varepsilon[/math], но тогда [math]S[/math] не встречается в правых частях правил).


Определение:
Контекстно-зависимая грамматика (англ. context-sensitive grammar) — это формальная грамматика, всякое правило из [math]P[/math] которой имеет вид [math]\alpha A \beta\rightarrow\alpha\gamma\beta[/math], где [math]\alpha , \beta \in \{\Sigma\cup N\}^{*}[/math], [math]A \in N[/math] и [math]\gamma \in \{\Sigma\cup N\}^{+}[/math] (возможно правило [math]S \rightarrow \varepsilon[/math], но тогда [math]S[/math] не встречается в правых частях правил).

Языки, заданные этими грамматиками, распознаются с помощью линейно ограниченного автомата (англ. linear bounded automaton) (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)

Известно, что неукорачивающие грамматики эквивалентны контекстно-зависимым.

Пример

[math]L=\{w \in \Sigma^* \mid w = 0^n1^n2^n, n \geqslant 1\}[/math]

Продукции:

[math] S \rightarrow 012 \\ S \rightarrow 0AS2 \\ A0 \rightarrow 0A \\ A1 \rightarrow 11 [/math]

Класс 2

Второй класс составляют контекстно-свободные грамматики, которые задают контекстно-свободные языки. Эти языки распознаются с помощью автоматов с магазинной памятью.

Определение:
Контекстно-свободная грамматика (англ. context-free grammar) — это формальная грамматика, всякое правило из [math]P[/math] которой имеет вид [math]A \rightarrow\beta[/math], где [math]A\in N [/math], [math]\beta \in \{\Sigma \cup N\}^{+}[/math].

То есть грамматика допускает появление в левой части правила только одного нетерминального символа.

Пример

[math]L=\{w \in \Sigma^* \mid w = w^R\}[/math] (язык палиндромов).

Продукции: [math]S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma[/math]

Класс 3

К третьему типу относятся автоматные или регулярные грамматики (англ. regular grammars) — самые простые из формальных грамматик, которые задают регулярные языки. Они являются контекстно-свободными, но с ограниченными возможностями.

Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:

Определение:
Леволинейная грамматика (англ. left-regular grammar) — это формальная грамматика, всякое правило из [math]P[/math] которой имеет вид [math]A \rightarrow B\gamma[/math] или [math]A \rightarrow \gamma[/math], где [math]\gamma \in \Sigma, A, B \in N[/math].


Определение:
Праволинейная грамматика (англ. right-regular grammar) — это формальная грамматика, всякое правило из [math]P[/math] которой имеет вид [math]A \rightarrow \gamma B[/math]; или [math]A \rightarrow \gamma[/math], где [math]\gamma \in \Sigma, A, B \in N[/math].

Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык уже не обязан быть регулярным.

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

Пример

[math]L[/math] для регулярного выражения [math]a^*bc^*[/math].

Продукции:

[math] S \rightarrow aS\ |\ bA \\ A \rightarrow \varepsilon\ |\ cA [/math]

См. также

Источники информации