Q26 — Theory of Computation

Theory of Computation

Q26. Marks: +2.0 UGC NET Paper 2: Computer Science 2nd January 2026 Shift 1

Match the LIST-I with LIST-II

LIST-I (Grammar)	LIST-II (All productions are of the form)
A. Regular Grammar	I. $A \to aX$ , where $a \in T$ and $X \in V^*$
B. Unrestricted Grammar	II. $A \to xB, A \to x$ or $A \to Bx, A \to x$ where $A, B \in V$ and $x \in T^*$
C. Chomsky Normal Form	III. $x \to y$ , where $x \in (V \cup T)^+$ and $y \in (V \cup T)^*$
D. Greibach Normal Form	IV. $A \to BC$ or $A \to a$ , where $A, B, C$ are in $V$ and $a$ is in $T$

Choose the correct answer from the options given below:

1.A-II, B-III, C-I, D-IV

2.A-I, B-III, C-II, D-IV

3.A-II, B-III, C-IV, D-I ✓ Correct

4.A-II, B-IV, C-I, D-III

← Previous 1 / 8 in this subject • Back to paper Next →

🏷 Change Tag for this Question ▶