Как определить язык по автомату с магазинной памятью (ДМПА)?

Question

[jane555]

Как определить язык L(P), который задается детерминированным автоматом с магазинной памятью Р({q0,q1,q2,q3},{a,b,c},{Z,c},q0,Z,delta,{q3}) , если дана функция переходов delta. Например, такая:
1)delta(q0,c,Z) = {(q0,cZ)}
2) delta(q0,c,c) = {(q0,cc)}
3) delta(q0,a,c) = {(q1,c)}
4) delta(q1,a,c) = {(q2,c)}
5) delta(q2,a,c) = {(q1,lambda)}
6) delta(q1,b,Z) = {(q3,Z)}
7) delta(q3,b,Z) = {(q3,Z)}
8) delta(q0,a,Z) = {(q1,Z)}
9) delta(q3,lambda,Z) = {(q3,lambda)}
Что в этом примере обозначает lambda?
В лекциях обычно нахожу задачу, определить, что какая-то конкретная цепочка распознается автоматом, и это несложно. Но нигде не могу найти алгоритм действий, как по функции переходов определить язык.

Answer 1

[Rsa97]

Анализировать переходы.
delta(q0,c,Z) = {(q0,cZ)} - состояние q0, на входе символ 'c', в стеке пусто. Остаёмся в q0, в стек кладём 'c'.
delta(q0,c,c) = {(q0,cc)} - состояние q0, на входе 'c', с вершины стека снят 'c'. Остаёмся в q0, в стек кладём 'c', 'c'.
И так далее.
lambda - это пустой символ λ.
Ну а язык, вроде, cⁿa²ⁿ⁺¹b^*

Comments

[jane555]

Спасибо! Построила граф, так получилось проще понять закономерность, и ответ сошелся с вашим