Question

Let $\mathit{A}\mathbf{=}\mathit{L}\left(G_1\right)$where is defined in Problem 2.55. Show that A is not a DCFL. (Hint: Assume that A is a DCFL and consider its DPDA P . Modify P so that its input alphabet is $\left\{a,b,c\right\}$. When it first enters an accept state, it pretends that c's are b's in the input from that point on. What language would the modified P accept?)

Short answer

A is not a Deterministic Context free language.

Step-by-step solution

Explain DCFL and DPDA 

Deterministic Context Free Languages are accepted by the deterministic pushdown automaton. DCFL is an unambiguous and accept an unambiguous grammar. Deterministic Pushdown Automata is used to recognizes the DCFL.

Show that is A not a DCFL.

Consider that grammar $G_1$,

$$\begin{gathered} R\to S\overline{)T} \\ S\to aSb\overline{)ab} \\ T\to aTbb\overline{)abb} \end{gathered}$$

Consider the contradictory statement, that A is a deterministic context free language. Assume that the pumping length of A is p, such that p length string satisfies the pumping lemma.

Consider the string s=$0^{2p}{0}^p{1}^p{0}^{2p}$, to satisfy the assumption the following ways can be used.

Case 1:

Consider the string ab'cd'e , that has only 0’s. Make the assumption, that i is the number that satisfy the condition,$7p>\overline{)b\overline{)d}}\times \left(i+1\right)\ge 6p$. The length of the string is not equal to the multiple of 3,$\left|s\right|=\left|t\right|=\left|s\text{'}\right|$that has all zeroes in s'.

Case 2:

Consider the string ab'cd'e, that has no 0’s. The length of the string is not equal to the multiple of 3, $\left|s\right|=\left|t\right|=\left|s\text{'}\right|$that has all zeroes in s' .

Case 3:

Consider the string ab'cd'e , that has some 0’s that are derived from the last of $0^{2p}$. In these case,$\left|bcd\right|\le p$ ,the string bcd is the substring. The length of the string is not equal to the multiple of 3,$\left|s\right|=\left|t\right|=\left|s\text{'}\right|$ that has all zeroes in s'.

Thus, all these above cases proves that the string doesnot satisfy the assumption made.

Therefore, In contradiction it has been proved that A is not a Deterministic Context free language