Match List I with List II : List I List II (A) Type 0 (I) Finite automata (B)…

2022

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 :

  1. A.

    (A)−(III),(B)−(IV),(C)−(II),(D)−(I)

  2. B.

    (A)−(II),(B)−(III),(C)−(IV),(D)−(I)

  3. C.

    (A)−(III),(B)−(IV),(C)−(I),(D)−(II)

  4. D.

    (A)−(II),(B)−(III),(C)−(II),(D)−(IV)

Attempted by 140 students.

Show answer & explanation

Correct answer: B

Correct matching and justification:

  • Type 0 → Turing machine: Type-0 (unrestricted) grammars generate recursively enumerable languages which are recognized by Turing machines.

  • Type 1 → Linear bounded automata: Type-1 (context-sensitive) grammars generate context-sensitive languages recognized by linear bounded automata (LBAs).

  • Type 2 → Pushdown automata: Type-2 (context-free) grammars generate context-free languages recognized by pushdown automata (PDAs).

  • Type 3 → Finite automata: Type-3 (regular) grammars generate regular languages recognized by finite automata (FAs).

Therefore the correct associations are: Type 0 → Turing machine; Type 1 → Linear bounded automata; Type 2 → Pushdown automata; Type 3 → Finite automata.

Explore the full course: Mppsc Assistant Professor