Post Machines

Post Machines

A Post machine (PM) is a theoretical model of computation created by Emil Leon Post in 1936. It is designed to process strings of symbols and is more powerful than finite automata (FA) and pushdown automata (PDA). Post machines can accept languages that are not context-free, making them an important concept in theoretical computer science.

Components of a Post Machine

A Post machine consists of five main components:

1. Alphabet: The alphabet I of input letters plus a special symbol #. For example, we can define I = { a, b }.
2. Store: A linear storage location called the STORE or QUEUE, which initially contains the input string. The STORE allows for reading the leftmost character and adding new characters to the right end.
3. READ states: States that remove the leftmost character from the STORE and branch according to the character read. Each READ state can have different branches for each character in I or the STORE alphabet.
4. ADD states: States that concatenate a character onto the right end of the STORE. Unlike PDA PUSH states, ADD states do not allow branching.
5. Start and Halt states: A START state (which cannot be entered) and some halt states called ACCEPT and REJECT. If a READ state encounters an unlabelled edge, the machine crashes, leading to a REJECT state.

How a Post Machine Works

When a Post machine processes an input string, it starts in the START state. It reads characters from the STORE, transitions between READ and ADD states, and ultimately reaches either an ACCEPT or REJECT state based on the input string.

Example of a Post Machine

Consider a Post machine designed to accept the language of strings of the form aⁿbⁿ, where n ≥ 0. The machine can be represented as follows:

START -> ADD a -> ADD b -> ACCEPT

This machine processes the input string aaabbb as follows:

1. Initially, the STORE contains the string aaabbb.
2. In the START state, the machine transitions to the ADD state, appending characters to the right.
3. The machine reads the first character 'a', appending it to the STORE.
4. It continues to read and append 'a's until it reaches 'b's.
5. Once all 'a's are processed, it reads 'b's and appends them as well.
6. Finally, the machine reaches the ACCEPT state if the number of 'a's matches the number of 'b's.

Common Mistakes

Simulating a Post Machine on a Turing Machine

Any language that can be accepted by a Post machine can also be accepted by a Turing machine (TM). This is shown through a constructive algorithm that converts a PM into a TM. The conversion involves the following steps:

1. The START state of the PM remains unchanged in the TM.
2. The ACCEPT state of the PM is renamed HALT in the TM.
3. REJECT states are removed, as TMs crash if no path can be found.
4. The STORE of the PM is converted into the TAPE of the TM.

For example, if the STORE contains the string X1X2X3X4X5, the corresponding TM TAPE will keep track of this string. The TM will perform operations that mimic the behavior of the PM, ensuring that the processing is equivalent.

Conclusion

Post machines are a powerful model of computation that can accept both context-free and non-context-free languages. Understanding their operation and how they relate to other computational models, such as Turing machines, is crucial in theoretical computer science.

Check your understanding

• What are the five components of a Post machine?
• Explain the difference between READ and ADD states in a Post machine.
• How can a Post machine be simulated using a Turing machine?
• What language does the example Post machine accept?