COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
context-free ⊂ right-linear ⊂ context-sensitive
|
|
|
context-free ⊂ context-sensitive ⊂ right-linear
|
|
|
context-sensitive ⊂ right-inear ⊂context-free
|
|
|
right-linear ⊂context-free ⊂context-sensitive
|
Detailed explanation-1: -All regular languages are context-free languages, but not all context-free languages are regular. Most arithmetic expressions are generated by context-free grammars, and are therefore, context-free languages.
Detailed explanation-2: -A CFG is right-linear if each production body has at most one variable, and that variable is at the right end; i.e. all productions of a right-linear grammar are of form A→wB or A→w, where A and B are variables and w is some string of zero or more terminals.
Detailed explanation-3: -In context sensitive grammar, there is either left context or right context (A i.e. is left context and is right) with variables. But in context free grammar (CFG) there will be no context. We cannot replace B until we get B0. Therefore, CSG is harder to understand than the CFG.
Detailed explanation-4: -The standard form of context-sensitive grammar is as follows: A→, A→BC, AB→CD, where ∈(∪V), A, B, C, D∈V. Context-sensitive language classes have the same language class as what a linear bounded automaton can accept.