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
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.