GATE CS 2008 Q51 — Regular and Context-free Languages

To find the correct match, we analyze each programming language concept and its corresponding formal language representation:

1. E → R (Checking that identifiers are declared before their use):
   Checking if an identifier is declared before its use requires matching the exact name of the identifier at two different places in the program. This is modeled by the non-context-free language: $$L = \{w c w \mid w \in (a \mid b)^*\}$$ where the first $w$ represents the declaration, $c$ represents the intermediate code, and the second $w$ represents the usage.
2. F → P (Matching formal and actual parameters):
   When matching the number of formal parameters to actual parameters across multiple or nested function calls, we need to maintain multiple independent counts in a cross-serial manner. This is modeled by the non-context-free language: $$L = \{a^n b^m c^n d^m \mid n \geq 1, m \geq 1\}$$ where the count of $a$'s matches $c$'s, and the count of $b$'s matches $d$'s.
3. G → Q (Arithmetic expressions with matched parentheses):
   The context-free grammar: $$X \rightarrow XbX \mid XcX \mid dXf \mid g$$ generates arithmetic expressions where $b$ and $c$ act as binary operators, $g$ acts as an operand, and $d$ and $f$ act as matching opening and closing parentheses (like ( and )).
4. H → S (Palindromes):
   The grammar: $$X \rightarrow bXb \mid cXc \mid \epsilon$$ is the standard context-free grammar that generates even-length palindromes over the alphabet $\{b, c\}$.

Thus, the correct matching is E-R, F-P, G-Q, H-S, which corresponds to option C.