Pushdown Automata

[!math|{“type”:“definition”,“number”:“auto”,“setAsNoteMathLink”:false,“title”:“Non-deterministic Pushdown Automaton”,“label”:“non-deterministic-pushdown-automaton”,“_index”:0}] Definition 1 (Non-deterministic Pushdown Automaton). NPDA $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ accepts string $w={\Sigma }^{\star }$ if $w$ can be written as

$$w_1{w}_2{w}_3\dots w_m\in (\Sigma \cup \{ϵ\}{)}^{\star }$$

and

• there exists states $r_0,r_1,\dots ,r_m$ and
• there exists strings $s_0,s_1,\dots ,s_m$ in $(\Gamma \cup \{ϵ\}{)}^{\star }$
  • $r_0=q_0$ and $s_0=ϵ$