Consider the following DFA over Σ = {a, b, c}. Start state q0, which is also the only final state. Transitions:
| State | a | b | c |
|---|---|---|---|
| →* q0 | q1 | q0 | q0 |
| q1 | q1 | q2 | q0 |
| q2 | q1 | q0 | q3 |
| q3 | q4 | q3 | q3 |
| q4 | q4 | q5 | q3 |
| q5 | q4 | q3 | q0 |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. L = {set of strings having an even count (including 0) of substring 'abc'}
Explanation
States q0, q1, q2 track progress towards 'abc' (q1 after 'a', q2 after 'ab'); reading 'c' in q2 completes an 'abc' and moves to q3. States q3, q4, q5 do the same job, and completing 'abc' from q5 returns to q0. So the machine flips between the two halves each time 'abc' occurs, and accepts (q0) exactly when the number of 'abc' substrings is even, including 0.More Theory of Computation and Compilers questions
- Match List I with List IIList I List II A. Type 3 Grammar I. V → (V ∪ Σ)* B. Type 2 Grammar II. αVβ → α(V ∪ Σ)⁺β, where α, β ∈ (V ∪ Σ)* C.…
- Arrange the following parsers in increasing order of their power of handling grammars, i.e. from the least powerful parser to the most powe…
- What are the various LEADERS (leading statements) for the TAC given in the passage?
- Which of the following is the optimized version of the TAC given in the passage?
- Which of the following is the correct high level code for the TAC given in the passage?
- What blocks do Block 3 and Block 5 dominate in the flow graph for the TAC given in the passage? (Basic blocks: B1 = 100–102, B2 = 103, B3 =…