Изменения

'''Иерархия Хомского''' — {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.

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

Язык <tex>L=\{w \in \Sigma^* | w = 0^n1^n2^n, n \ge 1\}</tex>.

Терминалы: <tex>\Sigma = \{0, 1, 2\}</tex>; Нетерминалы: <tex>\{S, A\}</tex>; Продукции:

S \rightarrow 0TS2 0AS2 \\T0 A0 \rightarrow 0T 0A \\ T1 A1 \rightarrow 11

'''Язык палиндромов'''. Задаётся формулой <tex>L=\{w \in \Sigma^* | w = w^R\}</tex>(язык палиндромов).

НетерминалНетерминалы: <tex>S</tex>;

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

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

Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего видаТерминалы:* <tex>A \rightarrow B\gamma</tex> или <tex>A \rightarrow \gamma</tex>{a, где <tex>\gamma \in V_T^*b, A, B \in V_N</tex> (для леволинейных грамматик).* <tex>A \rightarrow \gamma B</tex>c}; или <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Нетерминалы: {S, possibly preceded by a single nonterminal (left regular)A}; 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.

== Распознавание ==Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица сопоставляет классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.{| class="wikitable"|-! Грамматика! Языки! Машина|-| Класс 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 машина Тьюринга]|-<tex>S \rightarrow aS\ | Класс 1\ bA \\A \rightarrow \varepsilon\ | контекстно-зависимые\ cA| [http://en.wikipedia.org/wiki</Linear_bounded_automaton ЛПА]|-| Класс 2| контекстно-свободные| [[Автоматы с магазинной памятью|автоматы с магазинной памятью]]|-| Класс 3| [[Регулярные языки: два определения и их эквивалентность|регулярные]]| [[Детерминированные конечные автоматы|конечные автоматы]]|}tex>