2
$\begingroup$

I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression

(a + b)* (abba* + (ab)*ba)

Can someone clarify to what union is compared to concatenation? Looking at

(a + b)*

Is it { $\epsilon$, a, b, ab, ba, aa, aab, bbb...)? I just want to make sure, for union, that I can have any combination of a and b in whichever order.

Can I also have an example of what a word from this language may be? From what I gathered

aaababbaabbaababba

abbaba

bba

ba

would all be valid words in the given language, correct?

$\endgroup$
  • 1
    $\begingroup$ Are you sure you mean union and concatenation, rather than the kleene star (or, closure)? $\endgroup$ – Ran G. Apr 7 '16 at 0:35
  • $\begingroup$ @RanG. I feel like I have a good grasp of how kleene star works. I just wanna make sure I understand how (a+b)* works as opposed to (ab)*. I think I do understand it overall, but just need verification/think aloud. $\endgroup$ – trungnt Apr 7 '16 at 0:41
  • 1
    $\begingroup$ I'd still recommend you review the definition of kleene star, union and concatenation as sets. $\endgroup$ – Ran G. Apr 7 '16 at 0:47
  • $\begingroup$ If you understand the Kleene star, you have to understand concatenation. I'm confused as to what your question is then. Look at the definitions and apply them recursively. It's not very helpful to play through a finite set of examples of arguments to the Kleene star -- there are infinitely many, and it works for all of them. $\endgroup$ – Raphael Apr 7 '16 at 7:41
5
$\begingroup$

Simply put,

the kleene star of concatenation gives $$(ab)^* = \{\epsilon, ab, abab, ababab, ...\} $$

while the kleene star of union gives $$(a+b)^* =\{\epsilon,a,b,aa,ab,ba,bb,\ldots\}$$

so you got it correctly, and indeed all the words you write belong to the language.


Recall that for any two sets $L,K$ we have
$LK = \{xy \mid x\in L, y\in K\}$,
$L+K = L \cup K$,
$L^* = \{\epsilon\} \cup L \cup L^2 \cdots$.

and recall that the regular expression "a" corresponds to the set $\{a\}$ and operations between regular expressions correspond to the above operations on sets.

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