The transition function for the language \(L=\{w \mid n_a (w) \text{ and }…
2015
The transition function for the language \(L=\{w \mid n_a (w) \text{ and } n_b(w) \text{ are both odd} \}\) is given by:
The initial and final states of the automata are
- A.
𝑞0 and 𝑞0 respectively
- B.
𝑞0 and 𝑞1 respectively
- C.
𝑞0 and 𝑞2 respectively
- D.
𝑞0 and 𝑞3 respectively
Attempted by 174 students.
Show answer & explanation
Correct answer: D
Key idea: the four states track the parity (even/odd) of counts of a and b: q0 = (even a, even b), q1 = (odd a, even b), q2 = (even a, odd b), q3 = (odd a, odd b).
Start state: q0 because before reading any input both counts are zero (even).
Accepting state: q3 because the language requires both a and b counts to be odd, and q3 represents (odd a, odd b).
How transitions work: reading 'a' toggles the a-parity (moves between states that differ in the a-parity), reading 'b' toggles the b-parity.
Example check:
Start at q0. Reading 'a' leads to q1 (odd a, even b).
From q1, reading 'b' leads to q3 (odd a, odd b), which is accepting. So the string 'ab' is accepted, matching the requirement.
Conclusion: initial state is q0 and the accepting (final) state is q3.
A video solution is available for this question — log in and enroll to watch it.