UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (September 2022)
Q12. The reduced grammar equivalent to the grammar whose production rules are given below is
S → AB | CA
B → BC | AB
A → a
C → aB | b
S → AB | CA
B → BC | AB
A → a
C → aB | b
- S → CA, A → a, C → b
- S → CA | B, B → BC | B, A → a, C → aB | b
- S → CA | B, B → BC, A → a, C → aB | b
- S → AB | AC, B → BC | BA, A → a, C → aB | b
Q13. Consider the production rules of grammar G:
S → AbB
A → aAb | λ
B → bB | λ
Which language L is generated by G?
S → AbB
A → aAb | λ
B → bB | λ
Which language L is generated by G?
- L = {anbm : n ≥ 0, m > n}
- L = {anbm : n ≥ 0, m ≥ 0}
- L = {anbm : n ≥ m}
- L = {anbm : n ≥ m, m > 0}
Q14. Consider the language L = {anbm : n ≥ 4, m ≤ 3}. Which regular expression represents L?
- aaaa*(λ + b + bb + bbb)
- aaaaa*(b + bb + bbb)
- aaaaa*(λ + b + bb + bbb)
- aaaa*(b + bb + bbb)
Q15. Consider L = {ab, aa, baa}. Which of the following strings is NOT in L*?
- baaaaabaaaaa
- abaabaaabaa
- aaaabaaaa
- baaaaabaa
Q16. Consider the NPDA M = ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with
δ(q0, λ, z) = {(qf, z)}
δ(q0, a, z) = {(q1, 11z)}
δ(q1, a, 1) = {(q1, 111)}
δ(q1, b, 1) = {(q1, λ)}
δ(q1, λ, z) = {(qf, z)}
Which language L is accepted by the NPDA?
δ(q0, λ, z) = {(qf, z)}
δ(q0, a, z) = {(q1, 11z)}
δ(q1, a, 1) = {(q1, 111)}
δ(q1, b, 1) = {(q1, λ)}
δ(q1, λ, z) = {(qf, z)}
Which language L is accepted by the NPDA?
- L = {a2nbn : n ≥ 0}
- L = {anb2n : n ≥ 0}
- L = {a2nbn : n > 0}
- L = {anb2n : n > 0}
Q65. Consider two instances X and Y of the Post Correspondence Problem, each with lists A and B of three strings over {0, 1}. Which of the following is true?
X
| i | List A | List B |
|---|---|---|
| 1 | 1 | 111 |
| 2 | 10111 | 10 |
| 3 | 10 | 0 |
Y
| i | List A | List B |
|---|---|---|
| 1 | 10 | 101 |
| 2 | 011 | 11 |
| 3 | 101 | 011 |
- Only PCP in X has a solution
- Only PCP in Y has a solution
- PCP in both X and Y has a solution
- PCP in neither X nor Y has a solution
Q66. Consider the following properties of recursively enumerable sets:
(A) Finiteness
(B) Context-freedom
(C) Emptiness
Which of the following is true?
(A) Finiteness
(B) Context-freedom
(C) Emptiness
Which of the following is true?
- Only (A) and (B) are not decidable
- Only (B) and (C) are not decidable
- Only (C) and (A) are not decidable
- All of (A), (B) and (C) are not decidable
Q69. Consider the grammar S → SbS | a and the string abababa. Consider the statements: the string has
(A) two parse trees
(B) two leftmost derivations
(C) two rightmost derivations
Which of the following is correct?
(A) two parse trees
(B) two leftmost derivations
(C) two rightmost derivations
Which of the following is correct?
- All of (A), (B) and (C) are true
- Only (B) is true
- Only (C) is true
- Only (A) is true
Q78. Match List I with List II.
Choose the correct answer from the options given below:
Choose the correct answer from the options given below:
| List I | List II |
|---|---|
| A. Type 0 | I. Finite automata |
| B. Type 1 | II. Turing machine |
| C. Type 2 | III. Linear bounded automata |
| D. Type 3 | IV. Pushdown automata |
- A-III, B-IV, C-II, D-I
- A-II, B-III, C-IV, D-I
- A-III, B-IV, C-I, D-II
- A-II, B-III, C-II, D-IV
Q91. Consider the following statements:
Statement I: An LALR parser is more powerful than a canonical LR parser.
Statement II: An SLR parser is more powerful than LALR.
Which of the following is correct?
Statement I: An LALR parser is more powerful than a canonical LR parser.
Statement II: An SLR parser is more powerful than LALR.
Which of the following is correct?
- Statement I true and Statement II false
- Statement I false and Statement II true
- Both Statement I and Statement II false
- Both Statement I and Statement II true
Q92. Consider the following statements about context-free languages (CFL):
Statement I: CFLs are closed under homomorphism.
Statement II: CFLs are closed under complement.
Which of the following is correct?
Statement I: CFLs are closed under homomorphism.
Statement II: CFLs are closed under complement.
Which of the following is correct?
- Statement I is true and Statement II is false
- Statement II is true and Statement I is false
- Both Statement I and Statement II are true
- Neither Statement I nor Statement II is true