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 \{a^{n}b^{m}c^{m}d^{n}|n,m>0\} with \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}. 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 \{a^{n}b^{n}c^{n}d^{n}|n>0\}.

S2: You can always write the regular expression.

2Comments
Sri sricherry 11 Jan 2018 10:55 am

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?

Sumit Verma sumitverma 11 Jan 2018 11:12 am

There few grammars where you can not remove ambiguity by applying anything.
An example of an inherently ambiguous language is the union of \{a^{n}b^{m}c^{m}d^{n}|n,m>0\} with \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}. 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 \{a^{n}b^{n}c^{n}d^{n}|n>0\}.