Intro to Automata

123456789101112
Across
  1. 2. A classic problem in the theory of computation, asking whether a given Turing machine will eventually halt for a particular input.
  2. 4. The name of the * which allows you to repeatedly concatenating a string in a language
  3. 8. Properties of formal languages that are preserved under certain operations (union, intersection, complement, concatenation, etc.).
  4. 10. The principle that, in a set of objects, placing more objects than there are slots guarantees repetition
  5. 11. A set that contains only some elements of another set
  6. 12. a function that describes how you go between states for a given input symbol.
Down
  1. 1. A hierarchy of formal languages into four types based on their generative power, named after Noam...
  2. 3. A set of words over an alphabet
  3. 5. Something an automaton might do with a string
  4. 6. Type of language recognized by a deterministic finite automaton
  5. 7. Mathematical model of computation, consisting of states and transitions
  6. 9. Lemma used to show certain languages are not regular