# SUPERSTARWEBTECH

There is no elevator to success. You have to take the stairs. Take your first steps with SSWT!

# CS402-Theory of Automata Quiz MCQs Lecture 1-22 Midterm Objective Questions CS402-Theory of Automata Quiz  MCQS #Objective #Questions #Midterm

1. The state where there is no way to leave after the entry is called ___

• Davey John locker ✔
• initial state
• final state
• non-final state

2. The recursive method for defining a language has ___ steps.

• one
• two
• three ✔
• four

3. Let S={aa, bb}, then S* will have the ___ string.

• ^ ✔
• abba
• aabbbaa
• bbaab

4. The language of all strings defined over alphabet set = {a, b} that does not end with ‘a’ actually ends with:

• b
• b and ^ ✔
• ^
• ^ and a

5. a(a+b)*b+b(a+b)*a is the RE of language defined over Σ={a, b} is ___

• starting with a and ending in b or starting with b and ending in a ✔
• starting with a and ending in b
• starting with b and ending in a
• starting with a and ending in a

6. Let S = {a, bb, bab, baabb} be a set of strings, which one of the following will not be included in S*?

• baba
• baabbabb
• bbaaabb
• bbbaabaabb ✔

7. Which of the following regular expressions represent same language?
1. (a+ab)*
2. (ba+a)*
3. a*(aa*b)*
4. (a*b*)*

• 1 and 2 ✔
• 1 and 3
• 3 and 4
• 1 and 4

8. According to theory of automata there are ___ types of languages.

• One
• Two ✔
• Three
•  Four

9. Kleene’s Theorem Part III expresses the relationship between ___

• FA and TG
• TG and RE
• RE and FA ✔
• FA and RE

10. Kleene’s Theorem Part II expresses the relationship between ___

• FA and TG
• TG and RE ✔
• RE and FA
• FA and RE
11. In case of finite automation there ___ be a transaction on each ___ for every letter of the alphabet set.
• must, state ✔
• may be, state
• often, edge
• must, edge
12. Which of the following is the minimal number of states for a finite automation accepting the language of all strings defined over any alphabet set?
• 1 ✔
• 2
• 3
• 4
13. Two FAs are said to be equivalent if they ___
• accept null string
• accept the same language ✔
• accept different language
• None
14. The length of the string “AbBAbcd” defined over Σ= {Ab, B, c, d} is ___
• three
• four
• five ✔
• six
15. The language of all strings defined over alphabet set = {x, y} having triple x’s or triple y’s will have the minimum strings with length of:
• 1
• 2
• 3 ✔
• 4
16. For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the ___
• same ✔
• different
• R(S U T) is Greater
• None
17. How many types of machines exist, generating output for specific input?
• 1
• 2 ✔
• 3
• 4
18. In the context of make NFA for the concatenation of FA1 and FA2 (FA2 accepting null string), which of the following option is correct?
• Initial states in both FAs
• FA2 having initial state only
• Final states in both FAs ✔
• FA2 having final states only
19. Let L be the language of all strings, defined over Σ = {0,1}, ending in 10. Which of the following strings are indistinguishable with respect to L with z being 0?
• 100, 101
• 111, 101 ✔
• 110, 101
• 010, 101
20. While developing NFA for the union of FA1 and FA2, if there is a loop of ‘a’ at the initial state of FA1 then the new initial state will have a transition for ‘a’ that goes straight to:
• the initial state of FA1 ✔
• the initial state of FA1*FA1
• the initial state of FA2
• the final state of FA1
21. The language {a, ab, aba, bab} is ___
• regular ✔
• recursive
• infinite
• irregular
22. In NFA, if null word (lambda) is allowed to be a label of an edge, then that NFA is called ___
• NFA with one string
• NFA with two strings
• NFA without null string
• NFA with null string ✔
23. If we have an NFA having 3 states, and we convert that NFA to an FA. The resultant FA will contain ___ states.
• 2
• 3
• 4 ✔
• 5
24. FA corresponding to an NFA can be built by introducing a state corresponding to the combination of states, for a letter having
• no transition at certain state
• one transition at certain state
• more than one transitions at certain state ✔
• None
25. How many new states are introduced while developing NFA for the closure of an FA?
• one ✔
• two
• three
• four
26. Suppose we have the regular expression:
aa(a+b+c)*bb(a+b+c)*cc
Which of the following will not be generated by the given RE?

