3
$\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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Are you sure you mean union and concatenation, rather than the kleene star (or, closure)? $\endgroup$
    – Ran G.
    Commented Apr 7, 2016 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
    Commented Apr 7, 2016 at 0:41
  • 1
    $\begingroup$ I'd still recommend you review the definition of kleene star, union and concatenation as sets. $\endgroup$
    – Ran G.
    Commented Apr 7, 2016 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
    Commented Apr 7, 2016 at 7:41

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.