GATE 2024 Theory of computation Foundation Quiz 85

Let NFA has 5 states, what is the maximum number of states possible in the equivalent DFA ___.

What is the minimum number of states required by a DFA to accept the language

L=(a+b)* (ab+ba) ?

Consider a regular language R over Σ = {a, b} which is equivalent to the regular expression (ab + b)*. The number of equivalence classes of Σ* that are present for the language R is __________.

Which of the following is not regular language?

Consider the DFA over alphabet ∑ = {a, b} is given below.

Consider the following statements about above DFA:

S₁: Complement of L(A) is context-sensitive

S₂: L(A) = (a(a + b)* + ba(a + b)* + bb(a + b)*)

S₃: For the language accepted by A, the minimum DFA of A will contain 3 states.

S₄: A accepts all strings over {a, b} that ends with ‘a’.

Which of the following is false?