I have devised the following TM for the language EQUAL.

EQUAL accepts all strings with the same number of a's and b's. It is context free but non regular.

Using the TM I devised, how can I show that EQUAL is recursive? How can I show that it crashes when the input is not in EQUAL.

enter image description here

  • 1
    $\begingroup$ You do by adding yes/no states that indicate whether the string is accepted or not. $\endgroup$ – Hendrik Jan Dec 1 '12 at 0:47
  • 1
    $\begingroup$ If you're not restricted (for the purposes of an exercise for example) to TMs, you can also easily do it with a PDA or CFG, and all context-free languages are recursive. Then simply recognising the language (rather than deciding) is good enough. $\endgroup$ – Luke Mathieson Dec 1 '12 at 1:00
  • 1
    $\begingroup$ You say you know it's CFG; since CFG is a subset of the set of recursive languages, what is it you want? (Is EQUAL the language or the TM? You seem to use if for both.) $\endgroup$ – Raphael Dec 1 '12 at 14:01
  • $\begingroup$ I've edited the question to make it more clear, any help is appreciated $\endgroup$ – user3115 Dec 2 '12 at 19:20

A language is recursive if a Turing Machine decides it: On input w, the TM always halts, and accepts if w is in the language, and rejects if w is not in the language.

So to show that the language is recursive, you just need to show that your Turing Machine gives the correct answer on every input string (accepts if # of a's equals # of b's, rejects otherwise). That will also show that it halts on all inputs, so you're done.

As Hendrik says in the comment, a Turing Machine should have both an accept state and a reject state. (That's what it means to accept/reject -- to enter the appropriate state.)

So first, you'll need to make this change.

Then, to prove your construction correct, you use the following type of proof. First, suppose I have a string $w$ that does have an equal number of a's and b's. Then I will show that, when I feed $w$ into my TM, it halts in the accept state. Second, suppose I have a string $x$ that does not have an equal number of a's and b's. Then I will show that, when I feed $x$ into my TM, it halts in the reject state.

You should convince yourself that this proof accomplishes what I said is required above!

But note your TM is not quite there yet: Consider what will happen on input string "bbb"!

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy