- Let me know about any preferences re names
- Section 1.1 through “Designing Finite Automata”
- Finite automata are simple models of limited-memory computers
- 5-tuple ( states, alphabet, transition function, start state, accept states )
- Transition functions maps states and strings to states
- Either accepts or doesn’t string in language
- Input accepted if there is path from start state to accept state
- Represented by state diagrams
- Strings, languages, alphabets?
- Language consisting of all 3-bit odd binary numbers
- {001, 011, 101, 111}
- Alphabet = {0, 1}
- Language consisting of all 3-bit odd binary numbers
- Automata examples
- Finite automata are widely used to model the control parts of digital circuits
- Automaton that recognizes the 3-bit odd numbers language
- Beware the difference between the empty string and the empty language
- Empty string is a string with no symbols in it, but it can still be accepted (or not) by an automaton
- A language containing just the empty string contains 1 string, and so is not empty itself
- Automaton that recognizes language over {a,b,c} consisting of all strings that contain exactly 1 a
- And language over {a,b,c} consisting of all strings that don’t contain exactly 1 a
- And language over {a,b,c} consisting of all strings that don’t contain exactly 1 a
- Finite automata are widely used to model the control parts of digital circuits
- Let’s make finite automata more powerful
- Nondeterministic finite automata
- Read section 1.2 from beginning through “Formal Definition…”