verified computer science q$a 2025

1. Let P be a regular language and Q be context-free language such that Q ∈ P.
(For example, let P be the language represented by the regular expression p*q*
and Q be {pnqn
n∈ N}). Then which of the following is ALWAYS regular?
A. P ∩ Q

B. P – Q

C. ∑* – P

D. ∑* – Q

Answer:
C. ∑* – P

2. Given a Non-deterministic Finite Automation (NFA) with states p and r as
initial and final states respectively and transition table as given below:
AB
P–Q
qRS
rRS
sRS
The minimum number of states required in Deterministic Finite Automation
(DFA) equivalent to NFA is
A. 5
B. 4

C. 3

D. 2

Answer:
C. 3

3. Which one of the following statement is true for a regular language L over {a}
whose minimal finite state automation has two states?
A. L must be either {an I n is odd} or {an I n is even}
B. L must be {an I n is odd}

C. L must be {an I n is even}

D. L must be {an I n = 0}

Answer:
A. L must be either {an I n is odd} or {an I n is even}

, 4. The …………. is said to be ambiguous if there exist at least one word of its
language that can be generated by the different production tree .
A. CFL
B. CFG

C. GTG

D. None of the given

Answer:
B. CFG

Unit 2
5. Type-1 Grammar is known as_____________
A. CFG
B. CSG

C. REGULAR

D. All

Answer:
B. CSG

6. If G is “S → a S/a”, then L(G) = ?
A. a*
B. ^

C. {a}+

D. Both (a) & (c)

Answer:
C. {a}+

7. “S →a S”, what is the type of this production?
A. Type 0
B. Type 1

C. Type 2

D. Type 3

Answer:
D. Type 3