Find languages $\ L_1$ and $\ L_2$ such that the lengths equal $\ k+1$

44 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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} \}$