Skip to main content

All Questions

Filter by
Sorted by
Tagged with
11 votes
3 answers
1k views

Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
Antimony's user avatar
  • 917