Reference no: EM132681104

Question 1. Let M be an NFA with n states. Show that if |L(M )| > 1 then ∃w ∈ L(M ) with |w| < n. You may use without proof the fact that δY(q0, xy) = p∈δY(q ,x) δY(p, y).

Question 2. Let M be an NFA with n states. Show that if |L(M )| > 1 then there does not necessarily ∃w ∈ L(M ) with |w| < n.

Question 3. Prove that the following machine M that accepts the language L = 0i : i > 0 . Prove both directions: that all words in L are accepted, and that anything that is accepted is in L. The alphabet Σ = 0, 1 . One way to prove is that L is accepted and L is rejected. If you go that way you may use without proof the fact that L = s w Σ*: n1(w) > 0 and that δ*(q2, x) = q2 without proof.

Question 4. Prove that no DFA with three states can accept the language L = {0ⁱ : i > 0}∪ iⁱ : i > 0 is insufficient to simply show a X-state machine (for some X > 3) that is claimed to accept the language. You may apply any construction or algorithm we've covered in class and refer to its proof of correctness as part of this question. Clearly state the construction you are using and show the input and the output. You may also use the machine you provide in the previous question for {0ⁱ : i > 0} and without loss of generality {iⁱ : i > 0} without reproving that it accepts the language

Question 5. Let M = (Q, Σ, δ, q0, A) be an s-NFA and let S Q. Prove that ∈(S) = ∈(∈(S)).