UGC NET CSE | October 2022 | Part 1 | Question: 45

Question

Match List I with List II :

List I	List II
(A) Type $0$	(I) Finite automata
(B) Type $1$	(II) Tuning machine
(C) Type $2$	(III) Linear bound automata
(D) Type $3$	(IV) Pushdown automata

Choose the correct answer from the options given below :

• A. $(\text{A})-\text{(III)}, (\text{B})-(\text{IV}), (\text{C})-(\text{II}), (\text{D})-(\text{I})$
• B. $(\text{A})-(\text{II}), (\text{B})-(\text{III}), (\text{C})-(\text{IV}), (\text{D})-(\text{I})$
• C. $(\text{A})-(\text{III}), (\text{B})-(\text{IV}), (\text{C})-(\text{I}), (\text{D})-(\text{II})$
• D. $(\text{A})-(\text{II}), (\text{B})-(\text{III}), (\text{C})-(\text{II}), (\text{D})-(\text{IV})$

 

Answer 1

According to the Chomsky Hierarchy :

• Type $0$ grammar is unrestricted grammar which is accepted by the turning machine.
• Type $1$ grammar is the context-sensitive grammar that is accepted by linear bounded automata.
• Type $2$ grammar is context-free grammar which is accepted by push-down automata
• Type $3$ grammar is regular grammar which is accepted by finite automata.

So $A=(II),B=(III),C=(IV),D=(I)$

 

Answer 2

Machine equivalent to Type 0 Grammer is Turing Machine.

Machine Equivalent to type 1 Grammer(CSL) is Linear bounded automata.

Machine Equivalent to Type 2 Grammer( CFL) is PUSH DOWN AUTOMATA.

Type 3 Grammer is regular Grammer and equivalent system is Finite automata.

 

Hence Option B.