175
правок
Изменения
→Корректность построения
|statement= Если КС-грамматика <tex> G </tex> построена по МП-автомату <tex> P </tex>, с использованием указанной выше конструкции, то <tex> N(P) \subseteq L(G) </tex>
|proof= Выше доказана корректность построения КС-грамматики по МП-автомату. Значит языки допускаемые МП-автоматами являются подмножеством языков, заданных КС-грамматикой.
}}
=== Эквивалентность языков МП-автоматов и КС-языков===
{{Теорема
|about= Об эквивалентности языков МП-автоматов и КС-языков
|statement= Множество языков, допускаемых МП-автоматами совпадает с множеством языков, задаваемых с помощью контекстно-свободных грамматик.
|proof= Из утверждения 1 следует, что <tex> L(G) \subseteq N(P) </tex>, в свою очередь из утверждения 2 следует, что <tex> N(P) \subseteq L(G) </tex>. Отсюда <tex> L(G)=N(P) </tex>.
}}
