Theory of Computation MCQ Quiz - Objective Question with Answer for Theory of Computation - Download Free PDF
Last updated on Jun 26, 2025
Latest Theory of Computation MCQ Objective Questions
Theory of Computation Question 1:
Which of these strings can be represented by the regular expression: a*bb*abaaaa*?
Answer (Detailed Solution Below)
Theory of Computation Question 1 Detailed Solution
The correct answer is Option 4: babaaaaaaa.
Key Points
- The regular expression
a*bb*abaaaa*
represents strings that follow these rules:a*
: Matches zero or more occurrences of the character 'a'.bb*
: Matches one 'b' followed by zero or more occurrences of 'b'.ab
: Matches the exact sequence 'ab'.aaaa*
: Matches 'aaaa' followed by zero or more occurrences of 'a'.
- Let's analyze each option:
- Option 1: aaaabbbbbb - This string does not contain 'ab', so it does not match the regular expression.
- Option 2: bbbbbbaaaa - This string does not contain 'ab', so it does not match the regular expression.
- Option 3: aaaabaaaaa - This string does not contain 'ab', so it does not match the regular expression.
- Option 4: babaaaaaaa - This string matches the regular expression:
a*
: Matches zero occurrences of 'a'.bb*
: Matches one 'b'.ab
: Matches the sequence 'ab'.aaaa*
: Matches 'aaaa' followed by four 'a's.
Additional Information
- Regular expressions are used to define patterns for matching strings.
- They are commonly used in programming for searching, replacing, and validating text.
- The expression
a*bb*abaaaa*
ensures a specific sequence of characters while allowing flexibility with repetitions. - Understanding the structure of a regular expression is crucial for determining valid matches.
Theory of Computation Question 2:
Which of the following statement is correct about NP problems?
Answer (Detailed Solution Below)
Theory of Computation Question 2 Detailed Solution
The correct answer is They have a non-deterministic polynomial-time solution..
Key Points
- NP (Non-deterministic Polynomial time) problems are a class of decision problems for which a solution can be verified in polynomial time by a deterministic Turing machine.
- In essence, if a solution to an NP problem is provided, we can check its correctness in polynomial time.
- However, finding the solution itself may require non-deterministic computation.
- The term "non-deterministic polynomial-time solution" means that the problem can be solved by a non-deterministic Turing machine in polynomial time.
- A non-deterministic Turing machine can explore multiple computational paths simultaneously and "guess" the correct solution.
- This makes NP problems theoretically solvable in polynomial time under non-deterministic computation.
- Examples of NP problems include the Traveling Salesman Problem (TSP), Knapsack Problem, and Boolean Satisfiability Problem (SAT).
Additional Information
- NP problems are not necessarily "easy" to solve, but their solutions are "easy" to verify in polynomial time.
- The relationship between NP and P (problems solvable in polynomial time by a deterministic machine) is a famous open question in computer science: P vs NP.
- If P = NP, it means every NP problem can also be solved in polynomial time deterministically.
- If P ≠ NP, it implies that some NP problems cannot be solved in polynomial time deterministically.
- NP-complete problems are the "hardest" problems in NP, meaning that if any NP-complete problem can be solved in polynomial time, then all NP problems can be solved in polynomial time.
- Examples of NP-complete problems include the 3-SAT Problem and Graph Coloring Problem.
Theory of Computation Question 3:
_____ was the first Turing-complete machine to be designed.
Answer (Detailed Solution Below)
Theory of Computation Question 3 Detailed Solution
Analytical Engine:
- An analytical engine is a machine which is considered to be the concept for the first general mechanical computer.
- It was programmed using punch cards and also have an integrated memory.
- It was first proposed by Charles Babbage in 1837 and it was considered as the first design concept of a general-purpose computer.
EDSAC:
- EDSAC stands for Electronic Delay Storage Automatic Calculator
- It is considered to be the second stored-program electronic computer.
- It is also considered as the first computer to run a graphical computer game.
ENIAC:
- ENIAC stands for Electronic Numerical Integrator And Computer, was the first general-purpose electronic computer. It was the first Turing-complete, digital computer capable of being reprogrammed to solve a full range of computing problems.
The correct answer is option 1 i.e Analytical Engine
Theory of Computation Question 4:
Consider the finite automata given below :
The language b accepted by this automata is given by the regular expression :
Answer (Detailed Solution Below)
Theory of Computation Question 4 Detailed Solution
The correct answer is Option 1: b* a b * a b * a b *. Key Points
- The regular expression b* a b * a b * a b * represents the language accepted by the given finite automata.
- This regular expression can be broken down as follows:
- b* matches zero or more occurrences of the character 'b'.
- a matches a single occurrence of the character 'a'.
- Repeating the pattern b* a three more times ensures that the sequence 'a' appears exactly three times, each possibly preceded by zero or more 'b's.
- This pattern matches any string of 'b's followed by 'a', and this sequence is repeated three times.
Additional Information
- The finite automata can be visualized as having states that transition between each other upon reading specific inputs (characters).
- Understanding the structure of the automata and the transitions helps in deriving the correct regular expression that represents the language it accepts.
- Finite automata are used in various fields such as text processing, compiler design, and network protocols to recognize patterns and validate input sequences.
- Regular expressions are a powerful tool for describing patterns in strings and are widely used in search algorithms, text processing, and input validation.
- b* matches zero or more occurrences of the character 'b'.
- a matches a single occurrence of the character 'a'.
- Repeating the pattern b* a three more times ensures that the sequence 'a' appears exactly three times, each possibly preceded by zero or more 'b's.
Theory of Computation Question 5:
Let L = L1 ∩ L2 where L1 and L2 are language defined below :
L1 = {ambmc an bn m, n ≥ 0}
L2 = {aibj ck | i, j, k ≥ 0}
Then L is :
Answer (Detailed Solution Below)
Theory of Computation Question 5 Detailed Solution
The correct answer is Not Recursive.
Key Points
- Let L = L1 ∩ L2 where L1 and L2 are languages defined below :
- L1 = {ambmcanbn | m, n ≥ 0}
- L2 = {aibjck | i, j, k ≥ 0}
- The intersection of these two languages is a language L where the number of a's is equal to the number of b's and the number of c's is equal to the number of b's.
- This language is not recursive because it cannot be decided by a Turing machine in a finite amount of time.
Additional Information
- A recursive language is a type of formal language that can be decided by a Turing machine that always halts.
- A language is considered recursively enumerable if there is a Turing machine that will halt and accept the strings in the language but may run forever for strings not in the language.
- Regular languages can be recognized by finite automata and are a subset of context-free languages.
- Context-free languages can be recognized by pushdown automata and include most programming languages.
Top Theory of Computation MCQ Objective Questions
Identify the language generated by the following grammar, where S is the start variable.
S → XY
X → aX | a
Y → aYb | ϵ
Answer (Detailed Solution Below)
Theory of Computation Question 6 Detailed Solution
Download Solution PDFGrammar:
S → XY
X → aX | a
Y → aYb | ϵ
Explanation:
X generates at least one a. Generates a string of type {a, aa, aaa, aaaa……}
ambn, if n = 0 and m = 0 ∴ string = ϵ which cannot be generated from the given grammar and hence option 2 is incorrect.
Y generates an equal number of a and b { ϵ, ab, aabb, ……} with a comes before b.
Since at least one a is generated by X and an equal number of a’s and b’s generated by Y ∴ m> n and hence option 1 is incorrect
The smallest length string generated by Y is ϵ. In ambn, n ≥ 0 and hence option 4 is incorrect.
{ a, aab, aaabb,………….} which is equivalent to :
L = {ambn | m > n, n ≥ 0}
Which of the following languages is generated by the given grammar?
S → aS | bS | ϵ
Answer (Detailed Solution Below)
Theory of Computation Question 7 Detailed Solution
Download Solution PDFS → aS | bS | ϵ
This grammar results in (a + b)*
DFA for this grammar is:
Diagram
Now, consider the options one by one:
Option 1:
{anbm | n, m ≥ 0}
Here order is fixed, means first any number of a will come then any number of b. It is incorrect.
Option 2:
{w ϵ {a, b} * | w has an equal number of a’s and b’s}
As given grammar is not generating the expression which generates only equal number of a and b. So,
not correct.
Option 3:
{an | n ≥ 0} {bn | n ≥ 0} {anbn | n ≥ 0}
Here, also order is fixed. So, it is incorrect.
Option 4:
{a, b}*
This is equivalent to (a + b)*. So, it is correct.
The minimum possible number of states of a deterministic finite automation that accepts the regular language L = {w1aw2 | w1, w2 ϵ {a, b}*, |w1| = 2, |w2| ≥ 3} is ________.
Answer (Detailed Solution Below) 8
Theory of Computation Question 8 Detailed Solution
Download Solution PDFGiven language is: L = {w1aw2 | w1, w2 ϵ {a, b}*, |w1| = 2, |w2| ≥ 3}
Regular expression: (a+b) (a+b) a (a+b) (a+b) (a+b)(a+b)*
Minimum length string that is possible = (a+b) (a+b) a (a+b) (a+b) (a+b)
This string has minimum length 6. For these 7 states are needed and one trap state. So, total 8 states are needed.
DFA for given language is
Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is____________________
Answer (Detailed Solution Below) 1
Theory of Computation Question 9 Detailed Solution
Download Solution PDFConsider DFA M,
It is accepting all the string that ends with a.
Language for DFA M L(M) = {a, aa, ba, aaa, aba, …}
Regular expression = (a + b )*a
DFA N is accepting all the languages ending with b.
Language for DFA N L (n) = {b, ab, bb, aab, abb, bbb,…….}
Regular expression = (a + b)*b
Intersection of both these languages L (M) ꓵ L(N) = { } = Ø i.e. empty language
For this, we just need 1 state with all transitions to itself and no final state.
Language L1 is defined by the grammar: S1 → aS1b|ϵ
Language L2 is defined by the grammar: S2 → abS2|ϵ
Consider the following statements:
P: L1 is regular
Q: L2 is regular
Which one of the following is TRUE?
Answer (Detailed Solution Below)
Theory of Computation Question 10 Detailed Solution
Download Solution PDFSuppose grammar G1:
S1 → aS1b|ϵ
It generates language in which number of a’s are equal to number of b’s and all a’s are followed by b’s
L1 = { an bn | n ≥ 0}.
It is deterministic context free language. Extra memory is required for this. So, it can’t be accepted by finite state automata. L1 is not a regular language.
Now, another grammar let G2: S2 → abS2|ϵ
This grammar also generates language in which number of a’s are equal to number of b’s. But it generates language L2 = { (ab)n | n ≥ 0 }
Regular expression for this = (ab)*
It doesn’t require any extra memory to remember the last string. It can be accepted by finite state automata. So, L2 is regular.
If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?
Answer (Detailed Solution Below)
Theory of Computation Question 11 Detailed Solution
Download Solution PDF- Non-deterministic push down automata (NPDA) determines the middle position of the string in the language and start popping until Z(end of stack elements) is meet to tell the acceptance of it .
- As all the string present in the language wwR accepted by NPDA Hence it is a context free language (CFL).
- From the properties of regular language: Reverse, Suffix, Prefix, Concatenation of Regular language is Regular.
- Every regular language is context free language, but every context free language is not a regular language also wwR it is not possible to give, DFA, NFA or ϵ - NFA accepting the language. Therefore, it is not Regular language.
Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements.
I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
Answer (Detailed Solution Below)
Theory of Computation Question 12 Detailed Solution
Download Solution PDFConcept:
Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.
Explanation:
Statement I: TRUE.
L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}
{an |n ≥ 0} is a regular language and {anbn| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.
Statement II: FALSE.
L is DCFL then it is CFL too.
Statement III: TRUE
L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from an or from anbn. Both have a common prefix.
Consider the language L given by the regular expression (a + b)* b (a + b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ________.
Answer (Detailed Solution Below) 4
Theory of Computation Question 13 Detailed Solution
Download Solution PDFConcept:
First convert the given regular expression into an NFA and then find out the DFA from NFA.
Explanation:
Regular expression is (a + b) * b (a + b)
NFA for this expression is given here as:
Diagram: NFA
NFA Table:
States |
a |
b |
→ q0 |
q0 |
{q0, q1} |
q1 |
q2 |
q2 |
q2 |
ϕ |
ϕ |
DFA Table from the above NFA
States |
a |
b |
→ q0 |
q0 |
{q0, q1} |
{q0, q1} |
{q0, q2} |
{q0, q1, q2} |
*{q0, q2} |
q0 |
{q0, q1} |
*{q0, q1, q2} |
{q0, q2} |
{q0, q1, q2} |
Diagram: DFA
This DFA can’t be minimized further. So, for the given regular expression minimum number of states in the DFA is 4.
Let δ denote the transition function and
δ |
ϵ |
a |
b |
→ q0 |
{q2} |
{q1} |
{q0} |
q1 |
{q2} |
{q2} |
{q3} |
q2 |
{q0} |
ϕ |
ϕ |
*q3 |
ϕ |
ϕ |
{q2} |
Then
Answer (Detailed Solution Below)
Theory of Computation Question 14 Detailed Solution
Download Solution PDFConcept:
Extended transition function means when we start from a state and follow a sequence of input.
In case of ϵ-NFA, epsilon moves are also considered.
Diagram: NFA for the given NFA table is:
Here,
Explanation:
When input a is applied on q2 it will move to q0, q1 as there is null transition so it will also get to q2.
Similarly, states after input b => {q0, q2, q3}
States after input a = {q0, q1, q2}
So, final answer is {q0, q1, q2}
Consider the following statements.
I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
Answer (Detailed Solution Below)
Theory of Computation Question 15 Detailed Solution
Download Solution PDFStatement I: FALSE
If L1 ∪ L2 is regular, then neither L1 nor L2 needs necessarily be regular.
Example:
Assume L1= {an bn, n ≥ 0} over the alphabet {a, b} and L2 be the complement of L1.
Neither L1 nor L2 is regular (both are DCFL) but L1 ∪ L2= {an bn} ∪ {an bn}c = (a + b)* is regular.
Statement II: FALSE. The infinite Union of regular languages is not regular.
Example:
Given alphabet {a, b}.
L1= {ε}
L2= {ab}
L3= {aabb}
L4= {aaabbb}
:
:
L = L1 ∪ L2 ∪ L3 ∪ L4 …
Each of the above are regular but their infinite Union gives L1= {an bn, n ≥ 0} which is not regular but DCFL.
Note:
DCFL → Deterministic context free language