Question: Let L be the language over { a , b } containing all even - length strings where the first and second halves are equal.

Let L be the language over {a,b} containing all even-length strings where the first and second halves are equal. For example, these are all in L: (lambda, AA, BB, AAAA, ABAB, BABA, BBBB, AAAAAA, AABAAB. In a proof that L is not a regular language we assume L is regular with pumping length p and then pick a string that would allow an easy contradiction using the pumping lemma.
What string would you choose?The pumping lemma says that your string can be broken into xyz where y is a non-empty substring of the first p characters of your string and that both xz and xyyz are also in L.
But either xz or xyyz is not in L because why?

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!