MCQ IN COMPUTER SCIENCE & ENGINEERING

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?