Конфигурация автомата с магазинной памятью

Пусть:

• дан ДАМП $A$ и слово $w\in {\Sigma }^{\ast }$
• Автомат $A$ начал обрабатывать слово $w$
• Автомат $A$ перешел к такту с номером $i$ во время обработки слова $w$

Тогда конфигурацией автомата называется тройка $(q_i,{\beta }_i,v_i)$, где

• $q_i\in Q$ - состояние автомата на такте $i$
• ${\beta }_i\in {\Delta }^{\ast }$ - содержимое стека автомата на такте $i$
• $v_i$ - необработанная автоматом $A$ часть цепочки $w$ на $i$-ом такте работы автомата $A$

Конфигурацию автомата коротко обозначают как $[q_i,{\beta }_i,v_i]$

Запись $[q_i,{\beta }_i,v_i]\models [q_{i+1},{\beta }_{i+1},v_{i+1}]$ обозначает переход автомата $A$ из $i$-го такта в $i+1$-ый и, соответственно смену его конфигурации

Запись $[q_i,{\beta }_i,v_i]\models [q_j,{\beta }_j,v_j]$ обозначает, что автомат перешел из левой конфигурации в правую за несколько (0 и более) тактов