[Solved]: How to make a Post Machine for $a^nb^n$?

Problem Detail: 

I have tried to make a Post machine for that all words of the form $a^nb^n$ by the following steps.

1. add a marker '#'
2. read first 'a'
3. read next 'a's and add them
4. read first 'b'
5. read next 'b's and add them
6. read '#' (that we added in the first step)

repeat steps while input tape is not empty

but this algorithm also accepts words of the form $(ab)^n$ e.g abab, ababab I want to make a Post machine that only accepts words of the form $a^nb^n$ How to do that?

Asked By : user4129542

Answered By : n.Perception

Hint. One possible solution is checking the format of the input in the beginning of the procedure to get sure the user input is in form of $a^nb^n$. If it is in correct format then go to next step otherwise reject. In next step using the instructions that you've written can accept the language. But one thing which is important in post-turing machines is it's model (eg. Davis), which you didn't mention.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37092

3.2K people like this

 Download Related Notes/Documents