True or False: a)if a DFA M has n states, then L(M) has a string of length at le

Question

True or False:
a)if a DFA M has n states, then L(M) has a string of length at least n.
b)If a DFA M has n states, and L(M) has a string of length at least n, then L(M) has a string of at least 100n.
c)Let L = {a^nb^nc^n|n>=0} U {a,b,c}. L* is context free.

Explanation / Answer

a) false if there is no loop we can have atmost n-1 transitions from start to final state. b) true there must be loop present to have string of length n c) false L = {a^n b^n c^n: n>=0} is not context free. Here P.L is pumping lemma Proof. Assume L is context free. Then L satisfies P.L. Then there exists n by the P.L. s.t. ... Let z = a^n b^n c^n Because |z|>=n and z in L, by PL there exist uvwxy s.t. ... But if there exist u,v,w,x,y satisfying first three constraints, we can show there exists i s.t. the fourth constraint fails. Case uvw consists only of "a". Then when i=0 string is not in L (fewer "a"s than "b"s or "c"s). Case vwx contains only "b"s - similar. Case vwx contains only "c"s - similar. Case vwx contains only two types of characters from {a,b,c}. Then uwy has more of the remaining type of characters. The string vw cannot contain "a"s, "b"s, and "c"s, since vwx is a substring of z and has length

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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