Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}; C = {00, 001, 1000} and D = {0, 11, 011}. Which pairs have a Post correspondence solution?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. Only pair (C, D)
Explanation
A PCP instance has a solution if some sequence of indices makes the concatenated top and bottom strings equal. Following the official key, only (C, D) has one.
More Theory of Computation and Compilers questions
- Which data structure is used by the compiler for managing variables and their attributes?
- On translating the expression given below into quadruple representation, how many operations are required? (i*j)+(e+f)*(a*b+c)
- Replacing the expression by 8.56 is known as
- Shift-reduce parser consists of (a) input buffer (b) stack (c) parse table
- How many states are there in a minimum state automata equivalent to regular expression given below? a * b(a + b) Regular expression is
- Match List I with List II, where L1 is regular, L2 context-free, L3 recursive and L4 recursively enumerable. List I: (a) complement(L3) ∪ L…