Prove {0i 1i| i ≥ 0} is not regular

Let L = {0i1i| i≥0}.

Let n be any integer ≥0. Let x = 0n 1n.

Be certain that x is in L and |x|≥n.

The only possible way to chop x into u, v, and w such that vε≠, and |u v|≤n is:

u = 0p, v = 0q, w = 0n-p-q 1n, where 0≤p<n and 0<q≤n

Show that there is k≥0, u vk w is not in L.

u vk w = 0p 0qk 0n-p-q 1n = 0p+qk+(n-p-q) 1n = 0n+q(k-1) 1n

If k≠1, then n+q(k-1)≠n and u vk w is not in L. Next, L is not regular.

Let L = {0i1i| i≥0}.

Let n be any integer ≥ 0, and m= [n/2]. Let x = 0m 1m.

Make sure that x is in L and |x|≥n.

Possible ways to chop x into u, v, and w such that v≠ε, and |u v| ≤ n are:

-    u = 0p, v = 0q, w = 0m-p-q 1m, where 0≤p<m and 0<q≤m

-    u = 0p, v = 0 m-p 1q, w = 1m-q, where 0≤p<m and 0<q≤m

-    u = 0 m 1p, v = 1q, w = 1m-p-q, where 0≤p<m and 0<q≤m

Show that there is k≥0, u vk w is not in L.

-    u=0p, v=0q, w= 0m-p-q 1m, where where 0≤p<m and 0<q≤m

u vk w = 0p 0qk 0m-p-q 1m = 0m+q(k-1)1m is not in L k 1 1.

if k≠1.

-    u=0p, v=0m-p 1q, w=1m-q, where where 0≤p<m and 0<q≤m

u vk w = 0p (0m-p 1q)k 1m-q is not in L if k≠1.

-    u=0m 1p, v=1q, w=1m-p-q, where where 0≤p<m and 0<q≤m

u vk w = 0m 1p 1qk 1m-p-q = 0m 1m+q(k-1) is not in L if

k≠1

Then, L is not regular.

Email based Automata assignment help – homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help – Automata homework help and online tutoring with best qualified and experienced computer science tutor’s help. We cover all topics including Language checked by Pumping lemma in assignment help – homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.