Select all the statements below which are TRUE: Let sigma = {a, b, c}. If M is a

Question

Select all the statements below which are TRUE: Let sigma = {a, b, c}. If M is a dfa then each state q in M must have an outgoing edge for each symbol a, b, c, d. Dfa's and nfa's are equally powerful: (1) any dfa is also a nfa, and (2) any nfa has an equivalent dfa. Let sigma = {a, b, c}. Then abbbca elementof sigma*. Let w be a string and let M be a nfa. If there exists a sequence of moves for w starting from q_0 that put M in a non-final state, then w is rejected. Let G = {V, T, S, P) be a grammar. Then we can have V = {S, A, B} and T = {a, b, A}. Let sigma = {a, b, c}, L_1 = {a, ba} and L_2 = {ba, c, aa}. Then |2^L_1| lessthanorequalto |L_1 L_2|

Explanation / Answer

From the given question, following are the true statements.

Dfa's and Nfa's are equally powerful :1)any DFA contains nearly and 2)any Nfa's contains equivalent Dfa

Let sigma=(a, b, c) then abbbca belongs to £*

Let w be a string and M is an Nfa. Then if there exists a sequence of moves for w starting from q0 that put M in non-final state. Then we is rejected.

Let £ = (a, B, c), and l1=(a, ba) and l2=(ba, C, aa),

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.