Welcome! Log In Create A New Profile


Q8 2006

Posted by BlaXpydo 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Q8 2006
May 06, 2011 07:08PM
What examples would you suggest we use for Recursively enumerable languages and Recursive languages?

I'm actually a bit short on knowlege on this part, can't really remember what is what.

Hope you can give some ideas.

Don't be different...be the one making a difference
avatar Re: Q8 2006
May 06, 2011 07:54PM
r.e. Input goes to one of three: Accept(T), Loop(T), Reject(T)

The thing to remember there is Loop.

recursive is almost the same, but there's no loop.

So you need a language that loops forever on something for an r.e. (as well as being able to show the other two exhaust all the possibilities).

And with the recursive you must have one that can't loop eternally.

Is that enough to get you started?

Before you even think about that, I suppose the first thing to do is see if I'm talking nonsense again, eh? I seem to have gotten every question I look at back to front.

Just a thought. If you've done some question involving building a TM, you'll know how it behaves, right? So that would be one of your examples. If it has some eternal loop (like the perfectly good ba ba machine I was so puzzled about) then it's an example of an r.e. language.

Another thought. r.e. is the outermost circle of the Venn diagram, isn't it? (Better check that)

If it is, then you can take any language inside it, and you're r.e. Take some regular language, for instance.

Again, you might have examples lying around in the questions you've already answered.

In fact you probably just need an example of a recursive language? What do you think?
Re: Q8 2006
May 06, 2011 08:21PM
thanks eddy, you make it seem quite interesting, but perhaps a nice clean example will help make the link in my brain. What says you to that?

Don't be different...be the one making a difference
avatar Re: Q8 2006
May 06, 2011 10:44PM
Well for recursive you can't do much better than the example Cohen gives.

S ---- (a, a, R) ----> Halt

If your specification of L is simply that its words must start with a, how would you ever loop? I think that lack of a loop is intrinsic to a recursive language: That is to say you can stand on your head and whistle Dixie all day (what a magistrate I knew well used to love to tell an accused before whatever he had to say) and you still will not be able to loop.

I think so. I need to read a bit more to convince myself that this is so.
Re: Q8 2006
May 09, 2011 08:47PM
Thanks for that Eddy

And now a example for a R.E winking smiley
avatar Re: Q8 2006
May 09, 2011 09:29PM
Just put an infinite loop in that? (b, b, L) back to the start state. Same as in the other question. Because you've gone L on the tape you now know you're back on the initial a, which will take you R to b, which will take you L to a ...

"Words that start on a, but don't have b as their second letter" are now what is accepted.

Words that start on b crash, so we do have some crashes/ Reject(T). Everything you could ever want in a r.e. language. smile
Sorry, only registered users may post in this forum.

Click here to login