List of top Computer Science and IT Engineering Questions on Context Free Languages and Pushdown Automata asked in GATE CS

Let \(\Sigma=\{a,b,c,d\}\) and \(L=\{a^i b^j c^k d^{\ell}\mid i,j,k,\ell\geq0\}\).
Which of the following constraints ensure(s) that the language \(L\) is context-free?

Which of the following grammars is/are ambiguous?

Let 𝐿1 and 𝐿2 be two languages over a finite alphabet, such that 𝐿1 ∩𝐿2 and 𝐿2 are
regular languages.
Which of the following statements is/are always true?

Consider the following grammar where 𝑆 is the start symbol, and 𝑎 and 𝑏 are
terminal symbols.
𝑆 →𝑎𝑆𝑏𝑆 ∣ 𝑏𝑆 ∣ ϵ
Which of the following statements is/are true?

Consider the following context-free grammar 𝐺.
𝑆→𝑎𝑏𝑎𝐴𝐵𝐴𝑏𝑏𝑎
𝐴→𝑎𝑎𝐵𝐵𝐴𝑏 | 𝑏𝐵𝑎𝑏𝑎𝑎
𝐵→𝑎𝐵𝑏 | 𝑎𝑏
In the above grammar, 𝑆 is the start symbol, 𝑎 and 𝑏 are terminal symbols, and 𝐴 and
𝐵 are non-terminal symbols.
Let 𝐿(𝐺) be the language generated by the grammar 𝐺. For a string 𝑠∈𝐿(𝐺), let
𝑛1(𝑠) be the number of 𝑎’s in 𝑠 and 𝑛2(𝑠) be the number of 𝑏’s in 𝑠.
Which of the following statements is/are true?