Редактирование: Правоконтекстные грамматики, эквивалентность автоматам

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Праволинейной грамматикой''' (англ. ''right linear grammar'') называется [[Формальные_грамматики | грамматика]], в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.
+
'''Праволинейной грамматикой''' <tex>\Gamma</tex> (англ. ''right linear grammar'') называется [[Формальные_грамматики | грамматика]], в которой все правила имеют вид <tex> A \to a </tex>, <tex> A \to aB </tex>.
 
}}
 
}}
  
Строка 14: Строка 14:
 
:* Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.
 
:* Докажем, что если для автомата верно <tex>\langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>, то для построенной грамматики верно <tex> S \Rightarrow^* \alpha U </tex>. Будем доказывать индукцией по переходам в автомате.
  
::* Базой индукции будут переходы за <tex> 0 </tex> шагов.
+
::* Базой индукции будут переходы за 0 шагов.
 
::* Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем, что верно и для переходов за <tex>k</tex> шагов.
 
::* Индукционный переход: пусть данное свойство выполняется для переходов длины <tex>k-1</tex>. Докажем, что верно и для переходов за <tex>k</tex> шагов.
  
Строка 22: Строка 22:
 
:* Докажем в обратную сторону, а именно из <tex> S \Rightarrow^* \alpha U </tex> следует <tex> \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>. Доказательство также проведем по индукции. Индукция будет идти по количеству примененных подряд правил.
 
:* Докажем в обратную сторону, а именно из <tex> S \Rightarrow^* \alpha U </tex> следует <tex> \langle S, \alpha \rangle \vdash^* \langle U, \varepsilon \rangle </tex>. Доказательство также проведем по индукции. Индукция будет идти по количеству примененных подряд правил.
  
::* Базой индукции будут строки, выводимые в грамматике из начального нетерминала <tex> S </tex> за <tex> 0 </tex> применений правил.
+
::* Базой индукции будут строки, выводимые в грамматике из начального нетерминала <tex> S </tex> за 0 применений правил.
  
 
::* Индукционный переход: пусть верно для <tex>k-1</tex> применения правил. Рассмотрим произвольную строку, полученную за <tex>k</tex> применений правил. Рассмотрим последнее применение правила. Если оно имело вид <tex> A \to aB </tex>, значит в автомате возможен переход <tex> \langle A,a \rangle \vdash \langle B,\varepsilon \rangle </tex>, а если <tex> A \to a </tex>, то <tex> B </tex> является допускающим в автомате. Таким образом, свойство выполняется для <tex> k </tex> последовательно примененных правил. Эквивалентность языков автомата и грамматики доказана.
 
::* Индукционный переход: пусть верно для <tex>k-1</tex> применения правил. Рассмотрим произвольную строку, полученную за <tex>k</tex> применений правил. Рассмотрим последнее применение правила. Если оно имело вид <tex> A \to aB </tex>, значит в автомате возможен переход <tex> \langle A,a \rangle \vdash \langle B,\varepsilon \rangle </tex>, а если <tex> A \to a </tex>, то <tex> B </tex> является допускающим в автомате. Таким образом, свойство выполняется для <tex> k </tex> последовательно примененных правил. Эквивалентность языков автомата и грамматики доказана.
Строка 33: Строка 33:
  
 
:* Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex>  длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k  \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует соответствующая последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.
 
:* Докажем, что если слово допускается автоматом, то его можно вывести в грамматике. Рассмотрим слово <tex> \alpha </tex>  длины <tex> k </tex>. Рассмотрим какую-либо последовательность переходов автомата, допускающую данное слово <tex> \langle S,\alpha \rangle \vdash^k  \langle ok,\varepsilon \rangle </tex>. Для каждого одношагового перехода в автомате существует соответствующее правило в грамматике. Значит для подпоследовательности переходов из <tex> k-1 </tex> шага <tex> \langle S, \alpha \rangle \vdash^{k-1} \langle U,c \rangle </tex> существует соответствующая последовательность применений правил <tex> S \Rightarrow^{k-1} \alpha c^{-1} U </tex>. Для последнего перехода в автомате <tex> \langle U,c \rangle \vdash \langle ok, \varepsilon \rangle </tex> существует правило <tex> U \Rightarrow c </tex>. Таким образом, существует последовательность применений правил грамматики, выводящая слово <tex> \alpha </tex>.
 +
 +
Теорема доказана.
 +
 
}}
 
}}
==См. также==
 
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языки]]
 
*[[Иерархия Хомского формальных грамматик]]
 
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
 
  
== Источники информации ==
+
== Литература ==
* ''Michael A. Harrison'' Introduction to Formal Language Theory. — Addison-Wesley, 1978. — ISBN 978-0201029550. (с  19-20, 60-63.)
+
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.
* [[wikipedia:en:Linear grammar#Relationship with regular grammars|Wikipedia {{---}} Linear grammar]]
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
 

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

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

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

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