2006 Q7

Hi

Here is my answer for Question 7. It feels to short for 7 marks, but I do believe it is correct.

The TM will only accept a langauge of one or multiple a(s) followed by one b, thus a⁺b
The TM will loop on any a langauge of one or multiple a(s) followed by one b and then one or multiple a(s), thus a⁺ba⁺b^*

I suppose to get full marks you might have to point out why it behaves so.

So for instance "There's no b edge ... " ... oops ... I'm talking FA-taal there. OK in FA-sprache one would say "There is no b edge leaving the START state, so the machine will crash on any word beginning with a b"....

... and so on...

Reckon that might do it?

OK and then there's the question of whether I agree with your evaluation of the language.

I think the number of a's must be even?

And I see multiple b's ba ba ba ? But going back from b is (a, a, L). Two b's on the end goes to halt.

OK. But if an a is found after the first b, you rewind ..

Doesn't that crash?

Why do you say it needs to be a double b? Somebody in my Unisa said the same thing. But I had a look at the TM again and the shortest word is ab:

From Start go to State 1: a
From State 1 go to State 2 : b
From State 2 go to Halt: (Delta)

As seen in the diagram below:



Also the question ask only about Accept() and Loop() so I did not concern myself with *kaboom'*s (crashes)

So a more correct answer will be:

The TM will only accept a langauge of one or multiple a(s) followed by one b, thus a⁺b
The TM will loop on any a langauge of one or multiple a(s) followed by one b and then one or multiple a(s), thus a⁺ba⁺(a+b)^*.

Your first loop between Start and State 1 only accepts an odd number of a's. So I was wrong about that one. If you get an even number you're back to where you started from. Try aab, for instance. Follow that with aaab.

That odd number of a's must be followed by a single b, as you rightly point out.

====

OK and then there was loop.

After the b, you can reverse if you find an a instead of the delta that takes you to halt. You'll see this one had me a bit confused back there.

so we've got a tape sort of like this aaaaaba
so T tells us to go L. aaaaaba
so we land on that b again, which will be followed by the a on this tape (because we're overwriting b with b and a with a at this point). We're in a loop.

And after that a, what would there be on the Tape?

aaaaabajinglebellsjinglebellsjinglealltheway ... absolutely anything...

Well not absolutely because sigma = {a,b}

If you reach the a after the b, you're stuck forever. So loop a would be for any word starting with ....

Maybe that's the way to do it? Rough work is a piece of the tape, which you execute the moves on, so as to see what's going on? Certainly I've only really gotten this by actually "drawing that tape" for myself. I was stuck before that, as you can easily see.

So I suppose I owe you some thanks for forcing me to find enlightenment.