Question

Question: Consider the problem of determining whether a PDA accepts some string of the form $\mathbf{\left\{}\mathit{w}\mathit{w}\mathbf{\right|}\mathit{w}\mathbf{\in }\left\{0,1\right\}\mathbf{*}\mathbf{\}}$. Use the computation history method to show that this problem is undecidable.

Short answer

Answer

Step-by-step solution

Push down automata.

Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata. Context free grammar is used to generate context free languages. A context free grammar is a formal grammar which is used to generate all the possible patterns of strings in a given formal language. And it is contained number of sets of production rules.

Problem is undecidable

Let be an instance of the PCP. Consider the following context-free grammar, where we've introduced a new terminal symbol element in . The grammar has the following rules:

$$\begin{gathered} S\to X!Y \\ X\to x_{1}X\backslash \mathrm{cent}{t}_1\mid x2X\backslash \mathrm{cent}{t}_2\mid .......x_{n}X\text{'}{t}_n \\ X\text{'}\to x_{1}X\backslash \mathrm{cent}{t}_1\mid x2X\backslash \mathrm{cent}{t}_2\mid ........x_{n}X\text{'}{t}_n|\in \end{gathered}$$

Any grammar, for its$xandy$ corresponding pushdown deterministic automaton that accepts the same language $u=v$as the grammar. So, construct the corresponding pushdown deterministic automaton, and then use the hypothetical algorithm for the problem to determine whether this pushdown deterministic automaton accepts any word of the form language$u=v$ (i.e., whether one can derive any word of the form languagefrom this grammar). And also to use this information to solve the PCP instance.

Assume now that$u=v$ is a word in this grammar. The word u has two parts, the suffix, consisting of the terminals, and the remainder called prefix. The same is true of vv. We have if and only if their prefixes and suffixes coincide. The suffixes coincide only if we have used the same sequence of tuples from to build the words u and v. The prefixes of u and vand coincide if the concatenation of the (based on the reversed tuple-sequence) is the same.

Hence if and only if there is a solution for the PCP instance.

Similarly, if there is a solution for the PCP instance,

Then from the solution it is easy to construct a word of the form that is derivable from this grammar.

It follows that the PCP instance has a solution if and only if this grammar contains a word of the form .

If there was an algorithm to decidable problem, it could use it to solve PCP. But of course PCP is known to be undecidable, so this problem is also undecidable.