Совпадение множества языков МП-автоматов и контекстно-свободных языков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение МП-автомата по заданной КС-грамматике)
(Эквивалентность МП-автоматов и КС-языков)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
== Эквивалентность МП-автоматов и КС-языков ==
 
== Эквивалентность МП-автоматов и КС-языков ==
 +
Далее будут приведены конструкции для построения МП-автомата по заданной КС-грамматике, и наоборот. Также будут приведены теоремы об эквивалентности языков.
 
=== Построение МП-автомата по заданной КС-грамматике ===
 
=== Построение МП-автомата по заданной КС-грамматике ===
 
{{Определение
 
{{Определение

Версия 01:36, 15 января 2011

Эта статья находится в разработке!

Эквивалентность МП-автоматов и КС-языков

Далее будут приведены конструкции для построения МП-автомата по заданной КС-грамматике, и наоборот. Также будут приведены теоремы об эквивалентности языков.

Построение МП-автомата по заданной КС-грамматике

Определение:
Пусть [math] G=(V,T,Q,S) [/math] — КС-грамматика. Построим МП-автомат [math] P=(\{q\},T,V \cup T, \delta ,q,S) [/math], который допускает [math] L(G) [/math] по пустому магазину. Функция переходов [math] \delta [/math] будет определена по следующим правилам:
  • 1. [math] \delta(q,\epsilon,A)=\{(q,\beta )| A \rightarrow \beta[/math] — продукция [math] G \} [/math] — для каждой переменной [math] A [/math].
  • 2. [math] \delta(q,a,a)=\{(q,\epsilon)\} [/math] для каждого терминала [math] a [/math].

Пример.

Преобразуем грамматику выражений в МП-автомат. Пусть дана грамматика:

  • [math] I \rightarrow a|b|I1|I0|Ia|Ib [/math]
  • [math] E \rightarrow I|E*E|E+E|(E) [/math]

Множеством входных символов является [math] \{a,b,1,0,(,),+,*\} [/math]. Эти символы, вместе с переменными [math] I,E [/math], образуют магазинный алфавит. Функция переходов определена следующим образом:

  • a) [math] \delta(q,\epsilon,I)={(q,a), (q,b), (q,Ia), (q,Ib), (q,I0), (q,I1)};[/math]
  • b) [math] \delta(q,\epsilon,E)={(q,I), (q,E+E), (q,E*E), (q,(E))};[/math]
  • c) [math] \delta(q,a,a)=\{(q,\epsilon)\}[/math];[math] \delta(q,b,b)=\{(q,\epsilon)\}[/math];[math] \delta(q,1,1)=\{(q,\epsilon)\}[/math];[math] \delta(q,0,0)=\{(q,\epsilon)\}[/math];[math] \delta(q,),))=\{(q,\epsilon)\}[/math];[math] \delta(q,(,()=\{(q,\epsilon)\}[/math];[math] \delta(q,+,+)=\{(q,\epsilon)\}[/math];[math] \delta(q,*,*)=\{(q,\epsilon)\}[/math];

Пункты a,b образованы по первому правилу построения функции переходов, пункт c по второму правилу.

Теорема (О совпадении КС-языков и множества языков МП-автомата):
Если МП-автомат [math] P [/math] построен по грамматике [math] G [/math] по указанной выше конструкции, то [math] N(P)=L(G) [/math]