• aabbcc
• aaabcbbcbacc
• aaabbbbccc
• aaaabbccbc ✔

27. If r1 = (aa + bb) and r2 = (a + b) then the language (aa+bb)(a+b) will be generated by ___

• (r1)(r2) ✔
• (r1+r2)
• (r2)(r1)
• (r1)*

28. Suppose we have an alphabet set having four symbols, how many transitions will be there on each state of a finite automation for any language defined over the given alphabet?

• 1
• 2
• 3 ✔
• 4

29. FA is also called

• TG
• GTG
• NFA
• DFA ✔

30. If S={a}, then S+ will be ___

• {a, aaa, aaaa, aaaaa, …}
• {a, aa, aaa, aaaa, …} ✔
• {a, aaa, aaaaa, aaaaaaa, …}
• {aa, aaaa, aaaaaa, aaaaaaaa, …}

31. There can be more than ___ FA for a certain language but for ___ FA there is only one language associated with it.

• one, one ✔
• one, two
• two, three
• two, one

32. When ODD language is expressed by an FA, then it will have minimum ___ states.

• one ✔
• two
• three
• four

33. Which of the following statement is NOT true about TG?

• There exists exactly one path for certain string ✔
• There may exist more than one paths for certain string
• There may exist no path for certain string
• There may be no final state

34. Consider the following RE:
a(a+b)b*
All of the following words are accepted except ___

• aab
• abb
• aa
• aaa ✔

35. If an FA has 3 states and 2 letters in the alphabet, then it will have ___ number of transitions

• 4
• 5
• 6 ✔
• 7

36. Which of the following statement is true about GTG?

• Transitions are based on input letters
• Transitions are based on specified substrings
• Transitions are based on regular expressions ✔
• Transitions are based on alphabet set

37. Length of EVEN-EVEN language is ___

• Even
• Odd
• Sometimes even & sometimes odd
• Such language does not exist

38. The language having even number of a’s and even number of b’s defined over S = {a, b} is called ___

• EVEN-EVEN
• ODD-ODD
• PALINDROME
• FACTORIAL

39. Which of the following diagram is very rigid in order to express any language?

• TG
• NFA
• GTG
• FA

40. Which one of the following is the RE for the language defined over Σ = {a, b} having all the words starting with a?

• (a+b)*
• aa(a+b)+
• a(a+b)*
• a*(a+b)

41. Which one of the following string is a part of EQUAL language?

• aabbba
• babab
• ababab
• aabbaa

42. Keeping in view the language of all strings ending with ‘a’, for which symbol we will take a loop on the final state of its transition diagram?

• a
• b
• c
• d

43. Which is false about the PALINDROME LANGUAGE?

• Every word is reverse of itself
• It is an infinite language
• FA can be build for it
• None

44. The FA can be drawn for the regular expression (a+b)* with minimum ___ state(s)

• 1
• 2
• 3
• 4

45. How many states of a finite automation will be final for accepting L = {^, b, bb, bbb}?

• 1
• 2
• 3
• 4

46. FA stands for ___

• Finite Auotomation
• Fixed Automation
• False Automation
• Functional Automation

47. Which of the following string belongs to the language of the regular expression (aa*b)*?

• baabab
• abbbaa
• aaaaaa
• aabaab

48. What is false about the term alphabet?

• It is a finite set of symbols
• It is usually denoted by Greek letter sigma
• It can be an empty set
• Strings are made up of its elements

49. Which of the following statement is NOT true?

• FA can be considered to be an NFA
• FA can be considered to be an NFA with null string
• NFA can be considered to be a TG
• TG can be considered to be an NFA

