Across
- 1. Context-free grammar abbreviation
- 4. A machine that can compute anything that is computable
- 6. Problem The famous undecidable problem by Alan Turing
- 8. When there is only one possible state transition
- 10. A type of automaton where multiple transitions are allowed
- 11. The set of strings over an alphabet
Down
- 2. A mathematical structure defining input-output behavior
- 3. Automaton A type of automaton used to recognize context-free languages
- 5. The language class recognized by a finite automaton
- 7. A problem that can be solved by an algorithm
- 9. A problem with no algorithmic solution