ДМП-автоматы и неоднознчность — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}}»)
 
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 +
{{Теорема
 +
|statement=Пусть P=(Q,<tex>\Sigma</tex>,<tex>\Gamma</tex>, <tex>\delta</tex>,<tex>q_0</tex>,<tex>Z_0</tex>) - МП-автомат. Тогда существует КС-грамматика G, для которой L(G)=N(P)
 +
|proof=
 +
}}
 +
 +
 +
{{Теорема
 +
|statement=Если L=N(P) для некоторого ДМП автомата P, то L имеет однозначную КС-грамматику
 +
|proof=
 +
}}

Версия 00:49, 31 декабря 2014

Эта статья находится в разработке!
Теорема:
Пусть P=(Q,[math]\Sigma[/math],[math]\Gamma[/math], [math]\delta[/math],[math]q_0[/math],[math]Z_0[/math]) - МП-автомат. Тогда существует КС-грамматика G, для которой L(G)=N(P)


Теорема:
Если L=N(P) для некоторого ДМП автомата P, то L имеет однозначную КС-грамматику