TA_FLAT

123456789101112131415
Across
  1. 2. Hierarchical representation of the generation of a string from a grammar.
  2. 7. Property describing two automata that accept the same language.
  3. 8. A Turing machine that can simulate any other Turing machine via encoding.
  4. 9. Fundamental operations in the stack of a PDA.
  5. 10. Represents the null or empty string in automata theory.
  6. 12. CFG form where every production begins with a terminal symbol.
  7. 13. Rules describing operations under which language families remain closed.
  8. 14. Machine that recognizes context-sensitive languages.
  9. 15. Type of regular grammar where terminals appear to the right of non-terminals.
Down
  1. 1. Hypothesis equating effectively computable functions with Turing-computable ones.
  2. 3. A language recognized by a finite automaton or described by a regular expression.
  3. 4. Class of languages accepted by a Turing machine that may not halt for some inputs.
  4. 5. Computational concept allowing multiple possible transitions from a state.
  5. 6. Process of reducing the number of states in a DFA without changing its language.
  6. 11. Denotes the alphabet set in formal language theory.
  7. 13. Operation of joining two strings end-to-end.