New answers tagged pushdown-automata
0
If you want to read a word $w$ with a PDA, and know if $w\in L$ or not, then you could:
put the letters of $w$ in the stack of the PDA until you read a $c$;
read the $c$ without changing the stack. If there is no $c$, then $w\notin L$;
read the remaining of $w$:
if you read another $c$, then $w\notin L$;
if the stack is empty before the end of $w$, then $w\...
0
The set of languages of type $3$ is a proper subset of the of languages of type $2$. In other words, a language of type $3$ is also a language of type $2$.
If some automaton can recognize languages of type $2$, then it can also recognize languages of type $3$.
Top 50 recent answers are included
Related Tags
pushdown-automata × 441automata × 192
context-free × 192
formal-languages × 132
finite-automata × 48
formal-grammars × 36
nondeterminism × 34
turing-machines × 33
regular-languages × 28
computability × 21
closure-properties × 18
pumping-lemma × 13
computation-models × 13
simulation × 13
parsers × 10
complexity-theory × 7
undecidability × 7
halting-problem × 6
reference-request × 5
regular-expressions × 5
context-sensitive × 5
terminology × 4
proof-techniques × 4
programming-languages × 3
compilers × 3