Let ∑ = {0, 1}, then an automaton A accepting only those words from ∑ having…
Let ∑ = {0, 1}, then an automaton A accepting only those words from ∑ having an odd number of 1’s requires _________ states including the start state
Answer: A. 2 — The automaton must track whether the number of 1's in a string is odd or even. This requires two states: one for an even count of 1's (start state) and…
- A.
2
- B.
3
- C.
4
- D.
5
Attempted by 156 students.
Show answer & explanation
Correct answer: A
The automaton must track whether the number of 1's in a string is odd or even. This requires two states: one for an even count of 1's (start state) and another for an odd count. Transitions flip between these states upon reading a '1', while '0' keeps the current state. The accepting state is the one representing an odd count, so only 2 states are needed.
Loading lesson…