0
$\begingroup$

I am given this exercise:

Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2.

w1

w2=aabbcc

w3=abbccw

w4=aabbcccc

w5=ccaabb

w6=ab

So far I haven't seen such a notation for languages as the one that L1 and L2 are seen in. For example, I had seen other notations such as: L1={w∈{a,b}∗: every a in w is immediately preceded and followed by a b} which I could understand. A parallel between the two notations will be much appreciated.

Moreover, what does it refer by L1L2? Is this counted as a union or a concatenation?

What I could figure out from this exercise is what w1 is surely not in L1L2, as k must be over 1. Following the same logic, the other answer would be w2 as k will always be the same in both L1 and L2, hence the number of a's, b's and c's shouldn't differ.

Is the above thought correct or is it more to this notation than I have already thought of?

$\endgroup$

2 Answers 2

3
$\begingroup$

Language concatenation is defined as follows: $$ L_1 L_2 = \{ w_1 w_2 : w_1 \in L_1, w_2 \in L_2 \}. $$ In other words, a word $w$ belongs to $L_1 L_2$ if it can be written as the concatenation of two words, $w_1 \in L_1$ and $w_2 \in L_2$.

This definition should suffice for solving the exercise.

$\endgroup$
2
$\begingroup$

So far I haven't seen such a notation for languages as the one that L1 and L2 are seen in. For example, I had seen other notations such as: L1={w∈{a,b}∗: every a in w is immediately preceded and followed by a b} which I could understand. A parallel between the two notations will be much appreciated.

Exponents in alphabet symbols denote quantities. They are just a way to simplify/synthesize the more verbose definitions that you mentioned.

Moreover, what does it refer by L1L2? Is this counted as a union or a concatenation?

$L_1L_2$ means concatenation.

What I could figure out from this exercise is what w1 is surely not in L1L2, as k must be over 1. Following the same logic, the other answer would be w2 as k will always be the same in both L1 and L2, hence the number of a's, b's and c's shouldn't differ.

The $k$s for $L_1$ and $L_2$ are two different constraints, so, the quantities of as and bs are not related to the quantity of cs. The concatenation of these two languages could be defined like:

$$ L = \{a^kb^kc^i: k > 0, i > 0 \} $$

$\endgroup$
3
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. (Even my #1 reference for USAmerican English doesn't know sintetize, and there's a numerus error in denotes. (There is another typing error my spelling checker does flag.)) $\endgroup$
    – greybeard
    Oct 9, 2020 at 5:20
  • $\begingroup$ @greybeard Hi! Thanks for your advices. Indeed, my english is pretty rusty nowadays. My reading and listening are pretty good, but my writing I can't say the same. I corrected my mistakes :D $\endgroup$ Oct 10, 2020 at 14:18
  • $\begingroup$ (I appreciate the effort - you missed not related to the quantity os cs.) $\endgroup$
    – greybeard
    Oct 10, 2020 at 16:45

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.