Convert automaton to regular expression

Question

Given is a (finite state) automaton $M=(\{0,1,2,3\},\{0,1\},d,0,\{1\})$

$$d(0,0)=2, d(1,0)=3,d(2,0)=0,d(3,0)=1,d(0,1)=1,\\ d(1,1)=0,d(2,1)=3,d(3,1)=2$$ $d(i,j)=k$ means that when in state $i$, will move to state $k$ after input $j$.

I need to find the language accepted by this automaton.

After I draw the automaton I got the regular expression(11+0(11)*0)*1(00)* using Thompson's construction.

Will this automaton accept all strings that have total number 1 odd such as 1,3,5,7 ->2n+1?

Answer 1

Some trial an error gives these observations, letting $L \subseteq \{0,1\}^\ast$ be the accepted language:

• $1 \in L$.
• $x \in L \implies (00x \in L \land x00 \in L)$.
• $x \in L \implies (11x \in L \land x11 \in L)$.
• $x \in L \implies (0101x \in L \land x0101 \in L)$.
• $x \in L \implies (1010x \in L \land 1010x \in L)$.
• $x \in L \implies (1001x \in L \land x1001 \in L)$.
• $x \in L \implies (0110x \in L \land x0110 \in L)$.

This suggests to me that probably $$L = \{x \in \{0,1\}^\ast: \text{ number of 1's is odd and number of 0's is even}\}$$

which you might be able to show by induction.

A regex is probably best found by some algorithm. (IIRC THompson's construction goes from a regex to a NFA, so the other way around and to another class of automata).

Answer 2

By investigation, we have

• $q_0$ is the state of even number of 0s and even number of 1s,
• $q_1$ is the state of even number of 0s and odd number of 1s,
• $q_2$ is the state of odd number of 0s and even number of 1s,
• $q_3$ is the state of odd number of 0s and odd number of 1s.

With these identifications you should be able to construct a proof by induction.

Answer 3

To solve this, I will convert the automaton into a GNFA. There are a few rules to remember when constructing a GNFA:

1. Add a new start state which has $\epsilon$-transitions to every start state but itself.
2. There is only a single accept state.
3. All accept states has a transition to the new accept state, but there are no leaving transitions from the new accept state.
4. Except for the start state and the accept state, every state has a transition going to every other state and also a transition leading to itself. If there are no transition between two states, a $Ø$-transition is added.

If two states are not connected, we add a $Ø$-transition in between them.

You haven't given the accept states, so I will just assume the accept states are state 2 and 3. Below is seen a GNFA constructed by the given states and transitions ($Ø$-transitions are not shown for simplicity):

From now on, we remove on state one by one. For example, we can remove state 0, so we would get a transition from the start state to state 2. To do so, we label the transitions that will be removed. $q_1$ is the transition from the start state to state 1, $q_2$ is the transition going from state 0 to itself, $q_3$ is the transition going from state 0 to state 2, and $q_4$ is the transition going from state 2 back to the start state (which does not exist for this particular case). Now, all these transitions must be replaced by one transition that has the label $q_1q_2^*q_3 \cup q_4$.

Remember, when removing state 0, we have to do the same procedure for state 1 to state 2 via state 0, state 1 to state 3 via state 0, state 1 to state 1 via 0, state 3 to state 1 via state 0, state 3 to state 2 via state 0, state 3 to state 3 via state 0, state 2 to state 1 via state 0, state 2 to state 3 via state 0, and state 2 to state 2 via state 0.

Below is seen the result of removing state 0:

You can continue to do this until you only have the start state and the accept state remaining. The resulting regular expression is the label for the only transition left between the start state and the accept state.

Answer 4

One way would be convert to NFA to GNFA and step by step delete states until you reach to two state and the label on the arrow would be the REGEX of the language as Martin Pekar has explained. I did so and got a very long expression which I didn't bother myself to type it down or simplify it (ridiculously long expression), because here we can solve it in an smarter way: As you can observe, regardless of any state that you are in, if you see two consecutive $0$'s or two consecutive $1$'s, they cancel out each other and you stay put. So basically you can simplify any given string by deleting any pairs of $00$'s or $11$'s until there is no more pair left. Now, our input is just basically an alternation of $0$'s and $1$'s. Now, assume you are working with only simplified inputs: So it accepts $1(0101)^{*}\cup 010(1010)^{*}$. Now, in order to get the all strings, add arbitrary pairs of $00$ or $11$ anywhere you want with any abundance.