Изменения

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

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

28 байт добавлено, 21:01, 16 ноября 2014
Класс 1
== Класс 1 ==
Первый класс представлен '''неукорачивающими''' и '''контекстно-зависимыми''' грамматиками.
 
Type-1 grammars (context-sensitive grammars) generate the context-sensitive languages. These grammars have rules of the form \alpha A\beta \rightarrow \alpha\gamma\beta with A a nonterminal and \alpha, \beta and \gamma strings of terminals and/or nonterminals. The strings \alpha and \beta may be empty, but \gamma must be nonempty. The rule S \rightarrow \epsilon is allowed if S does not appear on the right side of any rule. The languages described by these grammars are exactly all languages that can be recognized by a linear bounded automaton (a nondeterministic Turing machine whose tape is bounded by a constant times the length of the input.)
{{Определение
|id = Неукорачивающие грамматики
|definition =
'''Неукорачивающие грамматикиНеукорачивающая грамматика''' (англ. ''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$ \to 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$ \to rightarrow \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}
 
Языки, заданные этими грамматиками, распознаются с помощью '''линейного ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]], неукорачивающие грамматики эквивалентны контекстно-зависимым.
 
===Пример===
Язык <tex>0^n1^n2^n</tex>.
 
<tex>\Sigma = \{0, 1, 2\}</tex>;
 
<tex>
S \rightarrow 012 \\
S \rightarrow 0TS2 \\
T0 \rightarrow 0T \\
T1 \rightarrow 11
</tex>
== Класс 2 ==
418
правок

Навигация