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

Author

Anam Afzal

Anam Afzal

Hi, I'm a Pakistani freelancer with a passion for helping businesses achieve their online goals through no-code solutions. I specialize in WordPress customization and ManyChat automation, and I'm always on the lookout for new ways to use technology to make businesses more efficient and successful. I'm also a big believer in the power of no-code tools to democratize technology and make it accessible to everyone. I'm passionate about sharing my knowledge and helping others learn how to use no-code tools to create their own websites, automate their workflows, and grow their businesses. If you're looking for a reliable and experienced no-code developer, I'm here to help. Please feel free to contact me to discuss your project requirements.
SHARE THIS POST