New answers tagged nondeterminism
2
votes
Accepted
Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$
Your language is NCFL. Your design of NPDA is perfectly right. And in state $q_0,q_1$ and $q_2$ transitions makes your diagram NPDA. You accepts your strings by final state that is $q_3.$ If you want ...
Top 50 recent answers are included
Related Tags
nondeterminism × 369finite-automata × 133
automata × 95
turing-machines × 83
complexity-theory × 80
formal-languages × 38
pushdown-automata × 36
regular-languages × 27
algorithms × 25
context-free × 21
np × 21
time-complexity × 20
space-complexity × 20
computation-models × 18
polynomial-time × 15
regular-expressions × 14
closure-properties × 13
computability × 11
terminology × 10
satisfiability × 9
simulation × 9
np-complete × 8
reference-request × 8
complexity-classes × 7
formal-grammars × 6