Cheap and Secure Web Hosting Provider : See Now

[Answers] What is the expansion of the regular expression $(a^*b^*)^*$

, , No Comments
Problem Detail: 

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$

Asked By : Nilushan

Answered By : Rick Decker

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64530

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback