Let $\Sigma=\{a,b,c,d\}$ and let $L=\{a^i b^j c^k d^l \mid i,j,k,l \ge 0\}$. Which of the following constraints ensure(s) that the language is context-free?
Correct answer: (A) $i+k=j+l$; (C) $i=l$ and $j=k$; (D) $i+j=k+l$
Explanation
Option (A) is context-free because the constraint $i+k=j+l$ can be enforced by a single counter that increases on $a$, decreases on $b$, increases on $c$, and decreases on $d$. Option (C) is context-free because it imposes the nested matching pattern $a^i b^j c^j d^i$. Option (D) is also context-free because the single counter can increase through the $a$ and $b$ blocks and decrease through the $c$ and $d$ blocks. However, option (B) requires the crossing dependencies $a^i b^j c^i d^j$, which is not context-free. Therefore, the correct choices are (A), (C), and (D).
More Context-Free Grammars and Pushdown Automata questions
GATE 2025 CS (CS1) Q19– Consider the following context-free grammar G, where S, A, and B are the variables…
GATE 2024 CS (CS1) Q59– Let G=(V,,S,P) be a context-free grammar in Chomsky Normal Form with =\a,b,c\ and V…
GATE 2024 CS (CS2) Q52– Consider a context-free grammar G with rules S aS, S aSbS, S c. Let w L(G) and let n a(w),…
GATE 2023 CS Q39– Consider the context-free grammar G below: S → aSb X; X → aX Xb a b, where S and X are…
GATE 2023 CS Q40– Consider the pushdown automaton (PDA) P below, which runs on the input alphabet a, b, has…
GATE 2021 CS (CS1) Q61– In a pushdown automaton P=(Q,,,,q 0,F), a transition of the form p a, X Y q represents…