Theory of Automata MCQ’s
By
Prof ALI RAZA MUSHTAQ
+92317001200
[email protected] Dedicated to My Wife.
Mrs. Sbahat Ali.
Publish: Saivi © May 15, 2020
1. Palindrome mean String read from Left to Right o Right to left
results are different
(a) True
(b) False
(c) Don't Know
(d) Statement Wrong
2. When we concatenate two FA remove second FA final state and
remove first FA initial state
(a) True
(b) False
(c) Don't Know
(d) Wrong Statement
3. In Concatenation order doesn't matter FA1 concatenate With FA2
as well as F2 concatenate with FA1
(a) True
(b) False
(c) Don't Know
(d) Statement Wrong
4. Concatenation mean Append or Attached
(a) True
(b) Don't Know
(c) Statement Wrong
(d) False
5. A regular Language over an Alphabet sigma is one that can't be
obtained from the basic language using the operation.
(a) Union
(b) Concatenation
(c) Kleene *
(d) All of the mentioned
6. Number of states required to accept string ends with 10
(a) 1
(b) 3
(c) 4
(d) 6
7. Regular expression for all string start with ab and ends with bba is
(a) aba*b*bba
(b) ab(ab)*bba
(c) ab(a+b)*bba
(d) All of the mentioned
8. Language of a Automata is
(a) If it is accepted by automata
(b) If it halts
(c) If automata touch final state in its life time
(d) None
9. Kleene asterisk start with 1 to infinity.
(a) True
(b) False
(c) Don't Know
(d) Wrong Statement
10. Kleene star start with 0 to infinity
(a) True
(b) False
(c) Don't Know
(d) Wrong Statement
11. (aa + bb) is a Regular language
(a) True
(b) False
(c) Don't Know
(d) Wrong Statement
12. Converting each of the final states of F to non-final states and
old non-final states of F to final states, FA thus obtained will reject
every string belonging to L and will accept every string, defined
over ∑, not belonging to L. is called
(a) Transition Graph of L
(b) Regular expression of L
(c) Complement of L
(d) Finite Automata of L
13. If L1 and L2 are two regular languages, then L1 U L2 is not a
regular.
(a) True
(b) False
(c) Don't Know
(d) Wrong Statement
14. L= language of words containing even number of a’s. Regular
Expression is
(a) (a+b)aa(a+b)
(b) (b+aba)
(c) a+bbaaba
(d) (a+b)ab(a+b)
15. The language that can be expressed by any regular expression
is called a Non regular language.
(a) True
(b) False
(c) Don't Know
(d) Wrong Statement
16. The languages -------------- are the examples of non regular
languages.
(a) PALINDROME and PRIME
(b) PALINDROME and EVEN-EVEN
(c) EVEN-EVEN and PRIME
(d) FACTORIAL and SQURE
17. The language Q is said to be quotient of two regular languages P
and R, denoted by---if
(a) PQ=R.
(b) R=Q/P
(c) Q=R/P
(d) Q=P/R
(e) P=R/Q
18. For language L defined over {a, b}, then L partitions {a, b} into
classes
(a) Infinite
(b) Finite
(c) Distinct
(d) Non-distinct
19. To examine whether a certain FA accepts any words, it is
required to seek the paths from ------- state.
(a) Final to initial
(b) Final to final
(c) Initial to final
(d) Initial to initial
20. Below given TG has _____________ RE
(a) (aa+aa+(ab+ab)(aa+ab)(ab+ba))
(b) (aa+bb+(ab+ba)(aa+bb)(ab+ba))
(c) (aa+bb+(ab+ba)+(bb+aa)+(ab+ba))
(d) None of these
21. Match the following Regular Expressions (RE's) with
corresponding Finite Automata (FA's) given above.
(a) aa*b(aa*b)*
(b) (a+b)*a(a+b)*b(a+b)*
(c) none of them
(d) both of them correct
22. Match the following Regular Expressions (RE's) with
corresponding Finite Automata (FA's) given above.
(a) aa*b(aa*b)*
(b) (a+b)*a(a+b)*b(a+b)*
(c) none of them
(d) both of them correct
23. If FA1 corresponds to (a+b)* then FA1 must accept ________
string/strings. Select correct option:
(a) No Odd
(b) length
(c) Their Exist only Two
(d) All
24. Let FA3 be an FA corresponding to FA1FA2, then the final state
of FA3 must correspond to the final state of
(a) FA1 only
(b) FA2 only
(c) FA1 or FA2
(d) FA1 and FA2
25. Let FA3 be an FA corresponding to FA1+FA2, then the initial
state of FA3Must correspond to the initial state of
(a) FA1 only
(b) FA2 only
(c) FA1 or FA2
(d) FA1 and FA2
26. A Language for which no DFA exist is a________
(a) Regular Language
(b) Non-Regular Language
(c) May be Regular
(d) Cannot be said
27. 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 string such that it has starting and ending character as 1
28. What does the following figure most correctly represents?
(a) Final state with loop x
(b) Transitional state with loop x
(c) Initial state as well as final state with loop x
(d) Insufficient Data
29. Which of the following will not be accepted by the following DFA?
(a) ababaabaa
(b) abbbaa
(c) abbbaabb
(d) abbaabbaa
30. Can a DFA recognize a palindrome number?
(a) Yes
(b) No
(c) Maybe
(d) Can’t be determined
31. Subset Construction method refers to:
(a) Conversion of NFA to DFA
(b) DFA minimization
(c) Eliminating Null references
(d) -^- NFA to NFA
32. The number of transitions required to convert the following into
equivalents DFA:
(a) 1
(b) 4
(c) 2
(d) 3
33. A binary string is divisible by 4 if and only if it ends with:
(a) 100
(b) 1000
(c) 1100
(d) 0011
34. 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) True,True
(b) False, False
(c) True, False
(d) False, True
35. 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
36. Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.
Statement 2: Every DFA is automatically an NFA
(a) True, True
(b) False, False
(c) True, False
(d) False, True
37. If two finite state machines are equivalent, they should have the
same number of
(a) states
(b) edges
(c) states and edges
(d) none of these
38. Which of the following are not regular?
(a) String of 0's whose length is a perfect square
(b) Set of all palindromes made up of 0's and 1's
(c) Strings of 0's, whose length is a prime number
(d) All of these
39. Finite state machine can recognize
(a) any grammar
(b) only context-free grammar
(c) Both (a) and (b)
(d) only regular grammar
40. Regular expression corresponding to the state diagram given in
the figure is
(a) (0+1(1 + 01)* 00)*
(b) (1 + 0 (0 + 10) 00)*
(c) (0 + 1 (1 + 10) 00)*
(d) (1 + 0(1 + 00) 11)*
41. The finite automata are called NFA when there exists _________
for a specific input from current state to next state
(a) Single path
(b) Multiple paths
(c) Only two paths
(d) None
42. Regular expression for all strings starts with ab and ends with ba
is.
(a) aba*b*ba
(b) ab(ab)*ba
(c) ab (a+b)*ba
(d) All of the mentioned
43. Which of the following are the examples of finite state machine
system?
(a) Control Mechanism of an elevator, Traffic Lights
(b) Combination Locks
(c) Digital Watches
(d) Both a & b
44. The finite automata is called DFA when there exists ________for
a specific input from current state to next state
(a) Single path
(b) Multiple paths
(c) Only two paths
(d) None
45. Choose the RE of Given Below Graph:
(a) (a+b)*
(b) a* + b*
(c) (ab + ba)*
(d) None of these
46. Every FA Should be:
(a) DFA
(b) NDFA
(c) DFA & NDFA
(d) None of These
47. ∑ = {a, abc, ad, ali, fuse, box} has Letter______
(a) 6
(b) 16
(c) 8
(d) None of These
48. Below given DFA accept the __________ no of Strings
(a) one
(b) two
(c) three
(d) four
49. Every finite language can be expressed by FA's. This s ______.
(a) True
(b) False
(c) Depend on Language
(d) None of These
50. Regular sets are closed under union, concatenation and Kleene
closure.
(a) True
(b) False
(c) Depends on regular set
(d) Can’t say
51. The maximum number of transitions which can be performed
over a state in a DFA? ∑= {a, b, c}
(a) 1
(b) 2
(c) 3
(d) 4
