← back to the Substrate Record
qid 10589 · computer science
Question: The language {ww | w in (0 + 1)*} is
- accepted by some Turing machine, but by no pushdown automaton
- context-free, but not regular
- accepted by some finite automaton, but not pushdown automaton
- accepted by some Turing machine and some pushdown automaton
- accepted by any context-free grammar, but not regular
- accepted by some context-free grammar, but not Turing machine
- regular, but not context-free
- accepted by some pushdown automaton, but not context-free
- not accepted by any Turing machine
Our answer: A. accepted by some Turing machine, but by no pushdown automaton Source quote machine-checked (exact quote)
How it was answered
Multi-step solver (maze), replayed by code
Current source
Wikipedia, "Context-free language"
https://en.wikipedia.org/wiki/Context-free_language
“The context-free nature of the language makes it simple to parse with a pushdown automaton.”
Source quote machine-checked (exact quote)
Earlier version (superseded)
No public source has been found for this card yet (3 places checked internally).
If you have a Citable Source to dispute or challenge this, ADD IT so we can correct the answer by appending, never deleting. — hello@lianabanyan.com