Theory of computer science
Theory Of Computer Science
MC0082
1Marks
1. A set A is said to be a proper subset of B if there exist an element of B which is not a element of A.
a A is subset of B
b B is subset of A
c A is proper subset of B
d B is proper subset of A
2. A set which contains a single element is called __
a Empty Set
b Singleton
c Null Set
d Union Set
3. Symmetrical difference is also known as
a Boolean sum of two sets
b Boolean difference of two sets
c Subtraction of two sets
d None of the above
4. A relation is said to be an equivalence relation if it is
a Reflexive
b Transitive
c Symmetric
d All of the above
5. ___________ is the technique of defining a set or an algorithm in terms of itself
a Function
b Subroutine
c Relation
d Recursion
6. If A & B are infinite sets and |A| > |B|, then there is no one-to-one function from A to B. This sates the
a Pigeonhole Principle
b Diagonlaization Principle
c Proof of Contrapositive
d Poof by contradiction
7. A tree T is said to be a _____________ of a connected graph G if T is a subgraph of G and T contains all the vertices of G.
a Spanning Tree
b Binary Graph
c Spanning graph
d Binary Tree
8. A ___________ consists of non empty set V (the elements of V(the elements of V are normally denoted by v1,v2, …) and a set E(the elements of E are normally denoted by e1, e2, ……) and a mapping Y that maps every element of E onto an ordered pair (vi,vj) of elements from V.
a Digraph
b Graph
c Bigraph
d None of the above
9. A grammar is defined by a ________
a 1 tuple, VT
b 2 tuple, VT, VN
c 3 tuple, VT, VN,S
d 4 tuple, VT, VN,S, f
10. a grammar is said to be _________-when every production in f is of the form a®b having ½a½£|b| or S®^
a Bitonic
b Context free
c Unrestricted
d Monotonic
11. It helps to determine the next output of the automation system.
a State relation
b Output Relation
c States
d Input
12. An automata system in which the output depends only on the present input is called a _________
a Mealy Machine
b Deterministic Finite Automata
c Non Deterministic Finite Automata
d Moore Machine
13. In turing machine Strings are fed into the device by means of _________
a Input tape
b Output tape
c Finite Control
d Read/Write Head
14. It can sense what symbol is written at any position on the input tape by means of a movable reading head
a Input Tape
b Output tape
c Finite Control
d Read/Write Head
15. In this type of automata there may be several possible next states for each of input value and states.
a Finite Automata
b Deterministic Finite Automata
c Non Deterministic Finite Automata
d None of the above
16. d(q,^) =
a q
b ^
c q^
d None of the above
17. ________is a regular expression denoting an empty language
a f
b ^
c { }
d None of the above
18. ____ is a regular expression indicates the language containing an empty string.
a f
b ^
c { }
d None of the above
19. x* represents the set _________
a {^, x, xx, xxx, xxxx}
b {^, x, xx, xxx, xxxx……..}
c {x, xx, xxx, xxxx}
d None of the above
20. A _____________ is a set of strings of symbols that can be generated by a regular grammar using certain operations such as union, concatenation and intersection.
a Regular expression
b Expression
c Linear Expression
d None of the above
21. A grammar which has most non terminal on the right side f any production without restriction on the position of this non terminal is called __________
a Regular grammar
b Context free Grammar
c Linear Grammar
d None of the above
22. Regular expression to accept a language consisting of strings of a’s and b’s of even length
a (aa+bb+ba+ab)*
b (ab+bb)*
c (a+b)*
d None of the above
23. Intersection of two regular language is ______
a Linear
b Square
c Regular
d None of the above
24. Production A®bB stands for
a d(A,b)=B
b d(A,^)=A
c d(A,bB)=A
d d(A,b)=A
25. According to pigeonhole principle, there are n objects and m boxes where number of objects _________, then at least one box will have more than one object
a n>m
b n<m
c n=m
d None of these
26. _____________ is an ordered tree in which each vertex is labeled with the left sides of a production and which the children of a vertex represent its corresponding right sides.
a Decision Tree
b Binary Tree
c Derivation Tree
d None of the above
27. The another method to display productions of context free grammar is
a Forward-Naur Form
b Backus-Naur Form
c Inward Naur Forms
d None of the above
28. Every non-terminal symbol is enclosed in Backus-Naur form is enclosed in
a { }
b [ ]
c < >
d | |
29. The turing machine can do
a. Halt and accept by entering into final state
b. Halt & Reject : This is possible if the transition is not defined
c. TM will never halt and enter into an infinite loop.
d. One of the above
30. ______ represents a set of tape symbols
a a
b b
c t
d å
31. The pumping lemma fro CFL’s is used to prove that certain languages are _________-
a Context Free
b Regular
c Not Context Free
d Not Regular
32. A language accepted by an empty stack is
a N(M) ={w | (q0,w,Z0) |-*(p,^,^)}
b N(M) ={w | (q0,w,Z0) |-*(p,z,w)}
c N(M) ={w | (q0,w,Z0) |-*(p,^,z)}
d None of the above
33. Explain the meaning of (q, aw, Za) q in
a current state
b final state
c halt state
34. aw stands for
a Output string
b aw the string to be processed
c Null String
d None of the above
35. Za stands for
a The current contents of the stack with Z as the topmost symbol of the stack
b The current contents of the stack.
c The contents of the string processed
d None of the Above
36. If an arbitrary number of moves are sued to move from one configuration to another then the moves are denoted by the symbol
a |-*
b |-+
c |-p
d Both a, b
37. The nodes of the graph represented by two concentric circles are the _________ states of the PDA
a Current State
b Initial State
c Final State
d Halt State
38. A grammar is ________ if and only if there exist at least one string wÎVT,fro which two or more different derivation trees exist by applying either the left most derivation or right most derivation
a Right Linear Grammar
b Ambiguous Grammar
c Left Linear Grammar
d Non Linear Grammar
39. The ________- symbol is used instead of ® and should be read as “isdefined as “.
a :=
b ::=
c =
d ==
40. The order of evolution of a regular expression is a __________
a Regular expression
b Linear Expression
c Context Free Expression
d Left Linear Expression
2 marks
41. True/False
1. Any polynomial function is Big-oh of the power function of its lowest order term or of any larger power function
2. Big O estimates will be developed for the factorial function and its algorithm.
a. Both are true
b. Both are false
c. 1 is true
d. 2 is true
42. True/False
i) An open walk, in which no vertex appears more than once, is called a path or simple path
ii) Vertices with which walk begins and ends are called the intermediate vertices of the walk
a. Both are true
b. Both are false
c. 1 is true
d. 2 is true
43. Let G=( VT, VN,S, f) be a grammar. For
s,Y Î (VN È VT)*- {empty string}, s is said to be a _________ of Y, if there are strings f1 & f2 such that_________________________ and a® b is a production of G
a. direct derivative, Y=f1 a f2, s=f1 b f2
b. indirect derivative,Y=f2 a f1, s=f1 b f2
c. indirect derivative, Y=f1 a f2, s=f1 b f2
d. None of the above
44. Suppose G=({S,A,B}, {0,1}, f,S) where f consists of productions S®0AB0, A®10AB1, B®A01, 0A®100 and 1B1®0101. Then w = ___________ is in L(G)
a. 100100100100101
b. 100100001001101
c. 100011101101010
d. 100110100011010
45. True/False
i) Every monotonic grammar G is equivalent to type 1 Grammar
ii) A sentential from is any derivative of the unique non terminal symbol S
a. Both are true
b. 1 is true
c. 2 is true
d. Both are false
46.
|
q2 |
|
q0 |
|
q1 |
0 0 0,1
Start 1 1 Final
a. q1
b. q0
c. q2
d. None of the above
47. The state table for the fig used in above question.
a
|
States S |
0 |
1 |
|
q0 |
q0 |
q1 |
|
q1 |
q1 |
q2 |
|
q2 |
q2 |
q2 |
b
|
States S |
0 |
1 |
|
q0 |
q1 |
q2 |
|
q1 |
q1 |
q2 |
|
q2 |
q2 |
q2 |
c
|
States S |
0 |
1 |
|
q0 |
q1 |
q2 |
|
q1 |
q0 |
q2 |
|
q2 |
q1 |
q0 |
d
|
States S |
0 |
1 |
|
q0 |
q2 |
q1 |
|
q1 |
q1 |
q0 |
|
q2 |
q2 |
q1 |
48. Given the strings u=a2bab & v=bab2, The string uv =_________ and lu=__
a. bab2a2bab, 8
b. a2baba2bab,10
c. a2babbab2, 9
d. None of the above
49. True/False
i) An automata system in which the output depends only on the present state is called Moore Machine.
ii) An automata system in which the output depends both on the present input and the present state is called Mealy machine.
a. Both are true
b. Both are false
c. 1 is true
d. 2 is true
50. Regular expression to accept a language consisting of strings of a’s and alternate a’s & b’s
a. (^+b)(ab)*(^+a)
b. bab*a
c. baba
d. ab*
51. A grammar G is said to be __________ regular grammar of all the productions are of the from
a. A®wB
b. A®w
c. None of the above
d. Both a & b
52. The regular expression (01)*+1 stands for_
a. Set of strings consisting of 01 & 1
b. Set of Strings consisting of even 1
c. Set of strings 1 or sting of (01)’s that repeat zero or more times
d. Set of strings 1 or string of 01’s that repeat zero or more times
53. True/False
1. If L1, L2 are regular, then L1ÈL2, L1.L2 and L1* are not the regular languages.
2. If L1 & L2 are regular, then the regular language is closed under complementation
a. Both are true
b. Both are false
c. 1 is true
d. 2 is True
54. Which of the following is not application of Pumping Lemma
1. To prove that certain languages are not regular
2. To check whether the language is infinite.
3. To prove that a given language is regular
4. To check whether the language is finite.
a. 1,2
b. 2,3
c. 1,4
d. 1,3
55. Which of the following is not a regular language
1. L={anblcn+1 | n,l³0}
2. L{anbn | n³0}
a. Both 1, 2
b. Only 1
c. Only 2
d. None of the above
56. The transition performed by the PDA depends on
1. The current state
2. The next output symbol
3. The next input symbol
4. The symbol on top of the stack
5. The final state
a. 1,2,3
b. 1,3,5
c. 1,2,4
d. 1,3,4
57. d(p,a,Z)=(q,^)means that
a. In state p, on scanning the input symbol ^(null string), and when top of this stack is Z, the machine enters into state q and the topmost symbol Z from the stack is replaced by a.
b. In state q, on scanning the input symbol Z, and when top of this stack is ^, the machine enters into state p and the topmost symbol aZ from the stack
c. In sate p, on scanning the input symbol a, and when top of this stack is Z, the machine enters into state q and the topmost symbol Z is deleted from the stack
d. None of the Above
58. Which of the following is not the application area of the Turing Machine
a. Automaton Theory
2. It can be used for calculating different types of functions such as simple functions and recursive functions
3. It can be used in the field of Artificial Intelligence
4. It helps in analyzing the different types of problems of their space and time complexity.
5. It helps in medical treatment
a. 1,2,3
b. 1,2,3,4
c. 1,3,4
d. 1,4,5
59. True/False
a The turing Machine has a tape that is unbound in both the directions
b The turing machine is deterministic in the sense that d defines at most one move for each configuration
a. Both are true
b. 1 is true
c. 2 is true
d. Both are false
60. True/False
a A language L is recursively enumerable, if it is accepted by TM.
b A turing machine is said to halt whenever it reaches a configuration for which d is defined
a. Both are True
b. Both are false
c. 1 is true
d. 2 is true
4 Marks
61. The big O for n! is
- O(log n)
- O(log n2)
- O(nlog n)
- O(log(n!))
62. Match the following
|
1. Direct Proof |
|
i) In this technique, we assume that property P is not true. Using logical reasoning, we have to get a conclusion that contradicts the given conditions |
|
2. Indirect Proof |
|
ii) The principle of this technique states that any set of natural numbers containing zero, and with the property that it contains n +1 whenever it contains all the numbers up to and including n, must be the set of all natural nos. |
|
3. Proof by Induction |
|
iii) This type of proof uses the technique of negation and conclusion |
|
4. Proof by Contradiction |
|
iv) In this type of proof we consider a set of hypothesis from which we infer a conclusion |
- 1-2, 2-4, 3-1, 4-4
- 1-4, 2-2, 3-3, 4-1
- 1-1, 2-2, 3-3, 4-4
- 1-4, 2-3, 3-2, 4-1
63. Let the symbols
L: Letter
D: Digit
I: Identifier
Write the Grammar G=(VN, VT, S, f)
a VN={a,b,c………….y,z}
VT={I, L,D}
S=I
f={I®L, I®IL, D®ID, D®a, L®b, ………L®z, L®0, L®1, ………. L®9}
b VN={I, L,D}
VT={0,1………9}
S=I
f={I®L, I®IL, I®ID, L®a, L®b, ………L®z, D®0, D®1, ………. D®9}
c VN={I, L,D}
VT={a,b,c………….y,z, 0,1…………..9}
S=I
f={I®L, I®IL, I®ID, L®a, L®b, ………L®z, D®0, D®1, ………. D®9}
d VN={I, L,D}
VT={a,b,c………….y,z}
S=I
f={LD®L, D®IL, I®ID, L®a, L®b, ………L®z, D®0, D®1, ………. D®9}
64. Match the following
|
1. Type O Grammar |
|
i) A grammar that contains only productions of the form a®b where ½a½£|b| |
|
2. Type 1 Grammar |
|
ii) A grammar in which there is no restrictions on its productions |
|
3. Type 2 Grammar |
|
iii) A grammar that contains only productions of the form a®b where ½a½£ ½b½ and a Î VN |
|
4. Type 3 Grammar |
|
iv) A grammar that contains only productions of form a®b where ½a½£ ½b½ and a Î VN and b has the form a, B or a where a Î VT, BÎVN |
a. 1-2, 2-4, 3-1, 4-4
b. 1-2, 2-1, 3-3, 4-4
c. 1-1, 2-2, 3-3, 4-4
d. 1-4, 2-3, 3-2, 4-1
65. In this method i.e ___________, a finite directed graph in which each node of the graph represents_________ and the directed edges from one node to another represent ________ . All the edges of the are labeled as __________.
a. Transition graph, State, Transition of state, input / output
b. Transition Table, Row, Column, Initial, Final State
c. Transition graph, Transition of State, state, input/output
d. None of the above
66. The DFA to accept even number of a’s.
a. a
|
q0 |
|
q1 |
a
b.
|
q0 |
|
q1 |
a
c.
|
q1 |
|
q0 |
a
a
d. None of the above
67. Match the following
|
i) States |
|
(1) It helps to determine the next output of the automaton system |
|
ii) State Relation |
|
2. The entire automata system at any given instant of time is in any one of the states |
|
iii) Output Relation |
|
3. These are generated at the output sides of the model are the elements. |
|
4. Output |
|
iv) It helps to determine the next state that the automaton system is going to attain. |
a. 1-2, 2-4, 3-1, 4-4
b. 1-2, 2-1, 3-3, 4-4
c. 1-2, 2-4, 3-1, 4-2
d. 1-4, 2-3, 3-2, 4-1
68. Arrange in the order of conversion of Mealy Machine into Moore machine
i) Rearrange the states and outputs in the format of a Moore Machine. The common output of the new state table can be determined by examining the outputs under the next state columns of the original Mealy Machine.
ii) If the outputs corresponding to state qi in the next state columns are same, then retain state qi s it is. Else break qi into different states with the number on new states being equal to the number of different outputs of qi
iii) If the output in the constructed state table corresponding to the initial state is 1, then this specifies the acceptance of the null string ^ by Mealy machine.
iv) For a state qi determine the number of different outputs that are available in q state table of the mealy machine
a. 1,2,3,4
b. 2,1,3,4
c. 4,2,1,3
d. 2,3,1,4
69. DFA and transition diagram to accept the language generated by the following grammar.
S®01A
A®10B
B®0A| 11
S |
|
q1 |
A |
|
q2 |
B |
|
q3 |
|
qf |
a.
1
0
0
1 1
b.
|
|