NET-JUNE-2026
1. Match the LIST-I with LIST-II
LIST-I Language | LIST-II Type of Language | ||
A. | L1 ={anbm | n,m ≥0} | I. | Unrestricted |
B. | L2 ={anbm | (n=m)≥0 } | II. | Context Sensitive |
C. | L3 = { anbncndnen | n ≥1 } | III. | Regular |
D. | L4 = {anbncmdne2| n,m ≥0} | IV. | Context Free |
Choose the correct answer from the options given below:
1. A - III, B - I, C - II, D - IV
2. A - III, B - IV, C - I, D - II
3. A - III, B - II, C - IV, D - I
4. A - II, B - III, C - IV, D - I
NET-JUNE-2026
2. If L1 is a regular language and L2 is a context free language, which of the following statement is correct ?
1. Any subset of L1 ∪ L2 is context free.
2. L1 ∩ L2 is a context free language.
3. L1 ∩ L2 is a regular language.
4. L1 ∩ L2 is accepted by a deterministic
push down automatons.
NET-JUNE-2026
3. Arrange the following families of languange from specialization to generalization, defined over alphabet Σ :
A. Family of all regular languages.
B. Family of all Turing acceptable languages.
C. Family of all Turing decidable languages.
D. Family of all context free languages.
Choose the correct answer from the options given below:
1. A, B, C, D
2. A, C, B, D
3. A, D, C, B
4. A, D, B, C
NET-JUNE-2026
4. Which of the following statements is incorrect ?
1. Given a context free grammar G and a string x, an algorithm can be designed to decide whether x ∈ L(G) in polynomial time.
2. Given a context free grammar L , its complement is also context free.
3. The language {an bm cp: m, n, p ≥ 0, m ≠ n or m ≠ p} is not deterministic context free.
4. Class of deterministic context free languanges is closed under intersection.
NET-JUNE-2026
5. The minimum state of DFA of the following would be the
following:
NET-JUNE-2026
6. - to - 10. Link Questions:
Consider the following Context Free Grammar (G):-
S -> A B
B -> + A B | ∈
A -> C D
D -> * C D | ∈
C -> [S] | x
Variable = {S, A, B, C, D}
Terminals = {+, *, [, ], x }
6. Find the Follow (A) & Follow (C).
1. Follow (A) = { ], $ };
Follow (C) = { +, ], $ };
2. Follow (A) = { +, ], $ };
Follow (C) = { *, +, ], $ };
3. Follow (A) = { *, $, [ };
Follow (C) = { *, [, $ };
4. Follow (A) = { *, ], $ };
Follow (C) = { +, ], $ };
7. In the LL(1) Parsing table of the given CFG, how many valid non blank entities will be there in the rows for variables 'B' and 'D' ?
1. B = 3 entries ; D = 4 entries
2. B = 6 entries ; D = 5 entries
3. B = 2 entries ; D = 3 entries
4. B = 1 entries ; D = 2 entries
8. Identify the correct statement from the following.
1. The given CFG (G) is Left recursive
2. The given CFG (G) needs Left factorization
3. [ [ x * x ] + x] is a valid sentence of this grammar
4. The given CFG (G) has an SLR (0) Parser as well.
9. What will be the FIRST (S) & FIRST (D) ?
1. FIRST (S) = { +, [, x };
FIRST (D) = { +, * };
2. FIRST (S) = { [, ], x };
FIRST (D) = { +, ∈ };
3. FIRST (S) = { [, x };
FIRST (D) = { *, ∈ };
4. FIRST (S) = { [, x, ∈ };
FIRST (D) = { *, ∈ };
10. The I0 state of the canonical LR (0) set of the SLR (1) parser of this CFG has how many productions ?
1. 3
2. 4
3. 5
4. 6
NET-DEC-2025
1. A phase of a compiler which produce the symbol table is
1. Syntax analysis
2. Semantic analysis
3. Target code generation
4. Code optimization
NET-DEC-2025
2. Given below are two statements: one is labelled as Assertion A and the other is labelled as Reson R.
Assertion A: L={ an bn cn : n ≥ 0 } is accepted by a linear bounded automata.
Reson R: Linear bounded automata's recognize exactly the class of context sensitive languages.
In the light of the above statements, choose the most appropriate answer from the options given below
1. Both A and R are correct and R is the correct explanation of A.
2. Both A and R are correct bur R is not the correct explanation of A.
3. A is correct but R is not correct.
4. A is not correct but R is correct.
NET-DEC-2025
3. Match the LIST-I with LIST-II
LIST-I Grammar | LIST-II All productions are of the form | ||
A. | Regular Grammar | I. | A -> aX, where a ∈ T and X ∈ V* |
B. | Unrestricted Grammar | II. | A -> xB, A -> x or A -> Bx, A ->x where A, B ∈ V and x ∈ T* |
C. | Chomsky Normal Form | III. | x -> y, where x ∈ (V U T)* and y ∈(V U T)* |
D. | Greibach Normal Form | IV. | A -> BC or A -> 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
4. A - II, B - IV, C - I, D - III
NET-DEC-2025
4. Which of the following languages cannot be accepted by push down automata ?
A. L = { an bn cn : n ≥ 0 }
B. L={ ap : p is Prime }
C. L={ wcwR : w ∈ (a, b)* }
D. L={ w ∈ (a, b)* : na(w) = nb(w) }
E. L = { an bm cn+m : n ≥ 0, m ≥ 0 }
Choose the correct answer from the options given below:
1. A, C & D only
2. B, D & E only
3. A & B only
4. C & D only
NET-DEC-2025
5. Let P and Q be two regular expressions over ∑. If p does not contain ∈, then the following equation in R namely,
R = Q + RP
has a unique solution given by,
1. R = Q* P*
2. R = Q P*
3. R = PQ*
4. R = Q* + P* R
NET-DEC-2025
6. What is the space complexity of the CYK algorithm for the P table, where n is the number of words in the sentence and m is the number of non terminal symbols in the grammar ?
1. O(n3)
2. O(nm2)
3. O(n2m)
4. O(n2m2)
NET-DEC-2025
7. If r1 and r2 are regular expressions, then which of the following are correct.
A. L ( r1+ r2 ) = L ( r1 ) U L ( r2 )
B. L ( r1 . r2 ) = L ( r1 ) L ( r2 )
C. L ( ( r1 ) ) = L ( r1 )
D. L ( r1* ) = ( L ( r1 ) )*
Choose the correct answer from the options given below:
1. A & B only
2. B, C & D only
3. A, C, & D only
4. A, B, C & D
NET-DEC-2025
8. If
.png)