Multiple choice question for engineering
Set 1
1. The language accepted by this DFA is
a) b*ab*ab*ab*
b) (a+b)*
c) b*a(a+b)*
d) b*ab*ab*
Answer
Answer: c [Reason:] Initially circle s around b so b* then a then followed by (a+b)*.
2. The minimum state automaton equivalent to the above FSA has the following number of states
a) 1
b) 2
c) 3
d) 4
Answer
Answer: b [Reason:] State q0 can be omitted because it takes the same input as state q1 hence by removing q0 nothing changes.v
Following is equivalent FSA with 2 states.
3. 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
Answer
Answer: c [Reason:] Only for this option we can build a FA.
4. 
a) q0, q1,q2
b) q0,q1
c) q0,q1,q2,q3
d) q3
Answer
Answer: a [Reason:] From q0 state ->0 then again remain on the same state 0, then to next state 1and to q2 we get 1.
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
Answer
Answer: b [Reason:] 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
Answer
Answer: A [Reason:] 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
Answer
Answer: B [Reason:] baa is not regular so 3.
8. Consider the machine M: The language recognized by M is :
a) {w ∈ {a, b}* / every a in w is followed by ex¬actly two b’s}
b) {w ∈ {a, b}* every a in w is followed by at least two b’}
c) {w ∈ {a, b}* w contains the substring ‘abb’}
d) {w ∈ {a, b}* w does not contain ‘aa’ as a substring}
Answer
Answer: b [Reason:] We can try some sample strings like aba, abbbabbb.
9. 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
Answer
Answer: c [Reason:] Language that can be accepted by DFA is 1001001 1001011, 1001101, 1001111, 1101001, 1111001, 1011001.
Set 2
1. S –> aSa| bSb| a| b ;the language generated by the above grammar is the set of
a) All palindromes.
b) All odd length palindromes
c) Strings beginning and ending with the same symbol
d) All even length palindromes
Answer
Answer: b [Reason:] The strings accepted by language are {a, b, aaa, bbb, aba, bab,}. All the strings are odd length palindromes.
2. 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)*?
a) strings with the substring 00
b) strings with at most two 0’s
c) strings with at least two 0’s
d) strings beginning and ending with either 0 or 1
Answer
Answer: c [Reason:] The RE having 2 0’s padded by (0+1)* which means accepted strings must have at least 2 0’s.
3. Which one is a FALSE statement?
a) There exists a unique DFA for every regular language
b) NFA can always are converted to a PDA
c) Complement of CFL is always recursive
d) Every NDFA can be converted to a DFA
Answer
Answer: d [Reason:] Deterministic PDA cannot handle languages or grammars with ambiguity, but NDFA can handle with ambiguous languages as well as context-free grammar. Hence not every Ndfa can be converted to DFA.
4. Match the following
Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization
a) P-4. Q-1, R-2, S-3
b) P-3, Q-1, R-4, S-2
c) P-3, Q-4, R-1, S-2
d) P-2, Q-1, R-4, S-3
Answer
Answer: b [Reason:] Regular grammar relates to lexical analysis
Pushdown automata relates to Syntax analysis
Data flow analysis is Code optimization
Register allocation is code generation.
5. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:
L1 = {ambmcanbn | m, n >= 0 }
L2 = {aibjck | i, j, k >= 0 }
Then L is
a) Not recursive
b) Regular
c) Context free but not regular
d) None of the mentioned
Answer
Answer: c [Reason:] The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb,} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is L1 ∩L2 = {akbkc | k >= 0} which is not regular but context free.
6. Convert the NFA to DFA
a) 
b) 
c) All of the mentioned
d) None of the mentioned
Answer
Answer: a [Reason:] Initially Q is empty. Then since the initial state of the DFA is {0} , {0} is added to Q.
Since 2( 0 , a ) = { 1 , 2 } , { 1 , 2 } is added to Q and ( { 0 } , a ) = { 1 , 2 } .
Since 2( 0 , b ) = , is added to Q and ( { 0 } , b ) = .
At this point Q = { {0} , { 1 , 2 }, }. Similarly ( { 1 , 2 } , b ) = { 1 , 3 } . Hence { 1 , 3 } is added to Q . Similarly ( { 1 , 3 } , a ) = { 1 , 2 } and ( { 1 , 3 } , b ) = . Thus there are no new states to be added to Q . Since the transitions from all states of Q have been computed and no more states are added to Q, the conversion process stops here.
7. Does epsilon ring any change in the automata
a) Yes
b) No
Answer
Answer: b [Reason:] It adds nothing new to the automata.
Set 3
1. Examine the following DFA: If input is 011100101, which edge is NOT traversed?
a) A B
b) C
c) C D
d) D A
Answer
Answer: c [Reason:] The states traversed are ABDBDABDAC, and the only edge not traversed C D.
2. If string s is accepted by this DFA, which of these strings cannot be suffix of s?
a) 111001
b) 111111
c) 111000
d) 101010
Answer
Answer: a [Reason:] 111001 cannot be the suffix of any string accepted by this DFA. Suppose s=w111001. No matter what state the DFA reaches after reading w, it will go to state D after reading “111”, then go to state B after reading “00” and finally reaches state C after reading “1”.
3. Find the pair of regular expressions that are equivalent
a) (0+1)* and (0*+1*)*
b) (0+1)* and (0+1*)*
c) (0+10)* and (0*+10)*
d) All of the mentioned
Answer
Answer: d [Reason:] All generate all strings of 0’s and 1’s thus are these pairs are equivalent.
4. Which of the following strings is NOT in the Kleene star of the language {011, 10, 110}?
a) 01
b) 10
c) 110
d) 10011101
Answer
Answer: d [Reason:] Every string in the language {011, 10, 110}* has to be formed from zero or more uses of the strings 011, 10, and 110. A string may be used more than once.
5. Which grammar is not regular
a) 0^n
b) 0^n 1^n n
c) 0^m 0^n n
d) 0^n 0^n n
Answer
Answer: a [Reason:] According to pumping lemma, is not a regular language. It is the language of the DFA with two states to achieve an even number of 0’s…
6. If is a language, and is a symbol, then, the quotient of and, is the set of strings such that is in: is in. Suppose is regular, which of the following statements is true?
a) L/a is always a regular language
b) L/a is not a regular language
c) Both of the mentioned
d) None of the mentioned
Answer
Answer: a [Reason:] We can build a DFA for as such: firstly we get the DFA for: Then, we copy all the states and transitions to the DFA for. However, we mark any state as a final state in if and only if is a final state in.
7. Here is a context-free grammar G: S → AB A → 0A1 | 2 B → 1B | 3A which of the following strings are in L (G)?
a) 021300211
b) 022111300211
c) None of the mentioned
d) Both of the mentioned
Answer
Answer: d [Reason:] First, notice that A generates strings of the form 021, where n is 0 or more. Also, B gives zero or more 1’s, which is followed by one 3, and then A gives something. Since S generates something an A can generate followed by something a B can generate, the strings in L (G) are of the form 0 21 30 21.
8. The parse tree below represents a rightmost derivation according to the grammar S → AB, A → aS|a, B → bA. Which of the following are right-sentential forms corresponding to this derivation?
a) aAbAba
b) aababa
c) aABba
d) aSba
Answer
Answer: b [Reason:] S => AB => AbA => Aba => aSba => aABba => aAbAba => aAbaba => aababa.
9. The grammar G: S → SS | a | b is ambiguous. Check all and only the strings that have exactly two leftmost derivations in G
a) bbb
b) ab
c) All of the mentioned
d) None of the mentioned
Answer
Answer: c [Reason:] S => a. A string of length 2 has only one derivation, e.g., S => SS => aS => ab.
10. For the following grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D → E0 | S E → D1 | S Identify all the unit pairs
a) D,C
b) A,B
c) B,C
d) A,C
Answer
Answer: a [Reason:] The cycle of unit-productions S → A → D → S says that any pair involving only S, A, and D is a unit pair. Similarly, the cycle S → B → E → S tells us that any pair involving S, B, and E is a unit pair.
Set 4
1. Which NDFA correctly represents the following RE
a(bab)*∪a(ba)*
a) 
b) 
c) 
d) None of the mentioned
Answer
Answer: a [Reason:] We can verify that the string ababa is accepted by this NFA once we “guess” the state path q0, q2, q5, q2, q5, q2 ∈ F. Of course the only choice is the first one. If we made the wrong startq0,q1,q3,q4,q1 we reach a point where we have a remaining a to process with no place to go. This is a failure.
2. Which is the correct NDFA for the following mentioned expression? (ab)*∪(aba)*.
a)
b)
c)
d) None of the mentioned
Answer
Answer: b [Reason:] A ε transition takes no input and represents a pure nondeterministic choice of being in the state or the target state without having done any processing.
3. NDFAs where introduced by ____________
a) Michael O Rabin & Dana Scott
b) Dan Brown
c) Sun micro system Labs
d) SAP Labs
Answer
Answer: a [Reason:] NFAs were introduced Dana Scott and Michael O. Rabin who also showed their equivalence to DFAs.
4. The regular languages are not closed under
a) Concatenation
b) Union
c) Kleene star
d) Complement
Answer
Answer: d [Reason:] RE are closed under
• Union (cf. picture)
• Intersection
• Concatenation
• Negation
• Kleene closure.
5. The Tuples for NDFA
a) ∑,Q,q0,F,δ
b) Q,q0,F,δ
c) Θ,Q,q0,F,δ
d) F,Q,Δ,q0, δ
Answer
Answer: a [Reason:] An NFA is represented formally by a 5-tuple, (Q, Σ, Δ, q0, F), of
• a set of states Q
• a set of input symbols Σ
• a transition function Δ : Q × Σ → P(Q).
• an initial state q0 ∈ Q
• a final state F ⊆ Q.
6. NFAs are ___ DFAs
a) Larger than
b) More expressive than
c) Less expressive than
d) Equally expressive as
Answer
Answer: a [Reason:] Because there is more number of states for a NDFA than for a DFA for a given expression.
7. An NFA’s transition function returns
a) A Boolean value
b) A state
c) A set of states
d) An edge
Answer
Answer: c [Reason:] A transition function Δ: Q × Σ → P (Q).Where P (Q) denotes the power set of Q…
Set 5
1. L1 is accepted by the NFA, obtained by changing the accepting state of M to a non-accepting state and vice versa. Which of the following statements is true?
a) L1 = {0, 1}* – L
b) L1 = {0, 1}* – L
c) L1 ⊆ L
d) L1=L
Answer
Answer: b [Reason:] Either it takes 0 or 1 or iterations of it or none.compilers-questions-answers-Obtaining the regular Expression from the Finite automata
2. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
a) N2
b) 2N
c) 2N
d) N!
Answer
Answer: b [Reason:] If the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
3. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?
a) L must be {an| n is odd}
b) L must be {an| n is even}
c) L must be {an| n is even}
d) Either L must be {an | n is odd}, or L must be {an | n is even}
Answer
Answer: d [Reason:] There are two states. When first state is final, it accepts even no. of a’s. When second state is final, it accepts odd no. of a’s.
4. How many minimum states are required to find whether a string has odd number of 0’s or not
a) 1
b) 2
c) 3
d) 4
Answer
Answer: b [Reason:] 
5. The number of states in DFA that accepts the language L(M) ∩ L(N) is _________
a) 0
b) 1
c) 2
d) 3
Answer
Answer: b [Reason:] In DFA M: all strings must end with ‘a’. In DFA N: all strings must end with ‘b’. So the intersection is empty. For an empty language, only one state is needed. 
6. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X0.How are X1 and X2 are related ?
X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}
Which one of the following represents the strings in X0?
a) 10 (0* + (10)*)1
b) 10 (0* + (10)*)*1
c) 10 (0* + (10)*)*1
d) 10 (0 + 10)*1 + 110 (0 + 10)*1
Answer
Answer: c [Reason:] The smallest possible string by given grammar is “11”.
X0 = 1X1
= 11X2 [Replacing X1 with 1X2]
= 11 [Replacing X2 with λ]
The string “11” is only possible with option (C).
7. Which of the following languages is/are regular?
L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w
L2: {anbm ⎪m ≠ n and m, n≥0
L3: {apbqcr ⎪ p, q, r ≥ 0}
a) L1 and L3 only
b) L2
c) L2 and L3 only
d) L3 only
Answer
Answer: a [Reason:] L3 is simple to guess, it is regular.
Below is DFA for L1.
L1 is interesting. The important thing to note
about L1 is length of x is greater than 0.
8. The reorganizing capability of NDFA and DFA
a) May be different
b) Must be different
c) Must be same
d) None of the mentioned
Answer
Answer: c [Reason:] Given any NDFA one can construct an equivalent DFA.
9. Which of the following is not regular?
a) String whose length is perfect square and consists of 0s
b) Palindromes consisting of 0’s and 1’s
c) All of the mentioned
d) None of the mentioned
Answer
Answer: c [Reason:] Strings of odd numbers of zeros can be generated by regular expression (00)*0.
10. Which of the following pairs of regular expression are equivalent?
a) 1(01)* and (10)*1
b) X(xx)* and (xx)*x
c) All of the mentioned
d) None of the mentioned
Answer
Answer: c [Reason:] R1 and R2 are reverse of each other. If ant one of them can be generated them the other can be generated as well.
Total Views: 21
