0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

This language $a^nb^n$ can be recognized by a one counter automaton, i.e. a pushdown automaton with only one kind of stack symbol (other than the stack bottom).

That can be easily mimicked by a Post machine (with capital P, like Turing), according to the Wikipedia definition.

So first try to design the PDA with a single stack symbol (that is easy), and then translate it to a Post machine.

But I am not sure you are using the same type of Post machine as described in Wikipedia, and you did not describe your model.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Given the description of the steps in your Post machine, and assuming that step 6 connects to step 1, then you have the correct algorithm.

Your machine will accept only the language $a^n b^n$ and it will not accept $abab$ or any other word not of the form $a^n b^n$.

Given the example $abab$, the machine will crash/reject at step 5 after it reads the second $a$ in $abab$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.