Computer Science - Automata Theory
Quiz-summary
0 of 70 questions completed
Questions:
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
Information
This is MCQs of Computer Science Subject.
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading...
You must sign in or sign up to start the quiz.
You have to finish following quiz, to start this quiz:
Results
0 of 70 questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 points, (0)
Categories
- Not categorized 0%
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- Answered
- Review
-
Question 1 of 70
1. Question
The word ‘formal’ in formal languages means
Correct
Incorrect
-
Question 2 of 70
2. Question
Let A = {0, 1} The number of possible strings of length ‘n’ that can be formed by the elements of the set A is
Correct
Incorrect
-
Question 3 of 70
3. Question
Choose the correct statements.
Correct
Incorrect
-
Question 4 of 70
4. Question
The major difference between a Moore and a Mealy Machine is that
Correct
Incorrect
-
Question 5 of 70
5. Question
Choose the correct statements.
Correct
Incorrect
-
Question 6 of 70
6. Question
The recognizing capability of NDFSM and DFSM
Correct
Incorrect
-
Question 7 of 70
7. Question
FSM can recognize
Correct
Incorrect
-
Question 8 of 70
8. Question
Pumping lemma is generally used for proving
Correct
Incorrect
-
Question 9 of 70
9. Question
Which of the following are not regular?
Correct
Incorrect
-
Question 10 of 70
10. Question
Which of the following pairs of regular expressions are equivalent?
Correct
Incorrect
-
Question 11 of 70
11. Question
pic the correct statements.
The logic of Pumping lemma is a good example ofCorrect
Incorrect
-
Question 12 of 70
12. Question
The basic limitation of an FSM is that
Correct
Incorrect
-
Question 13 of 70
13. Question
Palindromes can’t be recognized by any FSM because
Correct
Incorrect
-
Question 14 of 70
14. Question
An FSM can be considered TM
Correct
Incorrect
-
Question 15 of 70
15. Question
Tm is more powerful than FSM because
Correct
Incorrect
-
Question 16 of 70
16. Question
The FSM pictured in Fig. 6.1 recognizes
Correct
Incorrect
-
Question 17 of 70
17. Question
The FSM pictured in Fiq. 6.2 is a
Correct
Incorrect
-
Question 18 of 70
18. Question
The above machine
Correct
Incorrect
-
Question 19 of 70
19. Question
The language of all words (made up of a’s and b’s) with at least two a’s can be described by the regular expression
Correct
Incorrect
-
Question 20 of 70
20. Question
Which of the following pairs of regular expression are not equivalent?
Correct
Incorrect
-
Question 21 of 70
21. Question
Consider the two FSM’s in Fig 6.3.
Pick the correct statement.Correct
Incorrect
-
Question 22 of 70
22. Question
Set of regular languages over a given alphabet set, is not closed under
Correct
Incorrect
-
Question 23 of 70
23. Question
The machine pictured in Fig. 6.4.
Correct
Incorrect
-
Question 24 of 70
24. Question
For which of the following application regular expressions can’t be used?
Correct
Incorrect
-
Question 25 of 70
25. Question
The FSM pictured in Fig. 6.5 recognizes
Correct
Incorrect
-
Question 26 of 70
26. Question
Any given Transition graph has an equivalent
Correct
Incorrect
-
Question 27 of 70
27. Question
The following CFG
s→ as | bs | a | b
is equivalent to the regular expressionCorrect
Incorrect
-
Question 28 of 70
28. Question
Any string of terminals that can be generated by the following CFG
S → XY
X → aX | bX | a
Y → Ya | Yb | aCorrect
Incorrect
-
Question 29 of 70
29. Question
The following CFG
S → aB | bA
A → b | aS | bAA
B → b | bS | aBB
generates strings of terminals that haveCorrect
Incorrect
-
Question 30 of 70
30. Question
LET L(G) denote the language generated by the grammar G. TO prove set A = L (G),
Correct
Incorrect
-
Question 31 of 70
31. Question
The set {anbn |n = 1,2,3…} can be generated by the CFG
Correct
Incorrect
-
Question 32 of 70
32. Question
Choose the correct statements.
Correct
Incorrect
-
Question 33 of 70
33. Question
Which of the following CFG’s can’t be simulated by an FSM?
Correct
Incorrect
-
Question 34 of 70
34. Question
CFG is not closed under
Correct
Incorrect
-
Question 35 of 70
35. Question
The set A= {anbnan | n= 1, 2, 3, . . . ) is an example of a grammar that is
Correct
Incorrect
-
Question 36 of 70
36. Question
Let L1 = {anbnam | m, n = 1, 2, 3 . . . }
L2 = ( anbmam | m, n = 1, 2, 3, . . . }
L3 = { anbnan | n = 1, 2, 3, . . . . }
Choose the correct statements.
Correct
Incorrect
-
Question 37 of 70
37. Question
L = { anbnan | n = 1, 2, 3, . . . . } is an exampble of a language that is
Correct
Incorrect
-
Question 38 of 70
38. Question
The intersection of a CFL and a regular language
Correct
Incorrect
-
Question 39 of 70
39. Question
A PDM behaves like an FSM when the number of auxiliary memory it has is
Correct
Incorrect
-
Question 40 of 70
40. Question
A PDM behave like a TM when the number of auxiliary memory it has is
Correct
Incorrect
-
Question 41 of 70
41. Question
Choose the correct statements.
Correct
Incorrect
-
Question 42 of 70
42. Question
Which of the following is accepted by an NDPDM, but not by a DPDM?
Correct
Incorrect
-
Question 43 of 70
43. Question
CSG can be recognized by a
Correct
Incorrect
-
Question 44 of 70
44. Question
Choose the correct statemetns.
Correct
Incorrect
-
Question 45 of 70
45. Question
Choose the correct statements
Correct
Incorrect
-
Question 46 of 70
46. Question
Bounded minimization is a technique for
Correct
Incorrect
-
Question 47 of 70
47. Question
Which of the following is not primitive recursive but computable?
Correct
Incorrect
-
Question 48 of 70
48. Question
Which of the following is not primitive recursive but partially recursive?
Correct
Incorrect
-
Question 49 of 70
49. Question
Choose the correct statements.
Correct
Incorrect
-
Question 50 of 70
50. Question
A language L for which there exist a TM, T, that accepts every word in L and either rejects or loops for every word that is not in L, is said to be
Correct
Incorrect
-
Question 51 of 70
51. Question
Choose the correct statements.
Correct
Incorrect
-
Question 52 of 70
52. Question
Choose the correct statements.
Correct
Incorrect
-
Question 53 of 70
53. Question
Pick the correct answers.
Universal TM influenced the concept ofCorrect
Incorrect
-
Question 54 of 70
54. Question
The number of internal states of a UTM should be at least
Correct
Incorrect
-
Question 55 of 70
55. Question
The number of symbols necessary to simulate a TM with m symbols and n states is
Correct
Incorrect
-
Question 56 of 70
56. Question
The statement – “A TM can’t solve halting problem” is
Correct
Incorrect
-
Question 57 of 70
57. Question
Any TM with m symbols and n states can be simulated by another TM with just 2 symbols and less than
Correct
Incorrect
-
Question 58 of 70
58. Question
If there exists a TM which when applied to any problem in the class, terminates if the correct answer is yes, and may or may not terminate otherwise is said to be
Correct
Incorrect
-
Question 59 of 70
59. Question
The number of stats of the FSM, required to simulate the behavior of a computer, with a memory capable of storing ‘m’ words, each of length ‘n’ bits it
Correct
Incorrect
-
Question 60 of 70
60. Question
The vernacular language English, if considered a formal language, is a
Correct
Incorrect
-
Question 61 of 70
61. Question
Let P, Q and R be three languages. If P and R are regular and if PQ = R, then
Correct
Incorrect
-
Question 62 of 70
62. Question
Consider the grammar
S → PQ | SQ | PS
P → X
Q → Y
To get a string of n terminals, the number of productions to be used isCorrect
Incorrect
-
Question 63 of 70
63. Question
Choose the correct statements.
A class of languages that is closed underCorrect
Incorrect
-
Question 64 of 70
64. Question
The following grammar is
S → aab | baac | aBS → aS | b
S → abb | ab
ba → bdb | b
Correct
Incorrect
-
Question 65 of 70
65. Question
Which of the following definitions generates the same language as L, where
L = {xnyn, n ≥ 1} ?
I. E → xEy | xy
II. xy | x+xyy+
II. x+y+
Correct
Incorrect
-
Question 66 of 70
66. Question
A finite state machine with the following state table has a single input x and a single output z.
Present state | Next state, z
x=1 | X=0
A D,0 | B,0
B B,1 | C,1
C B,0 | D,1
D B,1 | c,0
If the initial state is unknown, then the shortest input sequence to reach the final state C isCorrect
Incorrect
-
Question 67 of 70
67. Question
Let A = {0,1} and L + A* Let R = {0n1n , n>0} The languages L U R and R are respectively
Correct
Incorrect
-
Question 68 of 70
68. Question
Which of the following conversion is not possible algorithmically?
Correct
Incorrect
-
Question 69 of 70
69. Question
An FSM can be used to add two given integers. This remark is
Correct
Incorrect
-
Question 70 of 70
70. Question
A CFG is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A → BC or A → a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of productions to be used is
Correct
Incorrect