Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
You do by adding yes/no states that indicate whether the string is accepted or not. – Hendrik Jan Dec 1 '12 at 0:47
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. – Luke Mathieson Dec 1 '12 at 1:00
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.) – Raphael Dec 1 '12 at 14:01
I've edited the question to make it more clear, any help is appreciated – user3115 Dec 2 '12 at 19:20
up vote 1 down vote accepted

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"!

share|cite|improve this answer
thanks for the help. I see what your saying now – user3115 Dec 4 '12 at 0:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.