Theoretical Computer Science MCQ Questions and Answers. Computer Science Multiple Choice Questions with Answers for IT exam.
What is the Theory of Computation
The theory of computation, a field within computer science, delves into the underlying principles that govern the behavior of algorithms, languages, and machines.
It delves into the abstract study of computation and aims to understand the limits and capabilities of computational systems.
At its core, the theory of computation seeks to answer vital questions such as what can be computed, how efficiently it can be computed, and what problems are inherently unsolvable.
It offers a conceptual framework for comprehending the computational intricacies and potentialities embedded in various computational models, including finite automata, Turing machines, and formal languages.
This field plays a pivotal role in shaping our understanding of algorithmic efficiency, decidability, and the classification of computational problems into different complexity classes.
It provides insights into the boundaries of what can be achieved using computational methods and aids in developing efficient algorithms, compilers, and programming languages.
By exploring the theory of computation, researchers and practitioners gain a deeper appreciation of the mathematical underpinnings of computation, paving the way for advancements in various domains, including artificial intelligence, cryptography, and software engineering.
This discipline fuels innovation and contributes to the foundation of modern computing paradigms, enriching our comprehension of the possibilities and limitations of computation itself.
Top 60 Theoretical Computer Science Questions and Answers pdf
1. A ___ is a collection of objects in which we can say whether a given object is in the collection.
a. Property
b. Data
c. set
d. Elements
2. The members of a set are called ___
a. Element
b. Subset
c. Special set
d. Proper subset
3. A set A is said to be a ___ of B if there exists an element of B which is not an element of A.
a. Proper subset
b. Special sets
c. Subset
d. None of the above
4. A relation is said to be an ___ if it is reflexive, symmetric and transitive.
a. Congruence relation
b. Binary relation
c. N-ary relation
d. equivalence relation
5. If x and y are rational numbers then x + y ___.
a. Is rational
b. Is not rational
c. It can be or can’t be
d. None of the above
6. Binary tree of height n has at most ___ leaves.
a. 2n
b. 2
c. 2n
d. n2
7. A tree G with „n‟ vertices has ___ edges.
a. (n – 1) (n+ 1)
b. (n – 1)
c. (n +1)
d. n
8. Which principle can be described by the given statement:
If A and B are finite sets and | A | > | B |, then there is no one-to-one function from A to B.”
a . Proof by induction
b. Proof by contradiction
c. The Pigeonhole Principle
d. The Diagonalization Principle
9. If there is more than one edge associated with a given pair of vertices, then these edges are called __
a. Adjacent edges
b. Non-parallel edges
c. Parallel edges
d. Diagonal edges
10. Graph containing either parallel edges or loops is referred to as ___
a. Simple Graph
b. General Graph.
c. Undirected Graph
d. Line Graphs
11. If a vertex v is an end vertex of some edge e, then v and e are said to be ___ with (or on, or to) each other.
a. Incident
b. Similar
c. Adjacent
d. Different
12. The sum of the degrees of the vertices of a graph G is ___ the number of edges
a. 3 times
b. 4 times
c. twice
d. one time
13. A simple method of the specification which satisfies this requirement uses a generative device is referred to as ___.
a. string
b. alphabet.
c. Variables
d. Grammar
14. A grammar in which there are no restrictions on its productions is called ___
a. type – 0 grammar or unrestricted grammar
b. context-sensitive grammar.
c. context-free grammar.
d. Type 3 grammar
15. A grammar that contains only productions of the form where is called ___
a. context-free grammar.
b. context-sensitive grammar.
c. type – 0 grammar or unrestricted grammar
d. Type 3 grammar
16. The theory of formal languages exclusively involves the study of the language syntax and this theory incepts from the works of well-known ___
a. Ben Chifley
b. Teodoro Agoncillo
c. Noam Chomsky
d. Renato Constantino
17. The main part of the machine itself is a “black box”, this black box – called the ___
A . Infinite control
b. initial state
c. finite control
d. Reading head
18. ___ may take into consideration only the current input or both the current input and the current state for determining the next output.
a. Input relation
b. States
c. State relation
d. output relation
19. The symbol Σ used for ___
a. Input alphabet
b. Output alphabet
c. States
d. Submission of stages
20. A finite directed labelled graph in which each node or vertex of the graph represents a state and the directed edges from one node to another represents the transition of a state is called ___
a. Transition graph
b. Line Graph
c. Area Graph
d. Waterfall chart
21. There may be several possible next states for each of the input value and state. Such machines are called ___
a. Deterministic
b. Nondeterministic
c. Finite Automata
d. None of the above
22. Which of the following is not the property of nondeterministic finite automata
a. δ(q,Λ) = (q,Λ) = q
b. δ(q, wa) = δ( (q, w), a) = Aj
c. δ(q, aw) = (δ(q, a), w) = Aq,
d. δ(q, wa) = δ( (q, w), a)
23. An___ is a system that performs some specific tasks without the direct intervention of a human being.
a. automata
b. Machine
c. Transition function
d. States
24. In a Moore machine, which one is the correct symbol for the output alphabet
a. Σ
b. Δ
c. δ
d. ρ
25. ___ are used to represent a set of strings, include symbols that are arranged using certain syntax rules.
a. Regular expressions
b. Fuzzy regular expression
c. Pattern matching
d. General Expression
26. The ___ of a regular expression is also a regular expression
a. Submission
b. iteration
c. differentiation
d. Production
27. This is a regular expression that indicates the language containing an empty string.
a. {a}
b. Λ
c. Φ
d. a
28. “Define the meaning of the given expression
(a+b)* (a + bb)”
a. Set of strings consisting of at least one „a‟ followed by a string consisting of at least one “b” followed by a string consisting of at least one „c‟.
b. Set of strings of a’s and b‟s having a substring aa.
c. Set of strings of a’s and b’s ending with either a or bb
d. ab(a+b)*
29. ___ language is that language for which a FA cannot be constructed.
a. A regular
b. A non-regular
c. Formal language
d. Determinative
30. Which of the following is not the non-regular languages:-
a. {w ∈ {0, 1} | w contains an equal number of 0’s and 1’s}
b. {0n1n ∈ {0, 1}* | n ≥ 0}
c. {ap ∈ {a}* | p ≥2 is a prime number}
d. None of the above
31. Let Σ = {0, 1}, Σ = {0, 1, 2} and f(0) = 01, f(1) =112. and f(010)= 0111201. Write the homomorphic image of L = {00, 010}.
a. L(00, 010) = L(0101, 0111201).
b. L(00, 010) = L(0111201, 0101 ).
c. L(00, 010) = L(0000, 0111201).
d. L(00, 010) = L(0100, 0111000).
32. Suppose there are n objects and m boxes where the number of objects n, are greater than the number of boxes m. In this case, if all n objects are placed into m boxes, then at least one box will have more than one object. This principle is called __
a. DFA
b .homomorphism
c. Pigeonhole principle
d. Pumping Lemma
33. CFL stands for ___
a. Concept full language
b. context-free language
c. context full language
d. Concept free language
34. We can context-free grammar as a ___
a. type 0 grammar
b. type 1 grammar
c. type 2 grammar
d. type 3 grammar
35. In Backus – Naur Form (BNF) every non-terminal symbol is enclosed in ___
a. Small brackets()
b. angle brackets < >.
c. Big brackets [ ]
d. Curly brackets { }
36. A ___ is an ordered tree in which each vertex is labelled with the left sides of a product and in which the children of a vertex represent its corresponding right sides
a. derivation tree
b. Binary Tree
c. B-Tree
d. Balanced Tree
37. By Pumping Lemma, it is assumed that string z ∈ L is___ and is a context-free language
a. Infinite
b. finite
c. Empty
d. full
38. The Pumping Lemma for CFL’s are used to prove that certain languages are ___.
a. does not context-free
b. context-free
c. finite
d. Infinite
39. According to the ____ Turing machine can carry out any computation that can also be carried out by a computer and human beings.
a. Alonzo Church
b. universal Turing machine
c. The Church-Turing theory
d. Alan Turing
40. The structure of the Turing machine is somewhat similar to the modern computer in which the memory acts as the tape and the processor as ___
a. the R/W head.
b. tape drive
c. memory drive
d. Hard disk
41. ___ describes connections between different elements of the same set, whereas ___ describe connections between two different sets.
a. Function, Relation
b. Relation, functions
c. set, property
d. property, set
42. State whether the following statements are true or false.
1) If (a, b) is an element of the equivalence relation, then we write a ~ b.
2) Two sets A and B are said to be equal (denoted by A = B) if A is a subset of B, and B is a subset of A.
a. 1-T, 2-F
b. 1-F, 2-T
c. 1-T, 2-T
d. 1-F, 2-F
43. Which of the following is not a type of special proof technique
a. Proof by induction
b. Proof by contradiction
c. The pigeonhole principle
d. The alphanumeric Principle
44. The principle of mathematical induction states that any set of natural numbers containing ___, and with the property that it contains ___ whenever it contains all the numbers up to and including n, must in fact be the set of all-natural numbers.
a. one,n+1
b. Zero, n + 1
c. Zero,n-1
d. Two,n
45. The vertices vi, VJ associated with edge Ek are called the ___ of Ek. An edge associated with a vertex pair {vi, vi} is called a ___.
a. Start vertices, Self-loop
b. End vertices, Self-loop
c. Self-loop, Start vertices
d. Self-loop, End vertices
46. 1. A connected graph is said to be ___ if the removal of anyone edge from the graph provides a disconnected graph.
2. A tree in which one vertex is distinguished from all the other vertices, is called a ___
a. rooted tree, minimally connected
b. minimally connected, rooted tree
c. minimally disconnected, Free tree
d. free tree, minimally disconnected
47. The terms <noun>, <verb> and <adverb>, are known as ___ and the suitable words that can sentence are known as ___.
a. terminals, variables
b. variables, terminals
c. sentences, String
d. String, sentences
48. Let x = 0100, y = 11. Find xy and yx.
a. xy = 110100, yx = 010011
b. xy = 010011, yx = 110100
c. xy = 010000, yx = 110100
d. xy = 010011, yx = 110111
49. An automata system in which the output depends only on the present input is called a ___ and an automata system in which the output depends both on the present input and the present state is called ___.
a. State machine, Mealy machine
b. Moore machine, Mealy machine
c. Deterministic finite state machine, the finite state machine
d. Finite state machine, the deterministic finite state machine
50. Which of the following is not the quintuple of deterministic finite automata?
a. Q is a non-empty, finite set of states.
b. ∑ is a non-empty, finite set of input alphabet.
c. q0 ∈ Q is the end state.
d. F ⊆ Q is a set of accepting or final states.
51. NFA have 5 tuples like M = (Q, ∑, δ q0, F), according to the given tuples what is the correct description of δ
a. It is a non-empty, finite set of states.
b. It is a non-empty, finite set of input alphabet.
c. is the transition function, which is a mapping from Q x ∑
d. it is the start state.
52. State whether the following statements are true or false:-
1. A string is a sequence of symbols obtained from ∑.
2 . In NFA F ⊆ Q is a set of accepting or final states.
a. 1-T, 2-F
b. 1-F, 2-T
c. 1-T, 2-T
d. 1-F, 2-F
53. In the Turing machine model the data stored in the cells of the tape can be read and written by reading/Write (R/W) head whose one end is connected with the ___ and the other end is connected with the ___.
a. tape, Infinite control
b. Infinite control, tape
c. tape, finite control
d. finite control, Infinite control
54. “The Turing Machine can do:
1. Halt and accept by entering into the final state.
2. Halt and reject. This is possible if the transition is not defined.
3. TM will never halt and enter into an infinite loop.
Which of the above-given statement/s are not correct.
a. 1 and 2
b. 2 and 3
c. 1 and 3
d. All are correct
55. State, whether the given language L = {anbncn | n ≥ 0}, is context-free or not
a. It is context-free
b. It is not context-free
c. Data insufficient
d . It is finite
56. Verify that the given language L = {an! | n ≥ 0} is context-free or not.
a. It is not context-free
b. It is context-free
c. Data insufficient
d. It is finite
57. The pop transition, also known as ___ transition, refers to the transition process in which the PDA moves from the current state to a new state without reading any input symbol. It can be represented as ___
a. lambda, ai bi λ → aj bj
b. read, ai bi wj → bi bj
c. write, a0 b0 w1 → a0 b1
d. alpha, ai bi α → aj bj.
58. State whether the following statements are true or false for the construction of pushdown automata.
1. Get the final state from the start state.
2. Get an empty stack from the start state
a. 1-T, 2-F
b. 1-F, 2-T
c. 1-T, 2-T
d. 1-F, 2-F
59. Which of the following description is not correct for context-free grammar?
A grammar G is a quadruple G = (VN, VT, Φ, S), where
1. VN is a set of variables or non-terminals
2. VT is a set of productions
3. Φ is a set of terminals symbols
4. S is the start symbol,
a. 1 and 2
b. 2 and 4
c. 2 and 3
d. 1,2 and 3
60. “State whether the following statements are true or false:-
1. √2 is a rational number.
2. According to the principle of mathematical induction for all positive integer n.
3. for any finite set A, the cardinality of the power set of A is 2 raised to a power equal to the cardinality of A.”
a. 1-T,2-T,3-T
b. 1-T,2-T,3-F
c. 1-T,2-F,3-T
d. 1-F,2-T,3-T
Computer Science MCQs with Answers: Set-1
Thanking you very much for reading our blog post on Theoretical Computer Science MCQ Questions if you like please share on social media.
