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.

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

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

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.

9. Kleen'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?

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 ___

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:

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?

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.

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?

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?

29. FA is also called

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.

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 ___

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

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?

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?

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)

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

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?

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:

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.

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 :

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:

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