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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Иерархия Хомского''' (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
+
'''Иерархия Хомского''' классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
 
}}
 
}}
 
== Класс 0 ==
 
== Класс 0 ==
Строка 11: Строка 11:
  
 
Практического применения в силу своей сложности такие грамматики не имеют.
 
Практического применения в силу своей сложности такие грамматики не имеют.
 
===Пример===
 
Продукции:
 
 
<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 = Неукорачивающие грамматики
 
|id = Неукорачивающие грамматики
 
|definition =
 
|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> не встречается в правых частях правил).
+
'''Неукорачивающая грамматика''' (англ. ''noncontracting grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha|\leq|\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> не встречается в правых частях правил).
 
'''Контекстно-зависимая грамматика''' (англ. ''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'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
 
  
[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Известно]], что неукорачивающие грамматики эквивалентны контекстно-зависимым.
+
Языки, заданные этими грамматиками, распознаются с помощью '''линейного ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
 +
 
 +
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]], неукорачивающие грамматики эквивалентны контекстно-зависимым.
  
 
===Пример===
 
===Пример===
<tex>L=\{w \in \Sigma^* \mid w = 0^n1^n2^n, n \geqslant 1\}</tex>
+
Язык <tex>0^n1^n2^n</tex>.
  
Продукции:
+
<tex>\Sigma = \{0, 1, 2\}</tex>;
  
 
<tex>
 
<tex>
 
S \rightarrow 012 \\
 
S \rightarrow 012 \\
S \rightarrow 0AS2 \\
+
S \rightarrow 0TS2 \\
A0 \rightarrow 0A \\  
+
T0 \rightarrow 0T \\  
A1 \rightarrow 11  
+
T1 \rightarrow 11  
 
</tex>
 
</tex>
  
 
== Класс 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>.
 
'''Контекстно-свободная грамматика''' (англ. ''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>L=\{w \in \Sigma^* | w = w^R\}</tex>
 +
 
 +
Терминалы: буквы алфавита <tex>\Sigma</tex>;
 +
 
 +
Нетерминал: <tex>S</tex>;
 +
 
 +
Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>;
  
Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>
+
Начальный нетерминал {{---}} <tex>S</tex>.
  
 
== Класс 3 ==
 
== Класс 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>.
 
}}
 
Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык уже не обязан быть регулярным.
 
  
Также можно [[Правоконтекстные_грамматики,_эквивалентность_автоматам|показать]], что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]].
+
Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:
 +
* <tex>A \rightarrow B\gamma</tex> или <tex>A \rightarrow \gamma</tex>, где <tex>\gamma \in V_T^*, A, B \in V_N</tex> (для леволинейных грамматик).
 +
* <tex>A \rightarrow \gamma B</tex>; или <tex>A \rightarrow \gamma</tex>, где <tex>\gamma \in V_T^*, A, B \in V_N</tex> (для праволинейных грамматик).
 +
Регулярные грамматики применяются для описания простейших конструкций: [[идентификатор]]ов, [[Строковый тип|строк]], [[Константа (программирование)|констант]], а также [[язык ассемблера|языков ассемблера]], [[командный процессор|командных процессоров]] и др.
  
===Пример===
+
Type-3 grammars (regular grammars) generate the regular languages. Such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed by a single nonterminal (right regular). Alternatively, the right-hand side of the grammar can consist of a single terminal, possibly preceded by a single nonterminal (left regular); these generate the same languages – however, if left-regular rules and right-regular rules are combined, the language need no longer be regular. The rule S \rightarrow \epsilon is also allowed here if S does not appear on the right side of any rule. These languages are exactly all languages that can be decided by a finite state automaton. Additionally, this family of formal languages can be obtained by regular expressions. Regular languages are commonly used to define search patterns and the lexical structure of programming languages.
<tex>L</tex> для регулярного выражения <tex>a^*bc^*</tex>.
 
  
Продукции:
+
{{Определение
 +
|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>.}}
  
<tex>
+
== Распознавание ==
S \rightarrow aS\ |\ bA \\
+
Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица сопоставляет классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.
A \rightarrow \varepsilon\ |\ cA
+
{| class="wikitable"
</tex>
+
|-
 +
! Грамматика
 +
! Языки
 +
! Машина
 +
|-
 +
| Класс 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
 +
| [[Регулярные языки: два определения и их эквивалентность|регулярные]]
 +
| [[Детерминированные конечные автоматы|конечные автоматы]]
 +
|}
  
 
== См. также ==
 
== См. также ==
* [[Правоконтекстные грамматики, эквивалентность автоматам]]
+
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языки]]
 
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
 
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
  
Строка 104: Строка 115:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
 

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

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

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

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