Construct an NFA wherein the first symbol of only appears once

275 Views Asked by At

Given the language $$ L= \{w \in \{a,b,c,d\}^* \mid \text{the first symbol of $w$ appears only once in $w$}\} $$

This is the answer I came up with and I'm not entirely sure if this is the right way to construct NFAs because the concept of having multiple next states is still confusing to me, and I don't know when a state can have more than one next state. Is there a formula of some sorts or is it really all down to just knowing what the next states are?

1

There are 1 best solutions below

0
On

Following Brian M. Scott's comment, you actually get directly the following deterministic incomplete automaton:

$\hskip 90pt$

If you want to get a deterministic complete automaton, just add one state as follows:

$\hskip 80pt$