Theory of Computation - Online Test

Q1.  Consider the following context-free grammar over the alphabet ∑ = {a,b,c} with S as the start symbol.
S → abScT|abcT
T → bT|b
Which one of the following represents the language generated by the above grammar ? 
Answer : Option B
Explaination / Solution:

The given Grammar over Σ = {a, b, c} with S as the start symbol is 
S → abScT | abcT 
T→ bT | b 
The minimum length string generated by the grammar is 1: 
S→abcT→abcb ; hence all variable greater than 1. 
Other cases
S → abScT→ ab abScT cT → ab ab abScT cT cT →........→ (ab)n (cT)n
Here T can generate any number of b’s starting with single b.  

Q2. If G is grammar with productions S → SaS|aSb|bSa|SS|∈ where S is the start variable, then which one of the following is not generated by G?
Answer : Option D
Explaination / Solution:
No Explaination.


Q3. Consider the following languages over the alphabet ∑= {a, b,c}

Which of the following are context-free languages ? 
I. L∪ L2                  II. L1 ∩ L2
Answer : Option A
Explaination / Solution:



Q4. Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* . We say f is computable if there exists a Turning machine M which given an input x in A* , always halts with f(x) on its tape. Let Lf denote the language {x#f(x)|x∈A*}. Which of the following statements is true:
Answer : Option A
Explaination / Solution:

A TM is recursive iff it halts for every input string (either in accept or reject state). Here, a computable function is defined in a similar way.

Q5. Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are nonterminals
G1 : S → aSb|T,T → cT|∈ 
G2 : S → bSa|T,T → cT|∈
The language L(G1) ∩ L(G2) is
Answer : Option B
Explaination / Solution:

The Context free grammar given over alphabets Σ ={ a, b, c} with S and T as non terminals are:


Q6. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
Answer : Option B
Explaination / Solution:
No Explaination.


Q7. The grammar S → aSa|bS|c is
Answer : Option B
Explaination / Solution:
No Explaination.


Q8. Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?
Answer : Option A
Explaination / Solution:
No Explaination.


Q9. Consider the languages L1 = {0i1j | i≠j}. L2 = {0i1j | i=j}. L3 = {0i1j | i=2j+1}. L4 = {0i1j | i≠2j}. Which one of the following statements is true?
Answer : Option A
Explaination / Solution:
No Explaination.


Q10. Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
Answer : Option B
Explaination / Solution:
No Explaination.