TOC GATE Questions

If you are preparing for the Graduate Aptitude Test in Engineering (GATE), practicing Theory of Computation (TOC) GATE questions is essential for scoring well in the Computer Science and Information Technology (CSE) paper. The subject Theory of Computation is a core topic in GATE and usually contributes multiple conceptual and problem-solving questions every year.

In this section, we will explore important TOC GATE questions with explanations, which can help students improve their problem-solving skills and perform better in the GATE examination.

TOC GATE Question 01

How many substrings “aab” are in ww^R w, where w = aabbab?

Solution:

Given w = aabbab

First compute wᴿ (reverse of w):

• w = aabbab

• wᴿ = babbaa

Now construct the string wwᴿw: wwᴿw = (aabbab)(babbaa)(aabbab) = aabbabbabbaaaabbab

Result: Total occurrences of “aab” = 2

Look at the following diagram to understand TOC GATE question 01 more clearly

TOC GATE Question 02

Show that | uⁿ | = n | u | for all strings “u” and all “n”, where n ≥ 0

Solution

• Let u be any string in Formal Language Theory and |u| denote its length.
• The notation uⁿ means the string u concatenated with itself n times.
• Since each copy of u has length |u|, the total length is the sum of |u| added n times.
• Therefore, |uⁿ| = n|u| for all n ≥ 0

Look at the following diagram to understand TOC GATE Question 02 more clearly

Common mistake !!

It is a common mistake that some people assume |uⁿ| = |u|ⁿ, but this is not correct in TOC. So, |uⁿ| ≠ |u|ⁿ

TOC GATE Question 03

Prove that ( uv )^R = v^R u^R for all u, v ∈ Σ⁺

Solution

Let u,v ∈ Σ⁺ be two strings over alphabet Σ. We prove that the reverse of the concatenation of two strings is equal to the concatenation of their reverses in opposite order.

General Proof: Look at the following diagram to understand TOC GATE Question 03 more clearly with general proof

Example Proof: Look at the following diagram to understand TOC GATE Question 03 more clearly with Example

Common mistake !!

It is a common mistake that some people assume (uv)^R = u^R v^R, but this is not correct in TOC. So, (uv)^R| ≠ u^R v^R

TOC GATE Question 04

Prove that ( w^R )^R= w for all w ∈ Σ^*

Solution

Let w ∈ Σ* be any string over alphabet Σ. We prove that reversing a string twice gives the original string.

General Proof: Look at the following diagram to understand TOC GATE Question 04 more clearly with general proof

Example Proof: Look at the following diagram to understand TOC GATE Question 04 more clearly with Example

TOC GATE Question 05

Let L = {ab, aa, baa}. Which of the following strings are in L^*: abaabaaabaa, aaaabaaaa, baaaaabaaaab, baaaaabaa? Which strings are in L⁴?

Solution

Look at the following diagram to understand TOC GATE Question 05 more clearly 

• All given strings are in L^*
• Strings in L⁴: aaaabaaaa and baaaaabaa.
• Strings in L⁵: abaabaaabaa and baaaaabaaaab.

TOC GATE Question 06

If Σ = {a, b} and L = {aa, bb}. Use set notation to describe L^c.

Solution

Look at the following diagram to understand TOC GATE Question 06 more clearly 

The above diagram also shows that L^c will contain all strings over Σ except “$aa”$ and “$bb”$.

• Example strings: L^c = {ε,a,b,ab,ba,aaa,aab,aba,… }