MHB What is the General Form of the Language Recognized by the Given Automaton?

[evinda]

Hello! (Wave)

I want to write the language of the automaton with the following transition function in regular form with $A$ as an initial state and $B,D$ as final states.

$$\delta:\begin{matrix}
& & 0 & 1\\
& A & B & C\\
& B & C & D\\
& C & D & B\\
& D & D & C
\end{matrix}$$

I have drawn the following dfa:

View attachment 5848

Some of the words that the automaton recognizes are the following:

$$0,11,10,000,01,010^{\star},0000^{\star}, 111, 101110$$

How can we find the general form of the words of the language? (Thinking)

 

[Evgeny.Makarov]

You can use the procedure from the proof of Lemma 1.60 (p. 69) in Sipser's book.

 

[evinda]

I read it. I tried the following:

The first GNFA that we get is this:

View attachment 5857

Then if we choose to remove C we get:

View attachment 5863

Then by removing A we get:

View attachment 5864

Then by removing B we have:

View attachment 5860

Finally by removing D we get:View attachment 5865

Is the last expression that I found the right language? Or have I done something wrong?