Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Notes  >  Theory of Computation  >  Post Correspondence Problem & Linear Bounded Automata

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:
Post Correspondence Problem & Linear Bounded Automata | Theory of Computation - Computer Science Engineering (CSE)
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 x1x5x2x3x4x4x3x4, we get 1010101001000100.
If we concatenate Y substrings y1y5y2y3y4y4y3y4, 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, x2x3 =010
y string is, y2y3 =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.
Post Correspondence Problem & Linear Bounded Automata | Theory of Computation - Computer Science Engineering (CSE)
Solution,
x2x1x1x3= 010000001
y2y1y1y3= 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.
Post Correspondence Problem & Linear Bounded Automata | Theory of Computation - Computer Science Engineering (CSE)
It can be seen that for every pair, |xi| > |yi|.
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 xi and yi,respectively; does there exist a solution tha tforms the same x series and y series?
The generic solution of PCP can be written as,
xi1 xi2 xi3........xik = yi1yi2yi3.......yik

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:
Post Correspondence Problem & Linear Bounded Automata | Theory of Computation - Computer Science Engineering (CSE)
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 = {anbncn|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,∑, Γ, δ, q0, #, <,>,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}),
q0 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,
Post Correspondence Problem & Linear Bounded Automata | Theory of Computation - Computer Science Engineering (CSE)
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= {q0, q1, q2, q3, q4}
∑= {a, b, c}
Γ= {a, b, c, #}
q= s
δ(q0, [) = (q1, [, R)      δ(q1, ]) = (q1, ],Y )     δ(q1, #) = (q1, #, R)
δ(q1, a) = (q2, #, R)    δ(q2, a) = (q2, a, R)   δ(q2, #) = (q2, #, R)
δ(q2, b) = (q3, #, R)    δ(q3, b) = (q3, b, R)   δ(q3, #) = (q3, #, R)
δ(q3, c) = (q4, #, L)     δ(q4, c) = (q4, c, L)   δ(q4, b) = (q4, b, L)
δ(q4, a) = (q4, a, L)    δ(q4, #) = (q4, #, L)   δ(q4, [) = (q1, [, R)
In the above, the transition δ(q1, a) = (q2, #, R) means,
LBA on state q3, head points to symbol b, remains in state q3, replaces b with b and head turns towards right by one cell.

The document Post Correspondence Problem & Linear Bounded Automata | Theory of Computation - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
18 videos|69 docs|44 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on Post Correspondence Problem & Linear Bounded Automata - Theory of Computation - Computer Science Engineering (CSE)

1. What is the Post Correspondence Problem?
Ans. The Post Correspondence Problem is a decision problem in computer science that involves determining whether there exists a sequence of string pairs that can be concatenated in different orders to form two equal strings.
2. What is the significance of the Post Correspondence Problem in computer science?
Ans. The Post Correspondence Problem is known to be undecidable, which means that there is no algorithm that can always give a correct answer for any given input. It is an important problem in theoretical computer science as it helps to understand the limits of computation.
3. How does the Post Correspondence Problem relate to Linear Bounded Automata?
Ans. Linear Bounded Automata (LBA) are a computational model that can solve the Post Correspondence Problem. LBAs are a restricted form of Turing machines where the tape head is not allowed to move beyond the input size. By simulating the behavior of an LBA, the Post Correspondence Problem can be solved.
4. Can the Post Correspondence Problem be solved in polynomial time?
Ans. No, the Post Correspondence Problem is known to be undecidable and cannot be solved in polynomial time. This means that no efficient algorithm can exist to solve the problem for all inputs.
5. What are some practical applications of the Post Correspondence Problem?
Ans. While the Post Correspondence Problem is primarily a theoretical problem, it has applications in areas such as cryptography, language theory, and formal languages. It helps in understanding the limits of computation and can be used to prove the undecidability of other problems. However, it does not have many direct practical applications in real-world scenarios.
18 videos|69 docs|44 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Extra Questions

,

Objective type Questions

,

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

,

past year papers

,

Viva Questions

,

mock tests for examination

,

video lectures

,

Previous Year Questions with Solutions

,

shortcuts and tricks

,

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

,

Important questions

,

Summary

,

ppt

,

practice quizzes

,

Exam

,

pdf

,

study material

,

Sample Paper

,

MCQs

,

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

,

Free

,

Semester Notes

;