Consider the language L of strings over the alaphabet {a,b} such that the number
ID: 3787470 • Letter: C
Question
Consider the language L of strings over the alaphabet {a,b} such that the number of a's minus the number of b's is at least three. For example, abaaa, aaaaaa, aabaababaa are in L but bb, aabbaa, aa are not in L. Fill in the missing parts of the following proof to show that L is not regular.
Proof: 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 _____________.
Since the this string is in L and has length greater than or equal to p, the pumping lemma gurantees s can be divided into parts s = xyz such that for any i >= 0, xy^iz is in L, and that |y| > 0 and |xy| <= p.
But if we let i = ________, we get a string xy^iz that is not in L becuase: ________
Consider the language L of strings over the alphabet ta, b) such that the number of a's minus the number of b's is at least three. For example, abaaa, aaaaaa, aabaababaa are in L but bb, aabbaa, aa are not in L. Fill in the missing parts of the following proof to show that Lis not regular. Proof: 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 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 z is in L, and that ly 0 and layl S p. we get a string zyiz that is not in L because But if we leti This is a contradiction. Therefore the assumption is false, and L is not regular.Explanation / Answer
Proof: 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 s= 0p 1p (in L of length >= P)
Since the this string is in L and has length greater than or equal to p, the pumping lemma gurantees s can be divided into parts s = xyz such that for any i >= 0, xy^iz is in L, and that |y| > 0 and |xy| <= p.
But if we let i = 2 , xy2z than we will have more 0's than 1's, we get a string xy^iz that is not in L becuase: it provide contradictionto the assumption of the pumping lemma and to L being regular.