First Semester Students

Yes that sounds right to me.

Nice and abstracted from the details, too. (I suppose all these theorems we're given were meant to be useful in the end).

... as long as we don't build a machine like mine or like the one in the solution it should all be fine.

Some feedback from the lecturer on this one:

There is nothing wrong with Q4 FA. Remember that the FA should accept words which have odd number of a’s OR even number of b’s. Which means aa has 0 number of b and 0 is even. As you can see NULL string is also accepted because it has 0 b’s.

Well then I take back whatever it was that I took back ...

The NULL string would also have an even number of a's for that matter, come to think of it.

I hate these even = 0 = even stuff.. it can only spell disaster during an exam. This is the kind of stuff I tend to overlook in a rush...

Hi there

In tut letter 105 there is a past paper, the pumping lemma question, how do we solve tht problem because the first b in the language is to the power one. Can we let vxy consist of b only and den pump uvvxyyz and say that there's a contradiction because b occurs twice?

@Tazz, there's another thread on this. I think it's under the relevant question number.

Let's see if I get somewhere. (Got lost badly on this at last attempt).

Words that are long enough pump IF the language is generated by some CF Grammar.

"Long enough" is "p letters long", I think. That's with the grammar having p live productions.

The question wants you to use the pumping lemma with length and gives it to you. There's extra info there. The middle section of the word is more than 2^p letters long. That means you can take a word whose next pump (whatever that is) has to be "only of so and of so" or "all of a" etc. You can find yourself a word that doesn't have too many cases to consider.

If you find that regardless of how you split that word up (and I don't think there's a way to escape covering several cases), you never get uv²xy²z (whichever way you rearrange the word to define these), then your language cannot be a CFL. You use the pumping lemma to prove a negative.

Now as far as your b goes, I think it might help to think of it as a very convenient separator.

Imagine trying to pump a v that has aabaa for instance. If you do that twice what do you get? aabaa.aabaa, right? But now your word is of the wrong form. It can't pump that way, so v can't be that group. Work out for yourself how vxy has to be in order to stand some chance of pumping, and maybe take it from there.

OK I'm off to work on tomorrow's exam. I'll have to come and edit this waffle into something more precise tomorrow afternoon.

please forward me tutorial 101 to ishongwe@yahoo.com