class of languages strongly recognized by nondeterministic automata coincides with the class of regular languages

Question

I've been on this question for weeks. does anyone have any idea about it?

A language $L \subseteq A^*$ is strongly accepted by a nondeterministic finite automaton $M=(A,q,\delta,q_0,F)$ if $L = \{ x \in A^* | \delta^*(q_0,x) \subseteq F\}$. In other words $L$ is strongly accepted by a NDFA $M$ if $L$ consists of those words $x \in A^*$ such that every sequence of states generated in $M$ by $x$ ends in a final state. Prove that the class of languages strongly recognized by nondeterministic automata coincides with the class of regular languages

Answer 1

Building on Frentos' comment:

• any regular language $L$ is strongly-accepted, i.e. you can construct a NFA with the required properties

Just construct a normal DFA. Think about why this is sufficient.

• any strongly-accepted language $L$ is regular

You can determinize the NFA in a usual manner with the powerset construction, except you define its final states $F'$ as follows: $F'=\{X\in 2^Q|\forall q\in X.q \in F\}$, where $Q$ are the states of the NFA (note that there is a universal quantifier instead of an existential one). Again, think about why this is the case.