0
$\begingroup$

I need to do an exercise with different questions about the length of languages in theoretical computer science. I got stuck at the first one and don't know how to construct the following.

Let $\ L_1$ and $\ L_2$ be two non-empty languages over an alphabet $\Sigma$ with length of $\ L_1$ equal to $\ k$ and length of $\ L_2$ equal to $\ l$. Give for every $\ k \ge 1$ and an alphabet of your choice an example of $\ L_1$ and $\ L_2$ such that $\ |L_1 \cdot L_2 | = k+1$.

Hope for help, thanks a lot

$\endgroup$
2
  • 3
    $\begingroup$ What do you mean by the "length" of a language, exactly? $\endgroup$ – Math1000 Sep 25 '16 at 11:13
  • 1
    $\begingroup$ Thanks for the question, I was not clear on that one. The length of a language $\ L$ over $\ Sigma $ equals the amount of words in in $\ L$, this is how I understood it, I might be wrong though. $\endgroup$ – gammaALpha Sep 25 '16 at 11:17
2
$\begingroup$

Take $L_1 = \{1, 11, 111, \dots , 1^k\}$ and $L_2 = \{\epsilon, 1\}$.

So You get that $L_1\cdot L_2 = \{1, 11, \dots , 1^k, 1^{k+1} \}$

$\endgroup$
1
  • 1
    $\begingroup$ argh, thanks a lot. I knew it was that easy but I was thinking too far, thanks again! $\endgroup$ – gammaALpha Sep 25 '16 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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