0
$\begingroup$

FA
$r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$

For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, then i used FSM2Regex which gave me $r_3$ which i simplified into $r_2$ using regex simplifier.
now $r_2$ seems better than $r_1$. Should I go with it? If so, what is lacking in $r_1$? I can't see the difference between $(a+b)^*b$ from $r_1$ and $(aa^*b)^*$ from $r_2$. Is one the subset of other? Are they overlapping or disjoint?

Inputting any of the three RE's back into FSM2Regex gives RIDICULOUSLY complex TG's especialy because for some reason that is beyond me, it also draws $\$$ (null string) transitions. Even $r_3$ doesn't give back the FA I used to generate it. So my question is : are $r_1$ and $r_2$ different? How? what should I go with?

$\endgroup$
  • $\begingroup$ 1) Tool requests are offtopic here. 2) The backtick has a different meaning in LaTeX; there is no Markdown nested in MathJax. You can get a plain dollar in LaTeX by \$. $\endgroup$ – Raphael Dec 1 '18 at 13:29
  • $\begingroup$ @Raphael , are tool requests completely disallowed on all SE sites or is there some place where you discuss that stuff? also, i don't know if there's some way to PM/chat other user for general discussion, so is there? $\endgroup$ – Awaisome Dec 2 '18 at 1:55
  • $\begingroup$ @Awaisome There's Software Recommendations, but I don't know how they do for specialized requests like TCS-specific tasks. For chatting, there's Computer Science Chat; you'll need a modest amount of reputation across the whole network to join, though. $\endgroup$ – Raphael Dec 2 '18 at 11:45
  • 1
    $\begingroup$ @Raphael, Awaisome: Software Recommendations accepts questions about highly specialized software, but the likelihood of finding someone who can answer is not high. If you consider posting there, do read the question guidelines. $\endgroup$ – Gilles 'SO- stop being evil' Dec 3 '18 at 19:35
1
$\begingroup$

Yes, the regular expressions $r_1=\Lambda+(a+b)^*b$ and $r_2=(b+aa^*b)^*$ are equivalent. There are several ways of doing this.

  1. Just observe that both of them match the empty string and all strings ending with $b$.

  2. Convert them to automata and then produce automata for $L(r_1)\setminus L(r_2)$ and $L(r_2)\setminus L(r_1)$. Minimize both automata and find that they both accept the empty language. (Actually, you'll find that you make a ton of mistakes and at least one of the automata accepts something, and at least one of the minimizations is wrong. But, if you were a computer, this wouldn't be an issue.)

  3. Clearly both regular expressions match the empty string, so let's show that they match the same non-empty strings, too. Suppose that $w\in L(r_2)\setminus\{\Lambda\}$. Then we can write $w=w_1\dots w_\ell$ where each $w_i$ is a string that either matches $b$ or $aa^*b$. In particular, $w_\ell$ must match one of these things, so the last character of $w_\ell$ is a $b$, so $w\in L(r_1)$.

    Conversely, suppose that $w\in L(r_1)\setminus\{\Lambda\}$. Write $w=s_1\dots s_n$, where each $s_i\in\{a,b\}$. Suppose there are $\ell$ $b$s in $w$ and let these be at positions $p_1, \dots, p_\ell$. Because $w\in L(r_1)$, $p_\ell=n$ (the last character is $b$). For convenience, let $p_0=1$. We can now write $w=w_1\dots w_\ell$, where $w_i=s_{p_{i-1}+1}\dots s_{p_i}$. For each $i\in\{1, \dots, \ell\}$, we have $w_i=a^{p_i-p_{p-1}-1}b$, so each $w_i$ matches either the regular expression $b$ or $aa^*b$. Therefore, $w$ matches $(b+aa^*b)^*= r_1$.

By the way, a fourth equivalent regular expression is $(a^*b)^*$, which you can see by observing that the inner part of $r_1$ is equivalent to $b+a^+b$, which is $a^*b$.

$\endgroup$

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.