Изменения

Наша конструкция эквивалентной грамматики использует переменные вида: <tex> [pXq]</tex> — которая означает, что в процессе изменения состояния автомата от <tex> p </tex> до <tex> q </tex>, <tex> X </tex> удалилось из стека.<br>

[[Файл:-pXq-.jpg]]

Следует отметить, что удаление <tex> X </tex> может являться результатом множества переходов.<br>

Пусть <tex> P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0)</tex> — МП-автомат. Построим <tex> G=(V,\Sigma,R,S)</tex>, где <tex> V </tex> состоит из: