How many states are there in a minimum state automata equivalent to regular expression given below? a * b(a + b) Regular expression is
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. 3
Explanation
States: start (loop on a), after b, and after one more symbol (accepting). That is 3 states, plus a dead state if the DFA must be complete.
Note: Counting the dead (trap) state as well gives 4.
More Theory of Computation and Compilers questions
- Match List I with List II, where L1 is regular, L2 context-free, L3 recursive and L4 recursively enumerable. List I: (a) complement(L3) ∪ L…
- How can the decision algorithm be constructed L for deciding whether context-free language is finite? CFGG (a) By constructing redundant in…
- Consider the following grammar : S → XY X → Y aY ∣ a and Y → bbX Which of the following statements is/are true about the above grammar? (a)…
- Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing M machine ? G L(G) = ϕ (a) is a CFG with M M…
- For a statement L ⊆ Σ∗ A language is recursive if there exists M some turing machine . Which of the following conditions is satisfied for ω…
- Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions. Consider: (i) L(s) ⊆ L(r) and L(s) ⊆ L(t) (ii) L(r) ⊆ L(s) and L(s) ⊆…