In the ε-NFA M = ({q0, q1, q2, q3}, {a}, δ, q0, {q3}), where δ is given in the transition table below, what is the minimum length of string to reach the final state?
| State | ε | a |
|---|---|---|
| q0 | {q1} | { } |
| q1 | {q2} | { } |
| q2 | { } | {q2, q3} |
| q3 | { } | { } |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 1
Explanation
q0 →ε q1 →ε q2 →a q3. Exactly one 'a' is needed, so the shortest accepted string has length 1.More Theory of Computation and Compilers questions
- Which of the following is (are) correct about the regular expression a a* b b* c c* d d*? 1. The language for the given expression is L = {…
- Which of the following statements are correct? 1. The first three-address instruction in the intermediate code is a leader. 2. The instruct…
- Which of the following are correct for regular expressions? a. φ + L = L + φ = L b. εL = Lε = L c. φL = Lφ = φ d. φL = Lφ = L Choose the co…
- Match the following based on the lengths of strings in the language accepted (using the brute-force method of parsing). Choose the correct…
- What is the safest order for simplifying a context-free grammar?
- What is the move in the cell numbered M1 of the table?