0
$\begingroup$

I need to prove (or disprove, but I think those are proves), that the regular expression:

r = (a+b)*b(a+b)*a(a+b)* (where + is OR and * is Kleene star) 

is equivalent to those expressions:

r' = (a+b)*bb*a(a+b)* r'' = a*b(a+b)*ab* 

The prove needs to be done by two-sided containment (that is, prove that L(r) is in L(r') and vice versa). Any help would be appriciated.

Thanks in advance

1 Answers 1

1

Let $\Sigma = \{a,b \}$.

Note that $s \in L(r)$ $\iff$ $s_k \in \Sigma$ for all $k$ and there exists $i such that $s_i=b$, $s_j=a$.

A moment's reflection shows that, without loss of generality, we may assume $s_i = s_{i+1} = \cdots = s_{j-1} = b$.

If $s \in L(r') \cup L(r'')$, then it is clear that $s$ has the form $s = \omega_1 b \omega_2 a \omega_3$, where $\omega_k \in \Sigma^*$, and so $s \in L(r)$. Hence $L(r') \cup L(r'') \subset L(r)$.

Now suppose $s \in L(r)$. From the above reflection, we see that $s$ has the form $s=\omega_1b b^* a \omega_2$, with $\omega_k \in \Sigma^*$. Hence $ s \in L(r')$. Now let $i$ be the first index such that $s_i = b$ and let $j$ be the last index such that $s_j = a$. (Since $s \in L(r)$ we know that such indices exist and that $i < j$.) Then $s$ has the form $a^* b \omega_1 a b^*$, with $\omega_1 \in \Sigma^*$. Hence it follows that $s \in L(r'')$.

  • 0
    OK I see it now, thanks alot man2012-11-22