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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Иерархия Хомского''' (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
+
'''Иерархия Хомского''' классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 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 ==
Первый класс представлен '''неукорачивающими''' и '''контекстно-зависимыми''' грамматиками.
+
Класс 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 =
 
|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> не встречается в правых частях правил).
+
'''Неукорачивающие грамматики''' - это [[формальные грамматики]],  
}}
+
всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha \in \{\Sigma\cup N\}^{+}</tex>, <tex>\beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha|\leq|\beta|</tex>, кроме, возможно, <tex>S\rightarrow \epsilon</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 ==
Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]], которые задают контекстно-свободные языки. Эти языки распознаются с помощью [[Автоматы_с_магазинной_памятью|автоматов с магазинной памятью]].
+
Класс 2 составляют [[контекстно-свободные грамматики]].
 
{{Определение
 
{{Определение
 
|definition =
 
|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>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'') {{---}} самые простые из формальных грамматик, которые задают [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярные языки]]. Они являются контекстно-свободными, но с ограниченными возможностями.
+
Класс 3 составляют [[праволинейные(автоматные) грамматики]].
 
 
Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:
 
{{Определение
 
|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 =
 
|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>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>.}}
Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык уже не обязан быть регулярным.
 
 
 
Также можно [[Правоконтекстные_грамматики,_эквивалентность_автоматам|показать]], что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]].
 
 
 
===Пример===
 
<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
 
* [[wikipedia:Chomsky_hierarchy|Wikipedia {{---}} Chomsky hierarchy]]
 
* [[wikipedia:ru:Иерархия_Хомского|Википедия {{---}} Иерархия Хомского]]
 
 
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Базовые понятия о грамматиках]]
 

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

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

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

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