List of top Theory of Computation Questions on Context Free Grammars asked in GATE CS

Which of the following grammars is/are ambiguous?

Consider the following grammar where \(S\) is the start symbol, and \(a\) and \(b\) are terminal symbols.
\[ S \rightarrow aSbS \mid bS \mid \epsilon \]
Which of the following statements is/are true?

Consider the following context-free grammar \(G\).
\[ S \rightarrow abaABAbba \]\[ A \rightarrow aaBBAb \mid bBabaa \]\[ B \rightarrow aBb \mid ab \]In the above grammar, \(S\) is the start symbol, \(a\) and \(b\) are terminal symbols, and \(A\) and \(B\) are non-terminal symbols.
Let \(L(G)\) be the language generated by the grammar \(G\). For a string \(s \in L(G)\), let \(n_1(s)\) be the number of \(a\)'s in \(s\) and \(n_2(s)\) be the number of \(b\)'s in \(s\).
Which of the following statements is/are true?