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

- must, state ✔
- may be, state
- often, edge
- must, edge

- 1 ✔
- 2
- 3
- 4

- accept null string
- accept the same language ✔
- accept different language
- None

- three
- four
- five ✔
- six

- 1
- 2
- 3 ✔
- 4

- same ✔
- different
- R(S U T) is Greater
- None

- 1
- 2 ✔
- 3
- 4

- Initial states in both FAs
- FA2 having initial state only
- Final states in both FAs ✔
- FA2 having final states only

- 100, 101
- 111, 101 ✔
- 110, 101
- 010, 101

- the initial state of FA1 ✔
- the initial state of FA1*FA1
- the initial state of FA2
- the final state of FA1

- regular ✔
- recursive
- infinite
- irregular

- NFA with one string
- NFA with two strings
- NFA without null string
- NFA with null string ✔

- 2
- 3
- 4 ✔
- 5

- no transition at certain state
- one transition at certain state
- more than one transitions at certain state ✔
- None

- one ✔
- two
- three
- four

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

- no transition at certain state
- one transition at certain state
- two transitions at certain state
- more than two transitions at certain state

- RE
- FA
- TG
- NFA

- Initial states in both FAs
- FA2 having initial state only
- FA2 havig final state only
- Final states in both FAs

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

- RE
- GTG
- NFA
- None

- Even Even
- Odd
- Palindromes
- Integers

- 1
- 2
- 3
- infinite

- debABc
- deAbBc
- deAbcB
- debAcB

- Same RE
- Equal RE
- Similar RE
- Equivalent RE

- FA1 only
- FA2 only
- FA1 or FA2
- FA1 and FA2

- FA
- TG
- GTG
- Regular expression

- FA and TG
- TG and RE
- RE and FA
- FA and RE

- Final states in both FAs
- Initial states in both FAs
- FA2 having initial state only
- FA2 having final state only

- 111, 101
- 100, 101
- 110, 101
- 010, 101

- 1
- n-1
- n+1
- n

- Infinite states
- infinite set of letters
- Infinite set of transitions
- Transition of null string is allowed at any stage

- Simply an initial state
- Final state
- An initial state which should be final as well
- An initial state with loop for all letters

- 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