Section I
1. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited
2. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
3. Number of states requires accepting string ends with 10 in DFA.
a) 3
b) 2
c) 1
d) can’t be represented.
4. Number of final state requires accepting Φ in minimal finite automata.
a) 1
b) 2
c) 3
d) None of the mentioned
5. An NFA’s transition function returns
a. A Boolean value
b. A state
c. A set of states
d. An edge
6. The behaviour of a NFA can be stimulated by DFA
a. Always
b. Sometimes
c.Never
d. Depends on NFA
7. The relation between NFA-accepted languages and DFA accepted languages is
a. >
b.<
c.=
d.<=
8. Examine the following DFA: If input is 011100101, which edge is NOT traversed?
a. A B
b. C
c. C D
d. D A
9. The transitional function of a NFA is
a. Q X Σ→Q
b. Q X Σ→2Q
c. Q X Σ→2n
d.Q X Σ→Qn
10. Which is true for Dead State?
a. It cannot be reached anytime
b. There is no necessity of the state
c. If control enters no way to come out from the state
d.If control enters FA deads
11. Which among the following states would be notated as the final state/acceptance state?
L= {xϵ∑= {a, b} | length of x is 2}
a. q1
b. q2
c. q1, q2
d. q3
12. Which of the following are the final states in the given DFA according to the Language given?
L= {xϵ∑= {a, b} |length of x is at most 2}
a. q0, q1
b. q0, q2
c.q1, q2
d. q0, q1, q2
Section II
1. For the following NDFA, what would be the states in a corresponding DFA?
a. [q0]
b. [q0], [q1]
c. [q0], [q0, q1]
d. [q0], [q1], [q0, q1]
2. “DFA is said to be a specific case of NDFA and for every NDFA that exists for a given
language, an equivalent DFA also exists”.The statement is True or False?
a. True
b. False
3. While converting NDFA to DFA, 𝛿’([q0, q1, … qi], a)is written as _________________
a. 𝛿([q0, q1, … qi], a)
b. 𝛿([q0], a)
c. 𝛿(q0, a)⋃𝛿(q1, a) …… ⋃𝛿(qi, a)
d. None of above
4. A Finite Automata with ^ - moves is considered to be ___________
a. DFA
b. NDFA
5. Let P and Q be two regular expressions over Σ. If P does not contain ^, then according to
Arden’s theorem, R = Q + RP has a unique solution given by _________________
a. R = QP*
b. R = Q + P*
c. R = Q*P
d. R = Q+ P
6. By using Arden’s Theorem, the equationq1=q1(ab + ba) + ^can be written as,
a. q1=(a+ b)*
b. q1= (abba)*
c. q1= (ab + ba)*
d. q1= (ab)*
7. Arden’s theorem is true for:
a. More than one initial states
b. Non-null transitions
c. Null transitions
d. None of the above
8. Arden’s theorem is false for:
a. More than one initial states
b. Non-null transitions
9. Algebraic method using Arden’s theorem is used for ____________
a. Converting a Regular Expression into a Transition System
b. Finding a Regular Expression corresponding to a given Transition System
10. The regular expression correspondingto the equation q2=0*1 + q2(1) when an Arden’s
Theorem is applied is ______________
a. (0*1)1*
b. (00)*
c. (11)*
d. 0*1*
11. Which of the following is useful for converting afinite automatoninto a regular
expression?
a. Null Moves
b. Kleen’s Closure
c. Transition Function
d. Arden’s Theorem
12. Recognize the regular expression corresponding to the following Finite Automata using
Arden’s Method:
a. 0*1*
b. (0 + 1)*
c. (1101)*
d. (0 + 11 + 010)*
Section III
1. An automata in which output depends only on the states of the machine is called
a) An automaton without a Memory
b) Automaton with a finite Memory
c) Moore Machine
d) Mealy Machine
2. An automata in which output depends only on the states as well as on the input at any
instant of time is called
a) An automaton without a Memory
b) Automaton with a finite Memory
c) Moore Machine
d) Mealy Machine
3. The Finite state machine described by the following state diagram with A as starting
state, where an arc label is x / y and x stands for 1-bit input and y stands for 2- bit output
[ GATE CS 2002]
a) Outputs the sum of the present and the previous bits of the input.
b) Outputs 01 whenever the input sequence contains 11.
c) Outputs 00 whenever the input sequence contains 10.
d) None of these
Explanation:
We assume the input string to be 1101.
1. (A, 1) –> (B, 01)
Here, previous input bit + present input bit = 0 + 1 = 01 = output
2. (B, 1) –> (C, 10)
Here, previous input bit + present input bit = 1 + 1 = 10 = output
3. (C, 0) –> (A, 01)
Here, previous input bit + present input bit = 1 + 0 = 01 = output
4. (A, 1) –> (B, 01)
Here, previous input bit + present input bit = 0 + 1 = 01 = output
Thus, option (A) is correct.
4. In Moore Machine, suppose if Input=’101’, then the output would be of length:
a) |Input|+1
b) |Input|
c) |Input-1|
d) Cannot be predicted
Explanation:
Initial state, from which the operations begin is also initialized with a value.
5. What is the output for the given language?
Language: A set of strings over ∑= {a, b} is taken as input and it prints 1 as an output “for
every occurrence of a b as its substring. (INPUT: abaaab)
a) 0010001
b) 0101010
c) 0111010
d) 0010000
6. Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned
7. Find output string for the input string 0111 from the following Moore Machine
Present State Next State Output
a) 00010
b) 10110
c) 11111
d) 10101
8. Find output string for the input string 1111 from the following Moore Machine
a) 01000
b) 00110
c) 11111
d) 10101
9. Find output string for the input 0010 from the following Mealy machine
a) 0101
b) 1000
c) 1010
d) 1001
10. The following mealy machine outputs which of the following?
Present State Next State Output
a) 9’s Complement
b) 2’s Complement
c) 1’s Complement
d) 10’s Complement
Answer: b
11. The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned
12. Which of the following does the given Mealy machine represents?
a) 9’s Complement
b) 2’s Complement
c) 1’s Complement
d) 10’s Complement
13. Which one among the following is true?
A mealy machine
a) produces a language
b) produces a grammar
c) can be converted to NFA
d) has less circuit delays
Explanation: It does not produce a language or a grammar or can be converted to a NFA.
14. According to Moore circuit, the output of synchronous sequential circuit depend/s on ______
of flip flop
a. Past state
b. Present state
c. Next state
d. External inputs
15. Find the correct answer after, converting the following Mealy to Moore machine
a)
b)
c)
d)
Q: 1 How many states are require to construct a minimal dfa from the given DFA
a)2
b)3
c)4
d)5
2.From the given DFA which string is accepted
a) abbabb
b) abbabba
c) aabba
d) aaba
3.Which DFA is accept the string in which every a is followed by b where Σ = {a,b} .
9. Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011 ?
a. q0, q1,q2
b. q0,q1
c. q0,q1,q2,q3
d. q3
13. Given the language L = {aba, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
a)1, 2 and 3
b)2, 3 and 4
c)1, 2 and 4
d)1, 3 and 4
14.)Let w be any string of length n is {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?
A )n-1
b)n
c)n+1
D)2n-1
Section IV
1. A grammar G = (V, T, P, S) in which V is
a) Set of variables
b) Set of terminals
c) Set of variables and terminals
d) None of these
2. A grammar G = (V, T, P, S) in which T is
a) Set of variables
b) Set of terminals
c) Set of variables and terminals
d) None of these
3. Which of the following is more powerful?
a) PDA
b) Turing machine
c) Finite automata
d) Context sensitive language
4. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned
5. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned
6. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba
7. Which of the following CFG's can't be simulated by an FSM ?
A.S --> Sa | b
B.S --> aSb | ab
C.S --> abX, X --> cY, Y --> d | aX
D.None of these
8. Regular Grammar is accepted by
a. FA
b. LBA
c. Turing Machine
d. All
9. If Σ = {a,b} and given productions are
S→XaaX
X→aX| bX|Λ
Then the above grammar defines the language expressed by___________ regular expression
a. (a+b)*aa(a+b)*
b. (a+b)*a(a+b)*a
c. (a+b)*aa(a+b)*aa
d. (a+b)*aba+b)*
10. The languages which can not accept PDA________
A. Regular Languages
b. Contect Free
C. Context Sensitive
D. None of these
11. Regular grammar is
a) Context free grammar
b) Non context free grammar
c) English grammar
d) None of the mentioned
12. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
13. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
14. Regular expressions are closed under
a) Union
b) Intersection
c) Kleene star
d) All of the mentioned
15. How many strings of length less than 4 contains the language described by the regular expression
(x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11
16. Grammatical rules which involve the meaning of words are called:
a. Semantics
b. Syntactic
c. Both a and b
d. None of given
17. Grammatical rules which do not involve the meaning of words are called:
a. Semantics
b. Syntactic
c. Both a and b
d. None of given
18. The symbols in a grammar that can’t be replaced by anything are called:
a. Productions
b. Terminals
c. Non-terminals
d. All of above
19. The symbols in a grammar that must be replaced by other Synbols are called:
a. Productions
b. Terminals
c. Non-terminals
d. None of given
Section V
1. A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine
2. Regular grammar is
a. context free grammar
b. non context free grammar
c. English grammar
d. none of the mentioned
3. Regular expression are
a. Type 0 language
b. Type 1 language
c. Type 2 language
d. Type 3 language
4. Regular languages are closed under (closure properties)
a. Concatenation
b. Union
c. Complement
d. All of the above
5. If L1 is regular, then there exists some regular expression r1 which describes it. Same for
L2.Then:L1 U L2 = L(r1) U L(r2) = r1 + r2
r1 + r2 is a regular expression and therefore describes a regular language.
a. True
b. False
Answer : a
6. If L1 = {`a^n` | n ≥ 0} and L2 = {`b^n`| n ≥ 0} is regular
then L3 = L1.L2 = {`a^m.b^n` | m ≥ 0 and n ≥ 0} is also regular?
a. False
b True
7. 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.The set of all strings containing the substring 00.
b. The set of all strings containing at most two 0’s.
c. The set of all strings containing at least two 0’s.
d. The set of all strings that begin and end with either 0 or 1.
8. A language is regular if it can be expressed in terms of ……………..
a. Regular expression
b. Type 0 Language
c. English Grammer
g. None of the above
9. Which of the following pairs of regular expressions are equivalent?
a. 1(01)* and (10)*1
b. x (xx)* and (xx)*x
c. x^+ and x^+ x^(*+)
d. All of the above mentioned
10. Regular expressions are used to represent which language
a) Recursive language
b) Context free language
c) Regular language
d) All of these
11. Which of the following operation can be applied on regular expressions?
a) Union
b) Concatenation
c) Closure
d) All of these
12. 7. Which of the following identity is wrong?
a) R + R = R
b) (R*)* = R*
c) ɛR = Rɛ = R
d) ØR = RØ = RR*
13. Which of the following statement is true?
a) Every language that is defined by regular expression can also be defined by finite automata
b) Every language defined by finite automata can also be defined by regular expression
c) We can convert regular expressions into finite automata
d) All of these
14. Which of the following identity is true?
a) ɛ +RR* = R* = ɛ + R*R
b) (R1R2)*R1 = R1(R2R1)*
c) R*R* = R*
d) All of these
15. (a+b)* is equivalent to
a) b*a*
b) (a*b*)*
c) a*b*
d) none of the mentioned
