Match the following : \(\begin{array} {clcl} & \textbf{List – I} &&…
2014
Match the following :
\(\begin{array} {clcl} & \textbf{List – I} && \textbf{List – II} \\ \text{a.}& \text{Context free grammar} & \text{i.} & \text{Linear bounded automaton} \\ \text{b.}& \text{Regular grammar} & \text{ii.} & \text{Pushdown automaton} \\ \text{c.}& \text{Context sensitive grammar} & \text{iii.} & \text{Turing machine} \\ \text{d.}& \text{Unrestricted grammar} & \text{iv.} & \text{Deterministic finite automaton} \\ \end{array}\)
Codes :
- A.
a-ii, b-iv, c-iii, d-i
- B.
a-ii, b-iv, c-i, d-iii
- C.
a-iv, b-i, c-ii, d-iii
- D.
a-i, b-iv, c-iii, d-ii
Attempted by 143 students.
Show answer & explanation
Correct answer: B
Correct matching: Context-free grammar → Pushdown automaton; Regular grammar → Deterministic finite automaton; Context-sensitive grammar → Linear bounded automaton; Unrestricted grammar → Turing machine.
Context-free grammar: Recognized by a pushdown automaton because context-free languages require a stack to handle nested or recursive structures.
Regular grammar: Recognized by a deterministic finite automaton because regular languages need only a finite amount of state memory.
Context-sensitive grammar: Recognized by a linear bounded automaton because the computation is constrained to tape space proportional to the input length.
Unrestricted grammar: Recognized by a Turing machine because there are no restrictions on productions, so full general computation power is required.
A video solution is available for this question — log in and enroll to watch it.