gotchaMinor
What's the difference between the concatenation and union of symbols within a language
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?
(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.
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.