Викиконспекты - Вклад участника [ru]

Иерархия Хомского формальных грамматик

2014-11-17T08:53:59Z

178.66.35.197:

{{Определение
|definition=
'''Иерархия Хомского''' (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
}}
== Класс 0 ==
К нулевому классу относятся все [[Формальные_грамматики|формальные грамматики]]. Элементы этого класса называются '''неограниченными грамматиками''' (англ. ''unrestricted grammars''), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны [[Машина_Тьюринга|машиной Тьюринга]]. Эти языки также известны как '''[[Перечислимые_языки|рекурсивно перечислимые]]''' (англ. ''recursively enumerable'').

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

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

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

===Пример===
Терминалы: <tex>\Sigma = \{a, c, d\}</tex>

Нетерминалы: <tex>N = \{S, A, B\}</tex>

Продукции:

<tex>
S \rightarrow aBc \\
aB \rightarrow cA \\
Ac \rightarrow d
</tex>

== Класс 1 ==
Первый класс представлен '''неукорачивающими''' и '''контекстно-зависимыми''' грамматиками.
{{Определение
|id = Неукорачивающие грамматики
|definition =
'''Неукорачивающая грамматика''' (англ. ''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 =
'''Контекстно-зависимая грамматика''' (англ. ''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^* | w = 0^n1^n2^n, n \geqslant 1\}</tex>

Терминалы: <tex>\Sigma = \{0, 1, 2\}</tex>

Нетерминалы: <tex>N = \{S, A\}</tex>

Продукции:

<tex>
S \rightarrow 012 \\
S \rightarrow 0AS2 \\
A0 \rightarrow 0A \\
A1 \rightarrow 11
</tex>

== Класс 2 ==
Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]], которые задают контекстно-свободные языки. Эти языки распознаются с помощью [[Автоматы_с_магазинной_памятью|автоматов с магазинной памятью]].
{{Определение
|definition =
'''Контекстно-свободная грамматика''' (англ. ''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^* | w = w^R\}</tex> (язык палиндромов).

Терминалы: буквы алфавита <tex>\Sigma</tex>

Нетерминалы: <tex>N = \{S\}</tex>

Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>;

== Класс 3 ==
К третьему типу относятся '''автоматные''' или '''регулярные грамматики''' (англ. ''regular grammars'') {{---}} самые простые из формальных грамматик, которые задают [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярные языки]]. Они являются контекстно-свободными, но с ограниченными возможностями.

Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:
{{Определение
|definition =
'''Леволинейная грамматика''' (англ. ''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>\Sigma = \{a, b, c\}</tex>

Нетерминалы: <tex>\{S, A\}</tex>

Продукции:

<tex>
S \rightarrow aS\ |\ bA \\
A \rightarrow \varepsilon\ |\ cA
</tex>

== См. также ==
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языки]]
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]

==Источники информации==
* ''А. Ахо, Дж. Ульман.'' Теория синтаксического анализа, перевода и компиляции. Синтаксический анализ. Том 2. Пер. с англ. — М.: Книга по Требованию, 2012. — ISBN 978-5-458-27407-4
* [[wikipedia:Chomsky_hierarchy|Wikipedia {{---}} Chomsky hierarchy]]
* [[wikipedia:ru:Иерархия_Хомского|Википедия {{---}} Иерархия Хомского]]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Иерархия Хомского формальных грамматик

2014-11-16T22:09:24Z

178.66.35.197:

{{Определение
|definition=
'''Иерархия Хомского''' (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
}}
== Класс 0 ==
К нулевому классу относятся все [[Формальные_грамматики|формальные грамматики]]. Элементы этого класса называются '''неограниченными грамматиками''' (англ. ''unrestricted grammars''), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны [[Машина_Тьюринга|машиной Тьюринга]]. Эти языки также известны как '''[[Перечислимые_языки|рекурсивно перечислимые]]''' (англ. ''recursively enumerable'').

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

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

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

===Пример===
Терминалы: <tex>\Sigma = \{a, c, d\}</tex>

Нетерминалы: <tex>N = \{S, A, B\}</tex>

Продукции:

<tex>
S \rightarrow aBc \\
aB \rightarrow cA \\
Ac \rightarrow d
</tex>

== Класс 1 ==
Первый класс представлен '''неукорачивающими''' и '''контекстно-зависимыми''' грамматиками.
{{Определение
|id = Неукорачивающие грамматики
|definition =
'''Неукорачивающая грамматика''' (англ. ''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 =
'''Контекстно-зависимая грамматика''' (англ. ''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^* | w = 0^n1^n2^n, n \geqslant 1\}</tex>

Терминалы: <tex>\Sigma = \{0, 1, 2\}</tex>

Нетерминалы: <tex>N = \{S, A\}</tex>

Продукции:

<tex>
S \rightarrow 012 \\
S \rightarrow 0AS2 \\
A0 \rightarrow 0A \\
A1 \rightarrow 11
</tex>

== Класс 2 ==
Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]], которые задают контекстно-свободные языки. Эти языки распознаются с помощью [[Автоматы_с_магазинной_памятью|автоматов с магазинной памятью]].
{{Определение
|definition =
'''Контекстно-свободная грамматика''' (англ. ''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^* | w = w^R\}</tex> (язык палиндромов).

Терминалы: буквы алфавита <tex>\Sigma</tex>

Нетерминалы: <tex>N = {S}</tex>

Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>;

== Класс 3 ==
К третьему типу относятся '''автоматные''' или '''регулярные грамматики''' (англ. ''regular grammars'') {{---}} самые простые из формальных грамматик, которые задают [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярные языки]]. Они являются контекстно-свободными, но с ограниченными возможностями.

Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:
{{Определение
|definition =
'''Леволинейная грамматика''' (англ. ''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>\Sigma = \{a, b, c\}</tex>

Нетерминалы: <tex>\{S, A\}</tex>

Продукции:

<tex>
S \rightarrow aS\ |\ bA \\
A \rightarrow \varepsilon\ |\ cA
</tex>

== См. также ==
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языки]]
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]

==Источники информации==
* ''А. Ахо, Дж. Ульман.'' Теория синтаксического анализа, перевода и компиляции. Синтаксический анализ. Том 2. Пер. с англ. — М.: Книга по Требованию, 2012. — ISBN 978-5-458-27407-4
* [[wikipedia:Chomsky_hierarchy|Wikipedia {{---}} Chomsky hierarchy]]
* [[wikipedia:ru:Иерархия_Хомского|Википедия {{---}} Иерархия Хомского]]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]