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.

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

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