175
правок
Изменения
→Построение КС-грамматики по МП-автомату
=== Построение КС-грамматики по МП-автомату ===
Наша конструкция эквивалентной грамматики использует переменные вида: <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> состоит из:
*1 Специальный стартовый символ <tex> S </tex>
*2 Все символы вида <tex> [pXq]</tex>, где <tex> p </tex> и <tex> q </tex> — состояния из <tex> Q </tex>
