Ch4 exercises

Re: Ch4 exercises

by Giorgio Satta -
Number of replies: 0

Dear Ashraf, I think solutions to this problem using the pumping lemma *directly* are possible,  but very difficult for the average ALC student. For instance, strings of the form a^n b^n are in the language, and if you iterate y in the left part for k times you still get a string in the language, so the lemma is satisfied.  

But I need to add that after the lecture,  a couple of students approached me with a p. lemma solution which was correct, although quite involved.