Post Correspondence Problem & Linear Bounded Automata | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Part X. Post Correspondence Problem

13 Post Correspondence Problem
Post correspondence problem (PCP) is a problem formulated by E. Post in 1940.
Let us illustrate this problem by an example:

Example 1:
Let there be two series of strings, say x series and y series as shown below:

Both X series and Y series contains 5 strings.
Let us call the strings in X series as X substrings, and
the strings in Y series as Y substrings.
If we concatenate X substrings x₁x₅x₂x₃x₄x₄x₃x₄, we get 1010101001000100.
If we concatenate Y substrings y₁y₅y₂y₃y₄y₄y₃y₄, we get 1010101001000100.
Let us call these strings as x string and y string.
It can be seen that x string and y string are same.
Here we say that this instance of PCP has a solution in the form 15234434.

If we take 23,
x string is, x₂x₃ =010
y string is, y₂y₃ =10010.
Here x string and ys tring are different. Hence 23 is not a solution to this instance of PCP.

Example 2:
Find the solution to the instance of PCP given in the following table.

Solution,
x₂x₁x₁x₃= 010000001
y₂y₁y₁y₃= 010000001
Hence, 2113 is a solution to this instance of PCP.

Example 3:
Find why the instance of PCP given below cannot have a solution.

It can be seen that for every pair, |x_i| > |y_i|.
So, in whatever way we concatenate the string, the length of the x string will be longer than the corresponding y string. Thsu there is no solution for this instance of PCP.

Definition of PCP
Let there be two series, x series and y series of size n with same charactere set ∑ with their ith element as x_i and y_i,respectively; does there exist a solution tha tforms the same x series and y series?
The generic solution of PCP can be written as,
x_i1 x_i2 x_i3........x_ik = y_i1y_i2y_i3.......y_ik

Post Correspondence Problem is unsolvable.
This means it is a non computable function. No turing machine exists for PCP.
The proof of this is beyond the scope of our study.

Use of PCP
Other problems can be reduced to PCP and we can declare them as unsolvable or undecidable.

Part XI. Linear Bounded Automata

Consider the following figure:

We learned in Chomsky classification that context sensitive languages (Type-1) are produced from context sensitive grammars.
Context sensitive languages are recognised using linear bounded automata.

The following is an example for a Context Sensitive grammar:
S → aBCT|aBC
T → ABCT|ABC
BA → AB
CA → AC
CB → BC
aA → aa
aB → ab
bB → bb
bC → bc
cC → cc
in this grammar, LHS of a production is not longer than the RHS.
The language, L = {aⁿbⁿcⁿ|n > 0} is a context sensitive language.

14 Linear Bounded Automata (LBA)
Context sensitive languages are recognised using linear bounded automata (LBA).
Here input tape is restricted in size. A linear function is used for restricting the length of the input tape.
Many compiler languages lie between context sensitive and context free languages.
A linear bounded automation is a non deterministic Turing machine which has a single tape whose length is not infinite
but bounded by a linear function.

Formal Definition
A linear bounded automation is defined as,
M = (Q,∑, Γ, δ, q₀, #, <,>,F),
where
Q is a set of states,
∑ is a set of input symbols,
Γ is a set of tape symbols, including #,
δ is the set of transition functions from
(Q × Γ) → (Q × Γ × {L, R, N}),
q₀ is the start state,
# is the blank symbol,
< is the left end marker in the input tape,
> is the right end marker in the input tape,
F is the final state.
Following diagram shows a linear bounded automation,

When an input string is processed using an LBA, input string is enclosed between < and > end markers. The end marker < prevents the R head from getting off the left end of the tape. The right end marker > prevents the R head from getting off the right end of the tape. On the input tape, head does not write. Also on the input tape, head does not move left. All the computation is to be done between end markers < and >. On the working tape head can read and write without any restriction.
Thus LBA is same as a Turing machine except that head can move only within the end markers.

Example:
Consider an LBA defined as,
Q= {q₀, q₁, q₂, q₃, q₄}
∑= {a, b, c}
Γ= {a, b, c, #}
q₀ = s
δ(q₀, [) = (q₁, [, R)      δ(q₁, ]) = (q_1, ],Y )     δ(q₁, #) = (q₁, #, R)
δ(q₁, a) = (q₂, #, R)    δ(q₂, a) = (q₂, a, R)   δ(q₂, #) = (q₂, #, R)
δ(q₂, b) = (q₃, #, R)    δ(q₃, b) = (q₃, b, R)   δ(q₃, #) = (q₃, #, R)
δ(q₃, c) = (q₄, #, L)     δ(q₄, c) = (q₄, c, L)   δ(q₄, b) = (q₄, b, L)
δ(q₄, a) = (q₄, a, L)    δ(q₄, #) = (q₄, #, L)   δ(q₄, [) = (q₁, [, R)
In the above, the transition δ(q₁, a) = (q₂, #, R) means,
LBA on state q₃, head points to symbol b, remains in state q₃, replaces b with b and head turns towards right by one cell.