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 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)