Waiting for answer This question has not been answered yet. You can hire a professional tutor to get the answer.

QUESTION

prove that the language L = {a^n b^m c^(m+n)|n,m gt;= 0} is not regular using the pumping lemma,by the following format,thank you so much: Step 1:...

prove that the language L = {a^n b^m c^(m+n)|n,m >= 0} is not regular using the pumping lemma,by the following format,thank you so much: Step 1: By way of contradiction, suppose L is regular.Step 2: Let n be as in the pumping lemma.Step 3: Let x = ((101)^(n+1))(1^n)Then x∈L [definition of L]and |x| = 4n+3 >= nStep 4: By pumping lemma, there are strings u, v, w such that,(i) x = uvw(ii) v != ε(iii) |uv| <= n(iv) u(v^k)w∈L for all k∈N By our choice of x, (101)^(n+1) is a prefix of x.Combining with (i), (101)^(n+1) is a prefix of uvw.Combining with (iii), uv = (101)^j for some j∈N with 0<=j<=nCombining with (ii), v = (101)^j for some j∈N with 0<j<=nBy (iv), u(v^2)w∈L (#)However u(v^2)w = uvvw= (101)^(n+1+j) (1^n)∉ L, [definition of L; since j>0, n+1+j ≠ n+1]Which contradicts to (#)Hence, L is not regular.

That one is from the question:Prove that the language L= {((101)^(k+1))((1)^k)|k>=0} is not regular by Pumping Lemma. And here is TA's comments:Don't use the same j for uv and v because you are using it later. Also I am not convinced why v=(101)^j, this may not be true.

Show more
LEARN MORE EFFECTIVELY AND GET BETTER GRADES!
Ask a Question