Time Left - 15:00 mins

# GATE CS 2022 : Theory of Computation-1 (App update required to attempt this test)

Attempt now to get your rank among 230 students!

Question 1

Let N be an NFA with n states. Let be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

Question 2

Identify the language, L which is not a CFL.

Question 3

Let L be the language represented by the regular expression Σ0011Σ∗ where Σ= {0, 1}. What is the minimum number of states in a DFA that recognizes (complement of L)?

Question 4

Consider the following languages.

L1 = { an bn cm| m >= 0 and n >= 0 }
L2 = { am bncn| n >= 0 and m >= 0 }

L3 = L1 ∪ L2 = { anbncm∪ ambncn| n >= 0, m >= 0 }

How many of the above language L1, L2, L3 are context free language?

Question 5

Consider a language L={ab,ba,abab} represented in the form of DFA machine. Then what is the number of strings present in the function INIT(L) ?

Question 6

How many of the following languages are regular?

I. {an bm ; n + m is even}

II. {an bm ; n = 6 – m}

III. {an bm ; nm <= 789}

IV. {an bm ; nm = 78 }

• 230 attempts
• 1 upvote
• 1 comment
Jun 6GATE & PSU CS

Posted by:

Member since Jul 2020