1. DFAs, NFAs, and ε-NFA s are equivalent.
a) True
b) False
Explanation: For every NFA there is an ε-NFA that accepts a similar language and vice versa.
2. The language accepted by this DFA is?
a) b*ab*ab*ab*
b) (a+b)*
c) b*a(a+b)*
d) b*ab*ab*
Explanation: Initially circle s around b so b* then a then followed by (a+b)*.
3. The minimum state automation equivalent to the below FSA has the following number of states?
a) 1
b) 2
c) 3
d) 4
Explanation: State q0 can be omitted because it takes the same input as state q1 hence by removing q0 nothing changes.
Following is equivalent FSA with 2 states.
4. Which one of the following is TRUE?
a) The language L={a^n b^n |n>0 } is regular
b) The language L={a^n |n is prime } is regular
c) The language L={w|w has 3k+1 b’s for some k } is regular
d) None of the mentioned
Explanation: Only for this option we can build a FA.
5. Which of the regular expressions given below represent the following DFA?
I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1
a) I and II only
b) I and III only
c) II and III only
d) I II III
Explanation: 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1
(I) and (III) represent DFA.
(II) doesn’t represent the DFA since it accepts strings like 11011, but the regular expression doesn’t accept.
6. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences of (110)’s as (011)’s}.
Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences of (000)’s as (111)’s}.
Which one of the following is TRUE?
a) L1 is regular but not L2
b) L2 is regular
c) L1 and L2 are regular
d) Neither of them are regular
Explanation: L1 is regular let us considering the string 011011011011 . Number of times 011 has occurred is 4 but also its occurrence is 3. Also if the string is ending with 011 we can make a 110 . Now the next string: 110110110110 in this 110 has occurred 4 times and 011 3 times which already satisfy the .
7. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is _____________
a*b*(ba)*a*
a) 2
b) 3
c) 4
d) 5
Explanation: baa is not regular so 3.
8. Consider the following deterministic finite state automaton M.
S denotes the set of seven bit in which the 1st ,4th and last bits are 1. The number of strings that are accepted by M is
a) 1
b) 5
c) 7
d) 8
Explanation: Language that can be accepted by DFA is 1001001 1001011, 1001101, 1001111, 1101001, 1111001, 1011001.
9. In a compiler the module that checks every character of the source text is called __________
a) The code generator
b) The code optimizer
c) The lexical analyzer
d) The syntax analyzer
Explanation: Lexical analysis is the process of converting a sequence of characters into a sequence of tokens.
10. The context free grammar is ambiguous if ______________
a) The grammar contains non-terminals
b) Produces more than one parse tree
c) Production has two non-terminals side by side
d) None of the mentioned
Explanation: Since more than one parse tree is generated hence one than option is available .Therefore it’s ambiguous.