50. We can create an equivalent ___ for a language for which we create an ___

• FA, NFA
• NFA, FA
• FA, GTG
• None

51. In which of the following machine, the length of output string is the same to that of input string?

• Moore machine
• Finite automation with output
• Mealy machine
• Non-deterministic finite automation

52. A ___ with “n” states must accept at least one string of length greater than “n”

• DFA
• RE
• Irregular language
• Irrelevant languge

53. While developing NFA for the union of FA1 and FA2, there will be ___ transition/transitions for both ‘a’ and ‘b’ on the new initial state.

• Single
• Only one
• Only three
• Multiple

54. Keeping in view the discussion by Martin, how many states are required to recognize the language of all strings defined over Σ = {a, b}, with ‘b’ being the second letter from right?

• 6
• 7
• 8
• 9

55. In order to make NFA for the union of FA1 and FA2, the final state/states of:

• both FAs should be linked
• FA1 have a transition to the final state of FA2
• both FAs should be left intact
• FA2 have a transition to the final state FA1
56. FA corresponding to an NFA can be built by introducing an empty state for a letter having
• no transition at certain state
• one transition at certain state
• two transitions at certain state
• more than two transitions at certain state
57. If we have only one state, having no transition for input letters, then i is an example of:
• RE
• FA
• TG
• NFA
58. In the context of make NFA for the concatenation of FA1 and FA2 (FA1 accepting null string), which of the following option is correct?
• Initial states in both FAs
• FA2 having initial state only
• FA2 havig final state only
• Final states in both FAs
59. In which of the following machine, the length of output string is 1 more than that of input string?
• Mealy machine
• Moore machine
• Finite automation with output
• Non-deterministic finite automation
60. An ___ can be considered to be an intermediate structure between Finite automation and Trnsition Graph.
• RE
• GTG
• NFA
• None
61. We cannot construct an NFA for the language of ___ defined over alphabet set {a, b}
• Even Even
• Odd
• Palindromes
• Integers
62. The language of all strings defined over Alphabet set = {x, y} that ends with same letter will have the maximum length of :
• 1
• 2
• 3
• infinite
63. Reverse of string “BcAbed” defined over = {Ab, Bc, d, e} is ___
• debABc
• deAbBc
• deAbcB
• debAcB
64. If two RE’s generate same language then these RE’s are called ___
• Same RE
• Equal RE
• Similar RE
• Equivalent RE
65. Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to initial state of:
• FA1 only
• FA2 only
• FA1 or FA2
• FA1 and FA2
66. If r1 and r2 are regular expressions then (r1*r2) is a/an ___
• FA
• TG
• GTG
• Regular expression
67. Kleene’s Theorem part I expresses the relationship between ___
• FA and TG
• TG and RE
• RE and FA
• FA and RE
68. In the context of make NFA for the concatenation of FA1 and FA2 (Both FAs accepting null string) which of the following option is correct?
• Final states in both FAs
• Initial states in both FAs
• FA2 having initial state only
• FA2 having final state only
69. Let L be the language of all strings, defined over = {0, 1} ending in 111. Which of the following strings are indistinguishable with respect to L with z being 11?
• 111, 101
• 100, 101
• 110, 101
• 010, 101
70. If we have a finite language and the number of states in the FA is n then the maximum number of letters in the each word of the language that will be accepted by the given FA will be:
• 1
• n-1
• n+1
• n
71. Which of the following statements is true about NFA with null string?
• Infinite states
• infinite set of letters
• Infinite set of transitions
• Transition of null string is allowed at any stage
72. Which of the following state is introduced while developing NFA for the closure of an FA?
• Simply an initial state
• Final state
• An initial state which should be final as well
• An initial state with loop for all letters
73. In order to make NFA for the union of FA1 and FA2, the new initial state should be linked to:
• initial and final states of FA1 and FA2 respectively
• initial states of both FAs
• initial state of FA1 only
• final and initial states of FA1 and FA2 respectively