minimal DFA with four states

95 Views Asked by At

I want to minimal this DFA: enter image description here

But i don't know what to do. Anyone can help me?

Thanks

2

There are 2 best solutions below

0
On BEST ANSWER

The DFA accepts any string containing at least one $a$, so

enter image description here

should work.

0
On

A more general approach to solve minimisation of a DFA goes as follows:

  1. get rid of unreachable states. ($p \in Q$ is unreachable $\Leftrightarrow \forall s \in \Sigma^*: \delta^*(q_s, s) \neq p$)
  2. group all indistinguishable states and merge every group of mutually indistinguishable states to one new state. ($p$ and $q$ are indistinguishable if $\forall w \in \Sigma^*: \delta^*(p,w) \in F \Leftrightarrow \delta^*(q,w) \in F$)

To find indistinguishable states, algorithms of Hopcroft, Moore or Brzozowski could be used...