3
$\begingroup$

Consider the regular expression $(a^*b^*)^*$

Does this mean that there are zero or more occurences of the term $(a^*b^*)$ before the term is expanded or that there are zero of more occurences of the term $(a^*b^*)$ after the term itself has been expanded?

Here is an example of what I'm try to say

zero or more occurences of $(a^*b^*)$ BEFORE expanding $(a^*b^*)$ $(a^*b^*)^* = a^*b^*a^*b^*a^*b^* = aababbab$

or

Zero or more occurences of $(a^*b^*)$ AFTER expanding $(a^*b^*)$ $(a^*b^*)^* = (aab)^* = aabaabaab$

$\endgroup$
5
$\begingroup$

Expand the outer starred expression first and then expand the terms. If $r$ is a regular expression, then $r^*$ denotes the language consisting of zero or more copies of $r$, concatenated together, so $r^*$ could take the form $\epsilon$ (the empty string, resulting from no copies of $r$) or $r$ or $rr$ or $rrr$, and so on.

In your example, with $r=a^*b^*$, then $r$ denotes all the strings consisting of zero or more $a$'s, followed by zero or more $b$'s, and so $(a^*b^*)^*$ will denote all possible concatenations of terms $(a^*b^*)$. For example, one possible concatenation would be $(a^*b^*)(a^*b^*)(a^*b^*)$ and then after expanding each term, we might have $(abb)(aab)(bbb)=aabaabbbb$.

By choosing to expand the inner term and then concatenating the results you will likely miss the general form. If, for example, we chose a particular string in $r$ and then concatenated them, we might replace $r=a^*b^*$ with $abb$. Then, if we concatenated just those terms three times, we'd have $(abb)(abb)(abb)$. While this is in the language $(a^*b^*)^*$, it is of a special form that doesn't capture the full generality of strings in the language.


While it's not directly related to the question you asked, it's worth noting that $(a^*b^*)^*=(a\mid b)^*$ (some authors would write $(a\mid b)$ as $(a\cup b)$ or $(a+ b)$). In other words, $(a^*b^*)^*$ denotes the language consisting of all possible strings over $a$ and $b$. Can you see why?

$\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.