It is possible to build a Post machine that recognizes the language:

$\displaystyle {a^{n+1} b^n | n >= 0 }$

??

Printable View

- Nov 6th 2010, 03:43 PMApprentice123Post Machine
It is possible to build a Post machine that recognizes the language:

$\displaystyle {a^{n+1} b^n | n >= 0 }$

?? - Nov 7th 2010, 11:44 AMemakarov
I used to have a brochure "Post Machines", but I never learned the difference between Post and Turing machines. However, according to Wikipedia, they are equivalent. Since the language you've given is Turing-decidable (more precisely, context-free), the answer to your question is yes.

Edit: This probably feels like an insult if you were actually asking for help in constructing the machine... See joke #19 here. - Nov 8th 2010, 02:53 PMApprentice123