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