143
правки
Изменения
перевод на русский
{{Лемма
|statement=
Для любой формальной грамматики существует машина Тьюринга, распознающая этот языкэтой грамматики.
|proof=
Пусть <tex>G = (N, \Sigma, P, S)</tex> — грамматика и <tex>L = L(G)</tex>. Опишем неформально недетерминированную машину Тьюринга <tex>Tm</tex>, допускающую <tex>L</tex>.<br>
