GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 17

Question

Which of the following is/are correct? (Mark all the appropriate choices)

• A. For any CFG $G$ there's a CFG $G_0$ such that $G_0$ is not ambiguous and $L(G) = L(G_0).$
• B. The CFLs are closed under symmetric difference
• C. Every regular language can be generated by a CFG $G = (V,\Sigma,R,S)$ in which all rules are of the form $A \to aB$ or $A \to \varepsilon$ (where $A,B \in V$ and $a \in \Sigma).$
• D. Regular languages having prefix property can be accepted by a Deterministic Pushdown Automata by empty stack

Answer 1

A is false. For inherently ambiguous languages we cannot have an unambiguous grammar. (An inherently ambiguous CFL cannot be deterministic but a nondeterministic CFL may or may not be inherently ambiguous.)

B is false. For $L_1 - L_2,$ by taking $L_1 = \Sigma^*$ which is regular and hence context-free, we have reduced complement problem to symmetric difference. Now, if symmetric difference is closed for CFG, complement must also be closed which is not the case. So, CFLs are not closed under symmetric difference.

C is true. For every regular language there exists a right linear (and left linear) grammar.
D is true. DPDA accepting by empty stack accepts all DCFLs having prefix property. Regular languages having prefix property is a subset of DCFLs having prefix property. (If a regular language is not having prefix property, it won't be accepted by a DPDA by empty stack)

Comments

In Option- C.

A → aB or A→ $\epsilon$

Isn’t any one of them given only??

---

For option C, how to create a grammar with said rules having even number of a's?

---

Hoping that the definition of a regular grammar is clear (if it isn’t, here is a comment that I made which you can check out, if you want to), every regular grammar (without loss of generality, we assume it to be a right-linear grammar) can be reduced to the form mentioned in option (B) as follows:-

1. If we have a production of the form \(A\rightarrow x_1x_2...x_nB\) (where \(A,B \in V, \ x_i \in \Sigma\), and \(n>0\)), then this can be replaced by a chain of productions of the form \(A\rightarrow x_1B_1, \ B_1\rightarrow x_2B_2, \ …, \ B_{n-1}\rightarrow x_nB\), where each \(B_i\) is a newly introduced non-terminal.
2. If we have a production of the form \(A\rightarrow x_1x_2...x_n\) (where \(A \in V, \ x_i \in \Sigma\), and \(n>0\)), then this can be replaced by a chain of productions of the form \(A\rightarrow x_1B_1, \ B_1\rightarrow x_2B_2, \ …, \ B_{n-1}\rightarrow x_n\), where each \(B_i\) is a newly introduced non-terminal.
3. If we have a production of the form \(A\rightarrow B\), then we keep expanding the RHS until it has size greater than 1, and then apply either step (1) or (2), as per need.
4. If we have a production of the form \(A\rightarrow \epsilon\), then we can leave it as it is.

I believe the above four points cover all the possible cases.