The minimum state DFA of the following would be the following: (a DFA with states q0 (start), q1, q2, q3 and q4 (accepting) is given, with transitions q0→0 q1, q0→1 q3, q1→0 q1 (self-loop), q1→1 q4, q3→0 q2, q3→1 q4, q2→1 q4, over the alphabet {0,1})
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. A –(0,1)→ B, B has a self-loop on 0, B –1→ C
Explanation
States q1, q2 and q3 are all non-accepting and all three transition to the accepting state q4 on input 1 (q1→1q4, q3→1q4, q2→1q4), and on input 0 each of them stays within the group {q1,q2,q3} (q1→0q1, q3→0q2). So q1, q2 and q3 are equivalent and merge into a single state B. The start state q0 goes to this same group {q1,q2,q3} on both 0 and 1 (q0→0q1, q0→1q3), so q0 becomes state A. The minimized DFA is therefore A –(0,1)→ B, with B having a self-loop on 0, and B –1→ C (the accepting state) – option (1).More Theory of Computation and Compilers questions
- Find the Follow (A) & Follow (C).
- In the LL(1) Parsing table of the given CFG, how many valid non-blank entries will be there in the rows for variables 'B' and 'D'?
- Identify the correct statement from the following.
- What will be the FIRST(S) & FIRST(D)?
- The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?
- Which of the following Grammars is/are only Context Free (i.e. context-free but not regular grammars)?Grammar Productions A S → Ab aS → aA…