[Solved]: What's the difference between the concatenation and union of symbols within a language

Problem Detail: 

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?

Asked By : trungnt

Answered By : Ran G.

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.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents