Deterministic finite automata
The deterministic finite automaton: states, transitions, initial state and accepting states, transition table, reading a word, recognized language, complete automaton with a sink state and the complement automaton.
- 24 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Deterministic finite automaton: what is it?
Show the answer
A machine with a finite number of states that reads a word letter by letter, with at most one transition per state and per letter, and a single starting state.
It is a five-tuple (Q, Σ, δ, q₀, F). The computation is unique: a word follows at most one path, so it is accepted or rejected unambiguously. With exactly one transition per state and per letter, the automaton is also complete.
This automaton reads numbers written in binary; the state is the remainder modulo 3 of what has been read, 0 is initial and accepting. It reads 1001. Where does it stop, and is the word accepted?
```text
0 1
→*0 0 1
1 2 0
2 1 2`- In state 0, accepted
- In state 1, rejected
- In state 2, rejected
- In state 1, accepted, since it went through 0
Show the answer
In state 0, accepted
Path: 0 -1→ 1 -0→ 2 -0→ 1 -1→ 0. Stopping in 0 means remainder 0, and 1001 in binary is 9 = 3 × 3. It is accepted because 0 is accepting, not because it was visited earlier.
An automaton is a five-tuple (Q, Σ, δ, q₀, F): Q is the set of …, δ the … function and F the set of … states.
Show the answer
An automaton is a five-tuple (Q, Σ, δ, q₀, F): Q is the set of states, δ the transition function and F the set of accepting states.
q₀ is the initial state, a single one for a deterministic automaton. Σ is the alphabet read.
Transition function: what is it?
Show the answer
The function δ that maps a state and a letter to the state reached by reading that letter from that state.
δ(q, a) = p is drawn as an arrow from q to p labelled a. It fits in a table: one row per state, one column per letter.