Consider the language L = {tu | t and u are strings over {0,1} with the same num
ID: 3787475 • Letter: C
Question
Consider the language L = {tu | t and u are strings over {0,1} with the same number of 1's}. Explain and correct the error below:
Proof that L is not regular using the pumping lemma:
Assume (towards a contradiction) that L is regular. Then the pumping lemma applies to L. Let p be the pumping length of L. Choose s to be the string 1^p0^p1^p0^p, which is in L because t = 1^p0^p and u = 1^p0^p each have p 1's.
Since this string is in L and has length greater than or equal to p, the pumping lemma gurantees s can be divded into parts s = xyz such that for any i >= 0, xy^iz is in L, and that |y| > 0 and |xy| <= p. Since the first p characters of s are all 1's and we have |y| > 0 and |xy| <= p, we know that y must be nonempty and made up of all 1's. But if we let i =2, we get a string xy^iz that is not in L because repeating y twice adds 1's to t but not to u, and strings in L are required to have the same number of 1's in t as in u.
This is a contradiction. Therefore the assumption is false, and L is not regular.
Consider the language L {tu t and u are strings over 10,1) with the same number of 1's Explain and correct the error below: Proof that L is not regular using the Pumping Lemma: Assume (towards a contradiction) that Lis regular. Then the Pumping Lemma applies to L. Let p be the pumping length of L. Choose s to be the string 1POP1POP, which is in L because 1POP and u 1POP each have p 1's. Since this string is in Land has length greater than or equal to p, the Pumping Lemma guarantees s can be divided into parts s ayz such that for any i 20, ay iz is in L, and that ly 0 and layl s p. Since the first p characters of s are all 1's and we have ly 0 and Iryl S p, we know that y must be nonempty and made up of all 1's. But if we let i 2, we get a string ryiz that is not in L because repeating y twice adds 1's to t but not to u, and strings in L are required to have the same number of 1's in t as in u. This is a contradiction. Therefore the assumption is false, and Lis not regular.Explanation / Answer
Given L={tu | where t and u are strings which are made up of equal no. of 1's}
To prove: L is not regular.
Assume: L to be a regular language.
Therefore, pumping lemma applies to L, that is if p is the pumping length of L then we can pump this p to get a string which belongs to the language only.
Say, s is string which belongs to the language such that
s = xyz
for any i>=0 where xyiz belongs to L.
and |xy|<=p and |y|>0.
Now since length of xy should be at most p characters, and we should have atleast p 1's
=> There are p 1's in the starting, followed up by the rest of the string covered in z.
For example, consider the string s = 111000111000.
Here, xy = 111
z=000111000
and the string satisfies s = xy1z and also belongs to L.
But pumping this i from 1 to 2 will result in:
s = xy2z , i.e., 111111000111000
only the starting ones get pumped; not the ones which come in z part.
Hence xy2z doesnt belong to L.
And its a contradiction to our assumption that L is a regular language.
Hence, L is not a regular language.