Register

GO Classes DPP | GATE CS | Theory of Computation | State Complexity

92 views
2 2 votes

Which statements are true?

  1. Every language recognized by an $n$-state DFA can be recognized by an NFA with $n$ states.
     
  2. Every language recognized by an $n$-state NFA can be recognized by a DFA with $n$ states.
     
  3. Every regular expression of length $n$ can be converted to an NFA having $O(n)$ states.
     
  4. If $A$ and $B$ each have an $n$-state DFA, then $A\cup B$ is always recognizable by a DFA with at most $2n+1$ states.

1 Answer

1 1 vote

A is true because every DFA is already an NFA.

B is false. Determinization may require exponentially many states, up to $2^n$ in the usual subset construction.

C is true using the standard regular-expression-to-NFA construction.

D is false. The standard product construction for union may require up to $n^2$ product states, and there are language pairs where quadratic state complexity is genuinely necessary. So $2n+1$ is not a valid general upper bound.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
118
118 views
GO Classes asked Sep 19
118 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $L_1$ and $L_2$ be regular languages and let $L_3$ be non-regular. Which statements are always true?$L_1=L_2$ iff $L_1\cap\overline{L_2}=\emptyset$ $L_1\cup L_3$ is n...
1 1 vote
1 1 answer
81
81 views
GO Classes asked Sep 19
81 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $L_1$ be regular where specified. Which of the following languages are guaranteed to be regular?$\{ww\mid w\in{0,1}^*\}$ $\{ww\mid w\in L_1\}$ $\{w\mid ww\in L_1\}$ $...
1 1 vote
1 1 answer
96
96 views
GO Classes asked Sep 19
96 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
All languages are over $\{0,1\}$. Which statements are true?If $L_1\subseteq L_2$ and $L_2$ is regular, then $L_1$ must be regular. If $L_1$ and $L_2$ are both non-regula...
1 1 vote
1 1 answer
102
102 views
GO Classes asked Sep 19
102 views
GO Classes DPP | GATE CS | Theory of Computation | De Morgan & NFA
Consider,Statement $1:$ If a language family is closed under union and complement, then it must also be closed under intersection. Statement $2:$ An NFA can be constructe...