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
