FLAT important Questions
I Choose the correct alternative
1.The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} | where
string s contains even number of 0 and 1
a) 01,0011,010101 b) 0011,11001100 c) ε,0011,11001100 d) ε,0011,11001100 [ ] [CO1,PO1,PO2]
2. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using
the operation. a) Union b) Concatenation c) Kleene* d) All of the mentioned [ ] [CO1,PO1,PO2]
3.The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1 b) 3 c) 5 d) [ ] [CO1,PO1,PO2]
4.Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet b) Transition function c) Initial State d) Output Alphabet [ ] [CO1,PO1,PO2]
5.The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2- and
∑=,0,1- a) 7 b) 6 c) 8 d) 5 * + [CO2,PO1,PO2]
6. There are ________ tuples in finite state machine.
a) 4 b) 5 c) 6 d) unlimited [ ] [CO2,PO1,PO2]
7. Transition function maps.
a) Σ * Q -> Σ b) Q * Q -> Σ c) Σ * Σ -> Q d) Q * Σ -> Q [ ] [C2,PO1,PO2]
8. δ*(q,ya) is equivalent to .
a) δ((q,y),a) b) δ(δ*(q,y),a) c) δ(q,ya) d) independent from δ notation [ ] [CO2,PO1,PO2]
9. String X is accepted by finite automata if .
a) δ*(q,x) E A b) δ(q,x) E A c) δ*(Q0,x) E A d) δ(Q0,x) E A [ ] [CO3,PO1,PO2]
10. The Grammar can be defined as: G=(V, ∑, p, S) In the given definition, what does S represents?
a) Accepting State b) Starting Variable c) Sensitive Grammar d) None of these
[ ] CO3,PO1,PO2]
II Fill in the blanks
1.. Under which of the following operation, NFA is not closed?--------------- [ ] [CO1,PO1,PO2]
2. It is less complex to prove the closure properties over regular languages using----------------
[ ] [CO1,PO1,PO2]
3. Which of the following do we use to form an NFA from a regular expression?--------------------
[ ] [CO1,PO1,PO2]
4. Which among the following can be an example of application of finite state machine(FSM)?
----------------------------[ ] [CO1,PO1,PO2]
5. L1= {w | w does not contain the string tr } L2= {w | w does contain the string tr}
Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?
------------------------- [ ] [CO2,PO1,PO2]
6. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}---------------------------[ ] [CO2,PO1,PO2]
7. A binary string is divisible by 4 if and only if it ends with:--------------------------
[ ] [CO2,PO1,PO2]
8. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L, [ ] [CO2,PO1,PO2]
9. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be
____________ under an operation op. [ ] [CO3,PO1,PO2]
10. If L1′ and L2′ are regular languages, then L1.L2 will be----------------------
1..Which of the following is not an example of finite state machine system?[ ][CO1,PO1,PO2]
a) Control Mechanism of an elevator b) Combinational Locks c) Traffic Lights d) Digital
Watches
2..Given L= {Xϵ∑*= {a, b} |x has equal number of a, s and b’s}.[ ][CO1,PO1,PO2]
Which of the following property satisfy the regularity of the given language?
a) Regularity is dependent upon the length of the string b) Regularity is not dependent upon the
length of the string c) Can’t be said for a particular string of a languaged) It may depend on the
length of the string
3. Language of finite automata is. [ ][CO1,PO1,PO2]
a) Type 0 b) Type 1 c) Type 2 d) Type 3
4. . Finite automata requires minimum _______ number of stacks. [ ][CO1,PO1,PO2]
a) 1 b) 0 c) 2 d) None of the mentioned
5. Which of the following options is correct? [ ][CO2,PO1,PO2]
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
a) Statement 1 is true and Statement 2 is true b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true d) Statement 1 is false and Statement 2 is also
false
6. An automaton that presents output based on previous state or current input: [ ][CO2,PO1,PO2]
a) Acceptor b) Classifier c) Transducer d) None of the mentioned.
7. NFA, in its name has ’non-deterministic’ because of : [ ][CO2,PO1,PO2]
a) The result is undetermined b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic d) All of the mentioned
8. The construction time for DFA from an equivalent NFA (m number of node)is: [
][CO2,PO1,PO2]
a) O(m2) b) O(2m) c) O(m) d) O(log m)
9. Under which of the following operation, NFA is not closed? [ ][CO3,PO1,PO2]
a) Negation b) Kleene c) Concatenation d) None of the mentioned
10. It is less complex to prove the closure properties over regular languages using[
][CO3,PO1,PO2]
a) NFA b) DFA c) PDA d) Can’t be said
II Fill in the blanks
1.Which of the following do we use to form an NFA from a regular expression? [CO1,PO1,PO2]
2: Which among the following can be an example of application of finite state machine(FSM)?
Ans:--------------------------- [CO1,PO1,PO2]
3. L1= {w | w does not contain the string tr } L2= {w | w does contain the string---------
_[CO1,PO1,PO2]
Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and
L2?
4. The total number of states to build the given language using DFA:[CO1,PO1,PO2]
L= {w | w has exactly 2 a’s and at least 2 b’s}-----------------------[CO1,PO1,PO2]
5. A binary string is divisible by 4 if and only if it ends with:----------------------------
[CO2,PO1,PO2]
6. If L1 and L2 are regular languages, which among the following is an exception?---------
[CO2,PO1,PO2]
7. Predict the analogous operation for the given language:A: {[p, q] | p ϵ A1, q does not belong to
A2}-----
8. Which among the following looks similar to the given expression?((0+1). (0+1)) *------
[CO2,PO1,PO2]
9. Concatenation of R with Ф outputs:-------------------- [CO3,PO1,PO2]
10. The total number of states required to automate the given regular expression
(00)*(11)*----------------------------------- [CO3,PO1,PO2]
Big questions
1.a. Give the formal definition of FA? [2M][CO1, PO1,PO2]
b. Let M =({ q0,q1,q2,q3},{0,1},δ,q0) and the transition functions are
δ (q0, 0) =q2 δ (q2, 0) =q0
δ (q0, 1) =q1 δ (q2, 1) =q3
δ (q1, 0) =q3 δ (q3, 0) =q1
δ (q1, 1) =q0 δ (q3, 1) =q2
a) Represent M by its State table
b) Represents M by its State diagram
c) Which of the following strings are accepted by M
1) 110101 2) 01001 3)1010 [3][CO1,PO1,PO2]
2.Construct DFA equivalent to given NFA
States 0 1
p { p, q} p
q r s
r s -
*s s s
The NFA M = ({p, q, r, s}, {0, 1}, δ, {p}, {s}) [M 5][CO1,PO1,PO2]
3.Consider the following є –NFA. Compute the є –closure of each state and find its
equivalent DFA [M 5][CO2,PO1,PO2]
State Є A b c
p {q} {p} φ Φ
q {r} Φ {q} Φ
*r Φ Φ φ {r}
4.a. Construct an NFA equivalent to the following Regular expression
((10)+(0+1)*)01 [M 3][CO2,PO1,PO2]
b. Show that id+id*id can be generated by two distinct derivation in the grammar &
E → E+E / E*E / (E)| id & draw parse trees. [M 3][CO3,PO1,PO2]
1.Construct DFA equivalent to given NFA
States 0 1
p { p, q} p
*q r r
r s -
*s s s
The NFA M = ({p, q, r, s}, {0, 1}, δ, {p}, {q,s}) [M 5][CO1,PO1,PO2]
2.Convert the Elision NFA to DFA [M 5][CO1,PO1,PO2]
3. Find out whether the following languages are regular or not [M 5][CO2,PO1,PO2]
1) L={w є { a,b}|w = w R }
2) L={ 0 n 1 m 2 n+m , n,m >=1}
3) L={1 k | k = n 2 ,n>=1}
4) L1| L2 = { x |for some y є L2, xy є L1 } where L1 and L2 are any
4. Consider G whose productions are S aAS | a A SbA | SS | ba Show that S aabbaa and
construct a derivation tree whose yield in aabbaa. [M 5][CO3,PO1,PO2]
Formal Languages and Automata theory
III Year -Department of CSE
1.The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} |
where string s contains even number of 0 and 1
a) 01,0011,010101
b) 0011,11001100
c) ε,0011,11001100
d) ε,0011,11001100
Ans:b
2. A regular language over an alphabet ∑ is one that cannot be obtained from the basic
languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned
Ans:d
3.The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1
b) 3
c) 5
d) 7
Ans:b
4.Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
Ans:d
5.The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and
∑={0,1} is_________
a) 7
b) 6
c) 8
d) 5
Ans:a
6.Given: ∑= {a, b}
L= {xϵ∑*|x is a string combination}
∑4 represents which among the following?
a) {aa, ab, ba, bb}
b) {aaaa, abab, ε, abaa, aabb}
c) {aaa, aab, aba, bbb}
d) All of the mentioned
ans:b
7. Moore Machine is an application of:
a) Finite automata without input
b) Finite automata with output
c) Non- Finite automata with output
d) None of the mentioned
Ans:b
8.For a give Moore Machine, Given Input=’101010’, thus the output would be of length:
a) |Input|+1
b) |Input|
c) |Input-1|
d) Cannot be predicted
Ans:a) |Input|+1
9. In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input
Ans:C
10Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata
Ans: b) Transducers
11.A Language for which no DFA exist is a________
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) Cannot be said
Ans: b) Non-Regular Language
12.What the following DFA accepts?
a) x is a string such that it ends with ‘101’
b) x is a string such that it ends with ‘01’
c) x is a string such that it has odd 1’s and even 0’s
d) x is a strings such that it has starting and ending character as 1
Ans: a) x is a string such that it ends with ‘101’
13Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined
Ans:b
14.Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches
Ans:d
15.Given L= {Xϵ∑*= {a, b} |x has equal number of a, s and b’s}.
Which of the following property satisfy the regularity of the given language?
a) Regularity is dependent upon the length of the string
b) Regularity is not dependent upon the length of the string
c) Can’t be said for a particular string of a language
d) It may depend on the length of the string
Ans:b
16.Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata
and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of
languages accepted by deterministic finite automata and deterministic push-down automata,
respectively.
a.Df ⊂ Nf and Dp b.Df ⊂ Nf and c.Df = Nf and d.Df = Nf
⊂ Np Dp = Np Dp = Np and Dp ⊂ Np
Ans:d.Df = Nf and Dp ⊂ Np
17.δ(A,1) = B, δ(A,0) =A
Δ (B, (0,1)) =C
δ(C,0) = A (Initial state =A)
String=”011001” is transit at which of the states?
a) A
b) C
c) B
d) Invalid String
ans:a
18.Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum
number of states in an equivalent minimized DFA is at least
a.N^2 b.2N c.2^N d.N!
Ans:c
19. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited
Ans :b
20. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
Ans:d
21. δ*(q,ya) is equivalent to .
a) δ((q,y),a)
b) δ(δ*(q,y),a)
c) δ(q,ya)
d) independent from δ notation
Ans:b
22. String X is accepted by finite automata if .
a) δ*(q,x) E A
b) δ(q,x) E A
c) δ*(Q0,x) E A
d) δ(Q0,x) E A
Ans:c
23. Language of finite automata is.
a) Type 0
b) Type 1
c) Type 2
d) Type 3
Ans:d
24. . Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned
Ans:b
25. Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true
d) Statement 1 is false and Statement 2 is also fals
Ans:a
26. An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned.
Ans:c
27. NFA, in its name has ’non-deterministic’ because of :
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the mentioned
Ans:b
28. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m2)
b) O(2m)
c) O(m)
d) O(log m)
Ans:b
29. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
Ans:d
30. It is less complex to prove the closure properties over regular languages using
a) NFA
b) DFA
c) PDA
d) Can’t be said
Ans:NFA
31. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
Ans:c
32: Which among the following can be an example of application of finite state machine(FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
Ans:a
33. L1= {w | w does not contain the string tr }
L2= {w | w does contain the string tr}
Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?
a) 0
b) 1
c) 2
d) Cannot be said
Ans:a
34. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
Ans:a
35. A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011
Ans:a
36. If L1 and L2 are regular languages, which among the following is an exception?
a) L1 U L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned
Ans:d
37. Predict the analogous operation for the given language:
A: {[p, q] | p ϵ A1, q does not belong to A2}
a) A1-A2
b) A2-A1
c) A1.A2
d) A1+A2
Ans:a
38. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
Ans:a
39. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
Ans:b
40. Which of the following is same as the given DFA?
a) (0+1)*001(0+1)*
b) 1*001(0+1)*
c) (01)*(0+0+1)(01)*
d) None of the mentioned
Ans:a
41. Which of the following statements is not true?
a) Every language defined by any of the automata is also defined by a regular expression
b) Every language defined by a regular expression can be represented using a DFA
c) Every language defined by a regular expression can be represented using NFA with e moves
d) Regular expression is just another representation for any automata definition
Ans:b
42. The total number of states required to automate the given regular expression
(00)*(11)*
a) 3
b) 4
c) 5
d) 6
Ans:c
43.Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words
repeated a number of times to produce a new word which also lies within the same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
Ans:b
44. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of
repeating y 0 or more times before checking that they still belong to the language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
Ans:b
45. There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for
some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
Ans:a
46. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0
47. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be
____________ under an operation op.
a) open
b) closed
c) decidable
d) none of the mentioned
Ans:b
48. If L1′ and L2′ are regular languages, then L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
Ans:a
49. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
Ans:c
50. The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
Ans:b
