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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 13: Строка 13:
  
 
===Пример===
 
===Пример===
 +
Терминалы: <tex>\Sigma = \{a, c, d\}</tex>
 +
 +
Нетерминалы: <tex>N = \{S, A, B\}</tex>
 +
 
Продукции:
 
Продукции:
  
Строка 23: Строка 27:
 
</tex>
 
</tex>
  
Выведем в данной грамматике строку <tex>addd</tex>:
+
Выведем в данной грамматике строку <tex>w = 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>
+
<tex>S \rightarrow aBcc \rightarrow aAcc \rightarrow aBc \rightarrow aAc \rightarrow aB \rightarrow aA \rightarrow adB \rightarrow adA \rightarrow adAAA \rightarrow addBAA \rightarrow addd</tex>
  
 
== Класс 1 ==
 
== Класс 1 ==
Строка 40: Строка 44:
 
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
 
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
  
[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Известно]], что неукорачивающие грамматики эквивалентны контекстно-зависимым.
+
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|в другом конспекте]], неукорачивающие грамматики эквивалентны контекстно-зависимым.
  
 
===Пример===
 
===Пример===
<tex>L=\{w \in \Sigma^* \mid w = 0^n1^n2^n, n \geqslant 1\}</tex>
+
Язык <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>
  
 
Продукции:  
 
Продукции:  
Строка 60: Строка 68:
 
'''Контекстно-свободная грамматика''' (англ. ''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>N = \{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>;
  
 
== Класс 3 ==
 
== Класс 3 ==
Строка 79: Строка 91:
 
'''Праволинейная грамматика''' (англ. ''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>.
 
'''Праволинейная грамматика''' (англ. ''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>L</tex> для регулярного выражения <tex>a^*bc^*</tex>.
 +
 
 +
Терминалы: <tex>\Sigma = \{a, b, c\}</tex>
 +
 
 +
Нетерминалы: <tex>N = \{S, A\}</tex>
  
 
Продукции:
 
Продукции:
Строка 94: Строка 110:
  
 
== См. также ==
 
== См. также ==
* [[Правоконтекстные грамматики, эквивалентность автоматам]]
+
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языки]]
 
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
 
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
  
Строка 104: Строка 120:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
 

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

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

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

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