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.