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

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?

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

Consider the following languages.

L1 = { aⁿ bⁿ c^m| m >= 0 and n >= 0 } 
L2 = { a^m bⁿcⁿ| n >= 0 and m >= 0 }

L3 = L1 ∪ L2 = { aⁿbⁿc^m∪ a^mbⁿcⁿ| n >= 0, m >= 0 }

How many of the above language L₁, L₂, L₃ are context free language?

How many of the following languages are regular?

I. {aⁿ b^m ; n + m is even}

II. {aⁿ b^m ; n = 6 – m}

III. {aⁿ b^m ; nm <= 789}

IV. {aⁿ b^m ; nm = 78 }