# Q8 2006

Posted by BlaXpydo
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Q8 2006 May 06, 2011 07:08PM Registered: 9 years ago Posts: 269 Rating: 0
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
 Re: Q8 2006 May 06, 2011 07:54PM Registered: 10 years ago Posts: 3,496 Rating: 1
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 Registered: 9 years ago Posts: 269 Rating: 0
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
 Re: Q8 2006 May 06, 2011 10:44PM Registered: 10 years ago Posts: 3,496 Rating: 1
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 Registered: 12 years ago Posts: 67 Rating: 0
Thanks for that Eddy

And now a example for a R.E
 Re: Q8 2006 May 09, 2011 09:29PM Registered: 10 years ago Posts: 3,496 Rating: 1
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.
Sorry, only registered users may post in this forum.