Consider the language L of odd length strings over the alphabet {a,b,c} such tha
ID: 3786615 • Letter: C
Question
Consider the language L of odd length strings over the alphabet {a,b,c} such that the middle symbol is b. For example, acbca, b, aabca are in L but bb, acb, a 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 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, xyiz is in L, and that |y| > 0 and |xy| <= p. But if we let i = _________, we get a string xyiz that is not in L becuase....
Consider the language L of odd length strings over the alphabet fa, b, c) such that the middle symbol is b. For example, acboa, b, aabca are in L but bb, acb, a 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 ryz such that for any i 20, zysz is in L, and that ly 0 and lzyl S p. we get a string zu 2 that is not in L because But if we let i This is a contradiction. Therefore the assumption is false, and Lis not regular.Explanation / Answer
Choose s to be the string acabaac.
Since 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, xyiz is in L, and that |y| > 0 and |xy| <= p. But if we let i = 2, we get a string xy2z that is not in L becuase the middle element "b" has to be present only once in the output that too at the middle