GATE CS 2002 Q2.18 — Programming in C

The correct option is B.

The C programming language is a context-sensitive language due to semantic constraints that cannot be specified by a Context-Free Grammar (CFG). Key reasons include:

• Declaration before use: In C, every variable must be declared before it is used. Checking that an identifier used in an expression has been previously declared requires matching the identifier at two different places in the program. This is analogous to the language $L = \{w c w \mid w \in \{a, b\}^*\}$, which is a well-known context-sensitive (and non-context-free) language.
• Type checking: Verifying that the types of operands match the operator requires context-sensitive analysis.

Why other options are incorrect:

• Options A & C: Since C requires matching arbitrary identifiers, it cannot be represented by a regular or context-free grammar.
• Option D: While a Turing machine can parse C, it is not the only machine capable of doing so. Context-sensitive languages can be parsed by a Linear Bounded Automaton (LBA). In practice, compilers parse the context-free structure of C using a PDA and resolve context-sensitive features using a symbol table.