MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

5 added 74 characters in body

To determine if an NFA $M$ accepts all strings , you can first convert $M$ to its construct the machine that accepts the complement language $\overline{M}$ (here is the exponential bottleneck ) $\overline{M}$. since you must first convert to a DFA). Then you can use Harry Altman's suggestion to check for emptiness.

To convert $M$ with $n$ states which accepts a language $L$ to a DFA $D$ which also accepts $L$ but using $d$ steps in poly$(n,d)$ time on a Turing machine is easy, however $d$ in the worst case is exponential in $n$ (using the naive algorithm undergrads learn). This problem is very well studied and in practice many programmes use tricks to do this more efficiently. I'm not at all familiar with these though so I cannot say if they use poly$(n)$ space and time average casethough.

4 added 2 characters in body

To determine if an NFA $M$ accepts all strings, first convert $M$ to its complement (here is the exponential bottleneck) $\overline{M}$. Then use Harry Altman's suggestion to check for emptiness.

To convert $M$ with $n$ states which accepts a language $L$ to a DFA $D$ which also accepts $L$ but using $d$ steps in poly$(n,d)$ time on a Turing machine is easy, however $d$ in the worst case is exponential in $n$ (using the naive algorithm undergrads learn). This problem is very well studied and in practice many programmes use tricks to do this more efficiently. I'm not at all familiar with these though so I cannot say if they use poly$(n)$ space and time worst average case though.

3 added 5 characters in body

To determine if an NFA $M$ accepts all strings, first convert $M$ to its complement $\overline{M}$ (where here is the exponential bottleneck) $L(M)\cup L(M)=\Sigma^*$). \overline{M}$. Then use Harry Altman's suggestion to check for emptiness. To convert$M$with$n$states which accepts a language$L$to a DFA$D$which also accepts$L$but using$d$steps in poly$(n,d)$time on a Turing machine is easy, however$d$in the worst case is exponential in$n$(using the naive algorithm undergrads learn). This problem is very well studied and in practice many programmes use tricks to do this more efficiently. I'm not at all familiar with these though so I cannot say if they use poly$(n)\$ space and time worst case though.

2 added 33 characters in body
1