Let A = L(G₁) where G₁ is defined in Problem 2.55. Show that A is not a DCFL.Assume that A is a DCFL and consider its DPDA P. Modify P so that its input alphabet is {a, b, c}. 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?

Problem 2.55.

Let G₁ be the following grammar that we introduced in Example 2.45. Use the DK-test to show that G₁ is not a DCFG.

R → S | T

S → aSb | ab

T → aT bb | abb