Key Terms
Alphabet, word/string, language, , , , decision problem, countably infinite, uncountably infinite, graph, non-determinism
Automata design exercises
words of length at least 3, even binary numbers
Skills to develop
learn to design automata for a given language, write a proof that an automaton is correct (by induction on the length of the input word)
References
Sipser (2013) Section 1.1
Practice Problems
Ignore the words Deterministic / DFA in the following problems.
Sipser: Exercise 1.1 (Page 83)
Kozen: Homework 1 Problem 1 (a,b,c,d) (Page 301)
References
Sipser, M. (2013). Introduction to the Theory of Computation (Third edition, international edition). Cengage Learning.