Regular languages and Finite automata
Question 1 
The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________.
a*b*(ba)*a*
3  
4  
5  
6 
Question 1 Explanation:
The regular expression generate all the strings of length 0 , 1 and 2
{ϵ, a, b, aa, ab, ba, bb}
Let’s check all the string of length 3.
The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}
But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).
{ϵ, a, b, aa, ab, ba, bb}
Let’s check all the string of length 3.
The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}
But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).
Question 2 
Consider the languages L_{1} = ϕ and L_{2 }= {a}. Which one of the following represents L_{1}L_{2}* ∪ L_{1}*?
{є}  
ϕ  
a*  
{є,a} 
Question 2 Explanation:
As we know, for any regular expression R,
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Question 3 
Consider the DFA given.
Which of the following are FALSE?
1. Complement of L(A) is contextfree. 2. L(A) = L((11*0+0)(0 + 1)*0*1*) 3. For the language accepted by A, A is the minimal DFA. 4. A accepts all strings over {0, 1} of length at least 2.
1 and 3 only  
2 and 4 only  
2 and 3 only  
3 and 4 only 
Question 3 Explanation:
L(A) is regular and its complement is also regular (by closure property) and every regular is CFL also. So Complement of LA is contextfree.
The regular expression corresponding to the given FA is
Hence we have regular expression: (11*0 +0) (0+1)*
Since we have (0+1)* at the end so if we write 0*1* after this it will not have any effect, the reason is whenever string ends with the terminals other than 1*0* there we can assume 1*0* as epsilon.
So it is equivalent to (11*0 +0) (0+1)*0*1*
The given DFA can be minimised, since the nonfinal states are equivalent and can be merged and the min DFA will have two states which is given below:
Hence statement 3 is false.
Since DFA accept string “0” whose length is one, so the statement “A accepts all strings over {0, 1} of length at least 2” is false statement.
The regular expression corresponding to the given FA is
Hence we have regular expression: (11*0 +0) (0+1)*
Since we have (0+1)* at the end so if we write 0*1* after this it will not have any effect, the reason is whenever string ends with the terminals other than 1*0* there we can assume 1*0* as epsilon.
So it is equivalent to (11*0 +0) (0+1)*0*1*
The given DFA can be minimised, since the nonfinal states are equivalent and can be merged and the min DFA will have two states which is given below:
Hence statement 3 is false.
Since DFA accept string “0” whose length is one, so the statement “A accepts all strings over {0, 1} of length at least 2” is false statement.
Question 4 
Let L be a regular language and M be a contextfree language, both over the alphabet Σ. Let L^{c} and M^{c} denote the complements of L and M respectively. Which of the following statements about the language if L^{c} ∪ M^{c} is TRUE?
It is necessarily regular but not necessarily contextfree.  
It is necessarily contextfree.  
It is necessarily nonregular.  
None of the above. 
Question 4 Explanation:
Contextfree languages not closed under complementation. So, L^{c} ∪ M^{c} is neither regular nor contextfree. It might be context sensitive language.
Question 5 
Which of the following statements is TRUE about the regular expression 01*0?
It represents a finite set of finite strings.  
It represents an infinite set of finite strings.  
It represents a finite set of infinite strings.  
It represents an infinite set of infinite strings.

Question 5 Explanation:
The given expression01*0 is regular. So this is a finite string. So options C and D are false and * is placed. So this is infinite set.
So, given regular expression represents an infinite set of finite strings.
So, given regular expression represents an infinite set of finite strings.
Question 6 
The language {0^{n} 1^{n} 2^{n}  1 ≤ n ≤ 10^{6}} is
regular  
contextfree but not regular  
contextfree but its complement is not contextfree  
not contextfree 
Question 6 Explanation:
In this the value of n is finite then we can be able to construct a finite state automata for this language.
So, given language is regular.
So, given language is regular.
Question 7 
Consider the nondeterministic finite automaton (NFA) shown in the figure.
State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about L1 and L2 is TRUE? Correction in Question: There is an edge from Z>Y labeled 0 and another edge from Y>Z labeled 1  in place of double arrowed and no arrowed edges.
L1 = L2  
L1 ⊂ L2  
L2 ⊂ L1  
None of the above 
Question 7 Explanation:
Based on Arden's theorem write the Y and Z in terms of incoming arrows,
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
Question 8 
Consider the contextfree grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?
id + id + id + id  
id + (id* (id * id))  
(id* (id * id)) + id  
((id * id + id) * id) 
Question 8 Explanation:
Let's draw more than one possible tree for id + id + id + id.
There are 8 questions to complete.