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*?

  1. aaaabbbbbb
  2. bbbbbbaaaa
  3. aaaabaaaaa
  4. babaaaaaaa

Answer (Detailed Solution Below)

Option 4 : babaaaaaaa

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?

  1. They can be solved using a branch and bound approach.
  2. They have a deterministic exponential-time solution.
  3. They have a non-deterministic polynomial-time solution.
  4. They can be solved in polynomial time.

Answer (Detailed Solution Below)

Option 3 : They have a non-deterministic polynomial-time solution.

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.

  1. Analytical Engine
  2. EDSAC
  3. ENIAC
  4. More than one of the above
  5. Search Engine

Answer (Detailed Solution Below)

Option 1 : Analytical Engine

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 :

  1. b* a b * a b * a b * 
  2. (a + b)* 
  3. b*a (a + b)*
  4. b* ab* ab*

Answer (Detailed Solution Below)

Option 1 : b* a b * a b * a b * 

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.

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 : 

  1. Not Recursive
  2. Regular 
  3. Context Free but not regular 
  4. Recursively enumerable but not context free

Answer (Detailed Solution Below)

Option 1 : Not Recursive

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 | ϵ

  1. {ambn | m ≥ n, n > 0}
  2. {ambn | m ≥ n, n ≥ 0}
  3. {ambn | m > n, n ≥ 0}
  4. {ambn | m > n, n > 0}

Answer (Detailed Solution Below)

Option 3 : {ambn | m > n, n ≥ 0}

Theory of Computation Question 6 Detailed Solution

Download Solution PDF

Grammar:

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 | ϵ  

  1. {anbm | n, m ≥ 0}
  2. {w ∈ {a, b} * | w has equal number of a’s and b’s}
  3. {an | n ≥ 0} ∪ { bn | n ≥ 0} ∪ {abn | n ≥ 0}
  4. (a + b}*

Answer (Detailed Solution Below)

Option 4 : (a + b}*

Theory of Computation Question 7 Detailed Solution

Download Solution PDF

S → 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 PDF

Given 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 PDF

Consider 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?

  1. Both P and Q are true
  2. P is true and Q is false
  3. P is false and Q is true
  4. Both P and Q are false

Answer (Detailed Solution Below)

Option 3 : P is false and Q is true

Theory of Computation Question 10 Detailed Solution

Download Solution PDF

Suppose 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?

  1. L . LR = {xy | x ϵ L, yR ϵ L}
  2. {wwR | w ϵ L}
  3. Prefix (L) = {x ϵ ∑* | ∃x ϵ ∑* such that xy ϵ L}
  4. Suffix (L) = {y ϵ ∑* | ∃x ϵ ∑* such that xy ϵ L}

Answer (Detailed Solution Below)

Option 2 : {wwR | w ϵ L}

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?

  1. I only
  2. II only
  3. I and III only
  4. III only

Answer (Detailed Solution Below)

Option 3 : I and III only

Theory of Computation Question 12 Detailed Solution

Download Solution PDF

Concept:

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 PDF

Concept:

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  denote the extended transition function of the ϵ-NFA whose transition table is given below:

δ

ϵ

a

b

→ q0

{q2}

{q1}

{q0}

q1

{q2}

{q2}

{q3}

q2

{q0}

ϕ

ϕ

*q3

ϕ

ϕ

{q2}

 

Then  is

  1. ϕ
  2. {q0, q1, q3}
  3. {q0, q1, q2}
  4. {q0, q2, q3}

Answer (Detailed Solution Below)

Option 3 : {q0, q1, q2}

Theory of Computation Question 14 Detailed Solution

Download Solution PDF

Concept:

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?

  1. I only
  2. II only
  3. Both I and II
  4. Neither I nor II

Answer (Detailed Solution Below)

Option 4 : Neither I nor II

Theory of Computation Question 15 Detailed Solution

Download Solution PDF

Statement 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

Hot Links: teen patti apk download teen patti stars teen patti master app teen patti - 3patti cards game mpl teen patti