Question

The correct hierarchical relationship among context-free, right-linear, and context-sensitive language is given by ____________________________.

• A. context-free $<$ right-linear $<$ context-sensitive
• B. context-free- $<$ context-sensitive $<$ right-linear
• C. context-sensitive $<$ right-linear $<$ context-free
• D. right-linear $<$ context-free $<$ context-sensitive

Answer 1

The correct option is D right-linear $<$ context-free $<$ context-sensitive

The correct hierarchical relationship among context-free, right-linear, and context-sensitive language is right-linear < context-free < context-sensitive.

Context-sensitive language:-

Context-sensitive languageis a language that can be defined by a context-sensitive grammar. Context-sensitive is one of the four types of grammars in the Chomsky hierarchy.

Context-free language:-

Context-free language (CFL) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages; in particular, most arithmetic expressions are generated by context-free grammars.

Right-linear language:-

A linear grammar is a context-free grammar that has at most one non-terminal in the right hand side of each of its productions. A linear language is a language generated by some linear grammar.