4
$\begingroup$

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. Substrings can overlap, so $010$ is in the language but, e.g., $01101$ is not.

I've worked on a DFA where I can move on to create the RE. Here is my DFA:

enter image description here

I'm trying to use Arden's theorem to get the regular expression but I'm stuck. This is how I'm thinking:

\begin{align*} a_1 &= 0a_2 + e\\ a_2 &= 0a_3 + 1a_5\\ a_3 &= 0a_3 + 1a_4\\ a_4 &= 0a_3 + 1a_4\\ a_5 &= 0a_6 + 1a_5\\ a_6 &= 0a_6 + 1a_5\,. \end{align*} I dont describe $a_7$, the "sink state" because it only results in the empty set.

My problem here is that I will never be able to get describe the language because of how $a_3$, $a_4$ ,$a_5$, $a_6$ are? Where did I go wrong?

After some work, I came to this solution, is it correct?

$$0 + 00(11^*0 + 0)^* + 01(1 + 00^*1)^*00^*$$

$\endgroup$
5
$\begingroup$

Part of your confusion stems from the fact that there are two different formulations of Arden's Lemma, which I'll call LR and RL. To illustrate them, let's take a simple FA with three states, $P,Q,R$, where $P$ is the start state and $R$ is the only final state. The transitions are $$\begin{array}{c|cc} & 0 & 1\\ \hline P & Q & \varnothing\\ Q & R & Q\\ R & R & R \end{array}$$ It's clear with a moment's thought that the language accepted by this FA is denoted by the regular expression $01^*0(0+1)^*$, so let's see what the two versions of Arden's Lemma produce.

LR: In this version we generate the regular expression from left to right. If we have a state $X$ with a transition on $a$ to state $Y$ we will include the equation $X=aY$, along with any other terms that arise from transitions from $X$ to other states. Along with this, we add a "$+\epsilon$" to the expression for $X$ if $X$ happens to be a final state. Having made the collection of equations, we may apply the simplification rule that says that whenever we have $X=rX + s$ for regular expressions $r, s$ we can replace the equation by its solution $X=r^*s$. Note that here the goal is to product a regular expression for the start state.

In the example above, we'll have the equations $$\begin{align} P&=0Q\\ Q&=0R+1Q\\ R&=(0+1)R+\epsilon & \text{since R is final} \end{align}$$ Substituting, we see that $R=(0+1)^*\epsilon = (0+1)*$ and $Q=1^*(0R)=1^*0(0+1)^*$, and finally $P=0Q=01^*0(0+1)^*$, as we expected.

RL: In this version we construct the regular expression from right to left. The difference is that if we have a state $X$ with transition on $a$ to state $Y$ we include the equation $Y=Xa$, along with any similar terms. In this case, we add the "$+\epsilon$" only to the start state's equation and the substitution in this case says that if we have $X=Xr+s$ we have the solution $X=sr^*$.

Returning to our example, we'll have $$\begin{align} P&=\epsilon & \text{since $P$ is the start state and has no incoming transitions}\\ Q&=P0+Q1\\ R&=Q0+R(0+1) \end{align}$$ Now our goal is just opposite of what we had in the LR version: we want an expression for the final state, $R$. Working from the top down we have $Q=Q1+P0=Q1+0$ so $Q=01^*$ and $R=Q0(0+1)^*=01^*0(0+1)^*$: the same result generated in a different order.

Assuming you want to use the LR version, your equations should be $$\begin{align} a_1&=0a_2\\ a_2&=0a_3+1a_5+\epsilon\\ a_3&=0a_3+1a_4+\epsilon\\ a_4&=0a_3+1a_4\\ a_5&=0a_6+1a_5\\ a_6&=0a_6+1a_5+\epsilon \end{align}$$ As for your problem with $a_5, a_6$, for example, we could do this: $$\begin{align} a_5 &= 1^*(0a_6)=1^*0a_6 & \text{Arden}\\ a_6 &= 0^*(1a_5+\epsilon) &\text{Arden again, now substitute $a_6$}\\ a_5 &= 1^*0[0^*(1a_5+\epsilon)]\\ &= (1^*00^*1)a_5+1^*00^* &\text{so we have}\\ a_5 &= (1^*00^*1)^*1^*00^* \end{align}$$

$\endgroup$
  • $\begingroup$ Hey can you check if I did correct here? Now i tried the other version, LR. Picture 1: imgur.com/xnyaBvB Picture 2: imgur.com/5v1rdN9 What do u think? And thanks for the explanation of the different ardens, really helped! $\endgroup$ – Ludvig W May 11 '16 at 19:31
  • $\begingroup$ @Lurr. Your regular expression was different from mine, but that's the result of doing substitutions in a different order than I did. At first glance, though, it seems pretty good. $\endgroup$ – Rick Decker May 11 '16 at 19:38
4
$\begingroup$

You can also do this noticing that a binary strings has exactly as many "01" substrings as "10" substrings iff it starts with the same character it ends with. Since you also need the first character to be 0, it's exactly the set of words that start and end with 0 :

$$L = 0(0+1)^*0$$

$\endgroup$
  • $\begingroup$ Thanks David ! I've edited accordingly. Do you think I should prove my observation ? $\endgroup$ – wazdra Jan 22 '18 at 17:33
  • $\begingroup$ It seems fairly obvious, once somebody tells you it's true, so I don't think it needs a proof. But, if you want to add one, go for it. $\endgroup$ – David Richerby Jan 22 '18 at 17:38
2
$\begingroup$

Converting a finite automata into regular expression is not a trivial problem. However, there are many ways in which one can proceed, discussed here.

The one I think will work best for this FSM is State Elimination Method. Go ahead and remove all states one by one other than initial and final states, preserving the path between states. It's always a better idea to convert such a FSM into NFA with $ \epsilon $-moves with only one initial and final state. This way after elimination you will be left with only two states.

Here I am including the FSM after eliminating couple of states, specifically states numbered as $4$ and $5$.

enter image description here

Note that $q_f$ is a single final state obtained by introducing $\epsilon$-moves on three final states in original design of FSM.
Proceed by eliminating state $3$ and $5$ and at last state $2$ to obtain the solution of this problem.

Comment in case you get stuck at some point and want me to include complete answer. I strongly recommend you to do some simple practice problems using this method before you make an attempt to solve this particular problem.

$\endgroup$
  • $\begingroup$ Yeah ive heard about that method tho, but the thin is we dont really learn it in the course im taking. Ill edit the post with my new solution, I think its correct, do u mind checking? Im using ardons theorem btw. $\endgroup$ – Ludvig W May 11 '16 at 19:12
  • $\begingroup$ Ill upload the pictures of my new solution to IMGUR, here are the links, they are two pics long. imgur.com/xnyaBvB imgur.com/5v1rdN9 These two pictures show my solution, is it correct? $\endgroup$ – Ludvig W May 11 '16 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.