Consider two instances X and Y of the Post Correspondence Problem, each with lists A and B of three strings over {0, 1}. Which of the following is true?
X
| i | List A | List B |
|---|---|---|
| 1 | 1 | 111 |
| 2 | 10111 | 10 |
| 3 | 10 | 0 |
Y
| i | List A | List B |
|---|---|---|
| 1 | 10 | 101 |
| 2 | 011 | 11 |
| 3 | 101 | 011 |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. Only PCP in X has a solution
Explanation
X: the sequence 2, 1, 1, 3 gives 10111·1·1·10 = 10·111·111·0 = 101111110. Y: every pair must start with pair 1 (10/101), and the B string then stays one symbol ahead with no way to close the gap, so Y has no solution.More Theory of Computation and Compilers questions
- Consider the following properties of recursively enumerable sets: (A) Finiteness (B) Context-freedom (C) Emptiness Which of the following i…
- Consider the grammar S → SbS | a and the string abababa. Consider the statements: the string has (A) two parse trees (B) two leftmost deriv…
- Match List I with List II. Choose the correct answer from the options given below:List I List II A. Type 0 I. Finite automata B. Type 1 II.…
- Consider the following statements: Statement I: An LALR parser is more powerful than a canonical LR parser. Statement II: An SLR parser is…
- Consider the following statements about context-free languages (CFL): Statement I: CFLs are closed under homomorphism. Statement II: CFLs a…
- Match List – I with List – II. List – I (Propositions) (A) P ∧ (P → Q) (B) ¬(P ∨ Q) → (P ∧ Q) (C) P → Q (D) P ∨ (Q ∧ R) List – II (Disjunct…