Given any strings u and x (with u notequalto), define #u(x) to be the number of

Question

Given any strings u and x (with u notequalto), define #u(x) to be the number of times u occurs as a substring of x. For example, if u = 010 and x = 01010 then #u(x) = 2 because two occurrences are counted even though they overlap. Using the Myhill-Nerode technique (not the Pumping Lemma), prove that two the following languages are not regular and give a regular expression for the one that is regular. L_1 = {x {0, 1}*: #00(x) > #11(s)}. L_2 = {x {0, 1}*: #01(x) > #10(x)}. L_3 = {x0y: #0(x) = #1(y)}.

Explanation / Answer

Consider w1=00011 and w2 = 0001. w1 and w2 both belong to L1. but when we concatenate 1 to w1 and w2 then we get w1.1 and w2.1 such that w1.1 does not belong to L1 but w2.1 belongs to L1. So using myhil-nerode theorem L1 is not regular.

Similarly you can generate counterexamples of other two also using concatenation.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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