Theory of Computation - Online Test
Q1. Definition of a language L with alphabet {a} is given as following
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
Answer : Option B
Explaination / Solution:
Let n = 3 and k=1
(n + 1) states
Q2. A deterministic finite automation (DFA)D with alphabet ∑ = {a,b} is given below
Which of the following finite state machines is a valid minimal DFA which accepts
the same language as D?
Answer : Option A
Explaination / Solution:
Options B and C will accept the string b
Option – D will accept the string “bba”
Both are invalid strings.
So the minimized DFA is option A
Q3. Consider the languages L1, L2 and L3 as given below
Which of the following statements is NOT TRUE?
Answer : Option C
Explaination / Solution:
L1: regular language
L2: context free language
L3: context sensitive language
Q4. Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate
P (x) = ¬ (x = 1) ∧ ∀y (∃z (x = y * z) ⇒ (y = x) ∨ (y = 1))
Answer : Option A
Explaination / Solution:
No Explaination.
Q5. Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is context-free language, then, is 
also context-free?
also context-free? 3) If L is regular language, then, is 
also regular?
also regular? 4) If L is recursive language, then, is 
also recursive?
also recursive?
Answer : Option D
Explaination / Solution:
CFL’s are not closed under complementation. Regular and recursive languages are closed
under complementation.
Q6. Given the language L-{ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
Answer : Option C
Explaination / Solution:
L ={ab, aa, baa}
Let S1 = ab , S2 = aa and S3 =baa
abaabaaabaa can be written as S1S2S3S1S2
aaaabaaaa can be written as S1S1S3S1
baaaaabaa can be written as S3S2S1S2
Q7. What is the complement of the language accepted by the NFA show below?
Assume Σ ={a} and ε is the empty string.
Answer : Option B
Explaination / Solution:
Language accepted by NFA is a+ , so complement of this language is {є}
Q8. What is the correct translation of the following statement into mathematical logic?
“Some real numbers are rational”
Answer : Option C
Explaination / Solution:
Option A: There exists x which is either real or rational and can be both.
Option B: All real numbers are rational
Option C: There exists a real number which is rational.
Option D: There exists some number which is not rational or which is real.
Q9. For the grammar below, a partial LL(1) parsing table is also presented along with the
grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty
string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The First and Follow sets for the non-terminals A and B are
Answer : Option A
Explaination / Solution:
Q10. For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The appropriate entries for E1, E2, and E3 are
Answer : Option C
Explaination / Solution:
