Post machines or tag machines:

The Post machine (Emil L. Post, 1897-1954) or tag machine is a FSM with single tape of unbounded length with FIFO access (that is, first-in first-out, as opposed to LIFO access of the stack). In a single transition, M reads and removes the symbol at the head of FIFO queue and might append symbols to the tail of queue. Technical detail: there is special symbol #, not part of alphabet A of the input string, on average employed as a delimiter.

Perhaps unexpectedly, Post machines are universal, that is, equivalent in computational power to TMs.

We utilize the given conventions in order to simplify the illustrations that follow. A = {0, 1} is the alphabet of language to be accepted, or the functions f: A* -> A* to be computed. We introduce additional marker symbols which might be helpful. We permit the FSM controller to inspect not just the symbol at the head of queue, however any prefix of constant length. This generalization very much simplifies the programming task. In order for PMs to be deterministic, we insist on prefix property: for any state q, and any two outgoing transitions q, x -> ..., and q, y -> ..., with x, y ∈ A*, x is not a prefix of y. The ability to examine a prefix of fixed length can be removed at the cost of introducing additional states, one for each symbol of prefix beneath inspection. The illustrations describe a general procedure for decreasing a PM which observes a string at the head of queue to the other PM which only observes the single symbol.

Transition is of the form: qi, x -> qj, y with x, y ∈ A*.  For x or y = ε we might omit ε. Example: qi, x -> qj cuts x from the head devoid of appending anything to tail, and qi  -> qj, y appends y to the tail regardless of the state of head of the queue. There are two special kinds of transition, halting and test for empty queue. We write them as: qi, x -> y, Halt and qi, Empty -> qj, y. Notice: qi, Empty applies to the net state of queue, while qi, ε -> refers to the prefix ε of queue that is always present and avoided.

Illustration: Translate an alphabetic source text to Morse code in the single left-to-right scan.

Samuel Morse (1791-1872) explained the ability of a telegraph system to transmit the information over wires.

Alphabet A = {_ , a, b, c, .. , z, •, -, /}. Sample Morse codes: a: • -;    b: - • • •, ... as illustrated in this code tree:

The Morse code lacks helpful properties that make decoding simple, like the prefix property (no code word is a prefix of any other). Rather, it relies on a pause of adequate length to point out the end of a letter; we employ _ to point out this pause. We use / as a word separator in source text and translate it to - • • - • in Morse code. The single-state PM whose transition from q to q is labeled by the whole dictionary as given in the code tree above will convert any text into Morse code. Example: the transitions: q, S -> q, • • •_ and q, O  -> q, ---_ , all along with q, # -> #, Halt   converts the input  ‘SOS#’  into  ‘• • •_  ---_• • •_ #’ .

Illustration: Parsing the context-free language of suffix expressions

The given CFG produces the language of Boolean suffix expressions which include the operator’s ¬∧∨, and a single operand symbol, o: Ε −> ο | Ε¬ | ΕΕ∧ | ΕΕ∨.

The single-state PM, whose transitions are ‘reverse productions’, parses any suffix expression (that is, terminated by the special symbol #) employing repeated scans till the expression is decreased to the single symbol E, and string to E#.

Call this procedure ‘reduces or rotates’: When the sub-expression currently at the head of queue can be decreased (parsed), do so; if not, rotate the symbol at the head of queue to the tail. Ultimately, it will make its way back to the head and get other chance to be decreased. The transitions from q to q are of four kinds:

Parsing: ο −> Ε,   Ε¬ −> Ε,   ΕΕ∧ −> Ε,   ΕΕ∨ −> Ε,

Rotating characters which can’t [currently] be parsed:  ‘any other’ -> ‘any other’

Successful recognition of [a part of] the input as an illustration of E: E# -> ε

Test whether the whole input string has been processed: q, Empty -> Halt

E# -> ε is the ultimate transition of parsing phase, whose aim is to convert a syntactically accurate string to ε. The halting transition q, Empty -> Halt terminates the parsing of syntactically accurate inputs, while wrong inputs cause the machine to loop. This fair weather parser works fine on syntactically accurate inputs, as shown by the given execution trace on the initial string ο ¬ ο ∧ #:

The single state suffices for FSM controller as this PM inspects the prefixes of length > 1. The following PM which inspects merely the single symbol at the head of queue does similar job. Its state labeled EE recalls that the string EE has been cut off from the head of queue and the PM awaits the subsequent symbol to decide what to do regarding this incomplete substring EE. Three cases should be differentiated:

A) ∧ or ∨ complete a sub expression E E ∧ or E E ∨, correspondingly that is parsed to an E;

B) Yet another E makes a substring E E E (as in E E E ∧, for illustration) of which the first E can’t be processed now, and therefore is rotated to the end of queue for later re-consideration. However the two most recent Es may be expanded to E E ∧, for illustration, and this describes the self-loop E -> E.

C) The transition labeled ‘any -> x any’ out of state q applies to any symbol not explicitly joined to a transition out of this similar state q. The symbol represented by ‘any’ is cut off as usual and the string ‘x any’ is appended to the tail of queue, where this second ‘any’ represents the symbol cut off. This transition effects the delayed rotation of the substring x, that had been accumulated in PM’s state space to be appended later.

The Post machine which differentiates accurate inputs from wrong inputs and always halts should break the endless loop whenever no progress takes place throughout a complete rotation of the queue content, from one occurrence of # at the head of queue to the next. The given two-state machine keeps track of any change which takes place, triggered by a transition of the kind ‘reverse production’ to the state labeled ‘content has modified. When no such change takes place throughout a complete rotation, the next appearance of # at the head of queue breaks the loop. The ‘E’ in a pair of consecutive symbols ‘E#’ can never be eliminated by any reverse production; therefore it is the root of a parse tree for the suffix expression. Whenever the queue comprises of just E#, then the whole input must have been an illustration of E. When, on the other hand, the queue includes other symbols besides E#, then the original input contained extraneous symbols which can’t be a part of suffix expression. Therefore, after eliminating E#, a test whether the queue is empty or not decodes syntactic accuracy.

Illustration: Duplicating a string

The two preceding tasks are simple as they are naturally understood as including left-to-right scans. Most of the string processing operations are intuitively understood by moving the read or write head either left or right, as a Turing machine does, wherever the subsequent task occurs to be. In PM, any desired sequence of moves should be resolved in terms of left-to-right scans, identical to the way a Markov algorithm processes its data.

Consider the task of copying or duplicating a string, example: 011. When we wanted to turn it to 001111, the single scan translation employed for Morse coding does the job. However we want to produce 011 011.

Initial string: # ! 0 1 1 # ! (# separates the two bit strings! Marks the place where things occur)

Intermediate: # 0 ! 1 1 # 0 ! (Invariant: the bit string to the left of! Has already been copied)

Final string: 0 1 1 ! # 0 1 1 ! # (There is nothing left to do to right of!)

We omit a clean-up phase to eliminate “!”

Execution trace on the initial string # ! 0 1 1 # !  (The consecutive rotations are compressed to one):

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.