COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
Regular
|
|
Context Sensitive
|
|
Context Free
|
|
All of the Mentioned
|
Detailed explanation-1: -Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form and has a size no larger than the square of the original grammar’s size.
Detailed explanation-2: -It will help us down the road. Okay, so if it might be good for something, we can ask the natural question: is it possible to convert an arbitrary CFG into an equivalent grammar which is of the Chomsky normal form? The answer, it turns out, is yes.
Detailed explanation-3: -Normal forms for Context-Free Grammars. where V is a “non-terminal symbol” and w is a “string” consisting of terminals and/or non-terminals. The term “context-free” expresses the fact that the non-terminal V can always be replaced by w, regardless of the context in which it occurs.
Detailed explanation-4: -Most famous classification of grammars and languages introduced by Noam Chomsky is divided into four classes: Recursively enumerable grammars –recognizable by a Turing machine. Context-sensitive grammars –recognizable by the linear bounded automaton. Context-free grammars-recognizable by the pushdown automaton.
Detailed explanation-5: -A grammar where every production is either of the form A → BC or A → c (where A, B, C are arbitrary variables and c an arbitrary symbol). (If language contains , then we allow S → where S is start symbol, and forbid S on RHS.) Why Chomsky Normal Form?