# Theory of Computation - Online Test

Q1. S → a Sa| bSb| a| b The language generated by the above grammar over the alphabet {a, b} is the set of
Answer : Option B
Explaination / Solution:
No Explaination.

Q2. Which one of the following languages over the alphabet {0, 1} is described by the regular expression: (0 + 1)* 0 (0 + 1)* 0(0 + 1)*?
Answer : Option C
Explaination / Solution:
No Explaination.

Q3. Which one of the following is FALSE?
Answer : Option D
Explaination / Solution:
No Explaination.

Q4. Let L = L1 ∩ L2, where L1 and Lare languages as defined below: Then L is
Answer : Option C
Explaination / Solution:
No Explaination.

Q5. Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below: Which of the above sche dules are conflict-serializable?
Answer : Option B
Explaination / Solution:
No Explaination.

Q6. If the difference between the expectation of the square of random variable (E[X2]) and the square of the expectation of the random variable (E[X2]) is denoted by R then
Answer : Option C
Explaination / Solution:
No Explaination.

Q7. The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
Answer : Option A
Explaination / Solution:

Lexical Analysis is implemented by finite automata

Q8. An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 : n - 1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Initialize Ln-1 =1
For all i such that 0 ≤ i ≤ n − 2 Finally the length of the longest monotonically increasing sequence is max (L0L1,....,Ln-1). Which of the following statements is TRUE?
Answer : Option A
Explaination / Solution:
No Explaination.

Q9. Let P be a regular language and Q be a context free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pn qn | n ∈ N}). Then which of the following is ALWAYS regular?
Answer : Option C
Explaination / Solution:

Σ* − P is the complement of P so it is always regular, since regular languages are closed under complementation

Q10. Which of the following pairs have DIFFERENT expressive power?
Answer : Option B
Explaination / Solution:

NPDA is more powerful than DPDA.