The 'C' language is
2012
The 'C' language is
Answer: A. Context free language — Concept: The Chomsky hierarchy classifies a language by the weakest grammar that can generate it. A regular grammar (Type 3) is right-linear and its…
- A.
Context free language
- B.
Context sensitive language
- C.
Regular language
- D.
None of the above
Attempted by 13 students.
Show answer & explanation
Correct answer: A
Concept: The Chomsky hierarchy classifies a language by the weakest grammar that can generate it. A regular grammar (Type 3) is right-linear and its recogniser is a finite automaton, which carries no auxiliary memory. A context-free grammar (Type 2) rewrites exactly one non-terminal at a time and its recogniser is a pushdown automaton, whose stack can track nesting of unbounded depth. A context-sensitive grammar (Type 1) may rewrite a non-terminal only inside a stated surrounding context and never shortens the string; its recogniser is a linear bounded automaton.
Application: Apply that test to the syntax of C, one step at a time.
Read how the syntax of C is actually defined. The language standard, and Appendix A of K&R, state it in BNF, where every production carries exactly one non-terminal on its left-hand side — that is precisely the defining shape of a context-free grammar.
Ask whether less power would do. Suppose the set of valid C programs were regular. Regular languages are closed under intersection with a regular set, so intersecting that set with the regular set of strings {
int main(){a=(i1)j;}: i, j ≥ 0 } would again leave a regular set. That intersection holds exactly the strings in which the two counts are equal, because C requires the parentheses of an expression to balance, and the pumping lemma for regular languages shows that no such set is regular. The supposition therefore fails, and no regular grammar generates C.Ask whether more power is needed. No production of the C grammar rewrites a symbol only when particular neighbours surround it, so the extra strength of a context-sensitive grammar is never called upon to generate the syntax.
The weakest class that generates the syntax of C is therefore Type 2: C is a context-free language.
Cross-check: Contrast the classes by what each one can generate.
Class | Relation to the syntax of C |
|---|---|
Regular language | A finite automaton has a fixed, finite memory, and the intersection argument above shows that the valid C programs are not a regular set, so no Type 3 grammar generates them. |
Context sensitive language | Every context-free language is also context-sensitive, so this is a true upper bound but not the smallest class that generates C, and the Chomsky-hierarchy question asks for the class the grammar actually needs. |
None of the above | A named class does generate the syntax of C, so the catch-all does not apply. |
Note: Rules such as "a variable must be declared before it is used", or the compatibility of types, are not expressible in a context-free grammar; a compiler enforces them in the semantic-analysis phase, after parsing. The syntactic classification of C stays context-free because the grammar governs parsing.