Is this NFA correct? First time doing this!

63 Views Asked by At

I have recently learned how to make DFA and NFA. For an assignment, I had the following question:

Draw the state diagram for an automaton accepting language L1 over alphabet A = {a, b} from the previous homework. L1 is the set of all words w ∈ A∗ such that w contains either only a’s or only b’s.

I created this state diagram in Latex. Can you guys see if this is correct? (I have no idea how to add the actual output of this code)

starting state: q0 final state: q4

1: enter image description here

1

There are 1 best solutions below

4
On

No, this in incorrect. The language this parses is the language of all strings that end in $b$.

Here's the DFA I'd use (it only has $4$ states, vs your NFA turned DFA would have $32$ states):

$\Sigma=\{a,b\}$

$Q=\mathcal P(\Sigma)$ ($\mathcal P$ is the power set).

$\delta(q,s)=\{s\}\cup q$

$q_0=\varnothing$

$F=\{\varnothing,\{a\},\{b\}\}$.

To check whether this is optimal, consider the regular expression for this language, $a^*+b^*$, and its derivatives.

$$D_\varepsilon(a^*+b^*)=a^*+b^*$$ $$D_a(a^*+b^*)=a^*$$ $$D_b(a^*+b^*)=b^*$$ $$D_{ab}(a^*+b^*)=\varnothing$$

Since there are at least $4$ distinct derivatives, this is optimal.

Edit:

For OP's new question, as I noted above, the presented NFA parses the language of strings ending with $b$.

Here's a DFA that solves the problem (DFAs are also NFAs)

$Q=\{0,a,b\}$

$\delta(q,c)=\begin{cases}a&c=a\\0&c=b\text{ and }q\neq a\\b&c=b\text{ and }q=a\end{cases}$

$q_0=0$

$F=\{b\}$.