HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

What's the difference between the concatenation and union of symbols within a language

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewhatunionlanguagewithindifferencebetweenandconcatenationsymbols

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#55601, answer score: 7

Revisions (0)

No revisions yet.