COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
Match the type of grammar according to Chomsky hierarchya) Type 0 i) Regular Grammarb) Type 1 ii) Context Free Grammarc) Type 2 iii) Context sensitive grammard) Type 3 iv) unrestricted grammar
|
|
a)-iv b)-iii c)-ii d)-i
|
|
|
a)-iv b)-i c)-ii d)-iii
|
|
|
a)-iv b)-iii c)-i d)-ii
|
|
|
a)-iii b)-iv c)-ii d)-i
|
Explanation:
Detailed explanation-1: -2 –Context-free grammars Type-2 grammars generate the context-free languages. These are defined by rules of the form A → with A a nonterminal and a string of terminals and nonterminals. These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton.
Detailed explanation-2: -Type 0 grammar is known as Unrestricted grammar. There is no restriction on the grammar rules of these types of languages. These languages can be efficiently modeled by Turing machines.
There is 1 question to complete.