##### Which of the following option is correct.

Which of the following option is correct.

S1: There exist context-free languages such that all the context-free grammars generating them are ambiguous.

S2: A finite set of string from one alphabet is always a regular language.

(A) Only S1 is true.

(B) Only S2 is true.

(C) Both S1 and S2 are true.

(D) Both S1 and S2 are false

Answer: C

S1: These are called inherently ambiguous grammars. There few grammars where you can not remove ambiguity by applying anything.

An example of an inherently ambiguous language is the union of with . This set is context-free, since the union of two context-free languages is always context-free. But it is proved that there is no way to unambiguously parse strings in the (non-context-free) common subset .

S2: You can always write the regular expression.

In CFG, suppose if ambiguity is removed (by adding precedence rules), and then we generate the same language as ambiguous grammar. Hence we could say that all grammars generating them are not ambiguous. Is this right?

There few grammars where you can not remove ambiguity by applying anything.

An example of an inherently ambiguous language is the union of with . This set is context-free, since the union of two context-free languages is always context-free. But it is proved that there is no way to unambiguously parse strings in the (non-context-free) common subset .