concatenation of context sensitive and context-free is context sensitive or not?

Question

Assume that $L_1$ is context sensitive language and $L_2$ is context free language, is the language $L_1 * L_2$ context-sensitive or not?

I almost sure that is not, but can't prove it.

Answer 1

Suppose that $L$ is a context-sensitive language which is not context-free. Then $L\{\epsilon\}$ is not context-free (here $\epsilon$ is the empty word), while $L\emptyset$ is context-free.

Answer 2

Claim. The concatenation of two context-sensitive languages is context-sensitive.

Since a context-free language is a context-sensitive language, the concatenation of a context-sensitive languages and a context-free language is context-sensitive.

---

Here is a simple proof of the claim by illustration.

Suppose $L_1$ is given by the following context-sensitive grammar
$\quad S\to abc\mid aAbc$
$\quad Ab\to bA$
$\quad Ac\to Bbcc$
$\quad bB\to Bb$
$\quad aB\to aa\mid aaA$

Suppose $L_2$ is given by the following context-sensitive grammar
$\quad S\to aSbS\mid \epsilon$

Then the concatenation $L_1L_2$ is given by the following context-sensitive grammar.
$\quad S\to S_1S_2$
$\quad S_1\to abc\mid aAbc$
$\quad Ab\to bA$
$\quad Ac\to Bbcc$
$\quad bB\to Bb$
$\quad aB\to aa\mid aaA$
$\quad S_2\to aS_2bS_2\mid \epsilon$

---

Here is a simple formal proof.

Suppose the context-sensitive grammar for language $L_1$ is $(N, \Sigma, P, S)$, where $N$ is a set of nonterminal symbols, $\Sigma$ is a set of terminal symbols, $P$ is a set of context-sensitive production rules, and $S$ is the start symbol. Similarly, $L_2$ is generated by $(M, \Sigma, Q, T)$. Since renaming the nonterminal symbols in a grammar does not change the language generated, we can assume that $N$ and $M$ are disjoint. Then $L_1L_2$ is generated by grammar $(N\cup M, \Sigma, P\cup Q\cup\{X\to ST\}, X)$, where $X$, a nonterminal symbol not in $N$ and $M$ is the start symbol. It is obvious that the production rules in $P\cup Q\cup\{X\to ST\}$ are context-sensitive.

---

Exercise 1. The concatenation of two context-free languages $L_1$ and $L_2$ is context-free.

Exercise 2. The concatenation of two regular languages $L_1$ and $L_2$ is regular.

Answer 3

Yes, the concatenation $L_1*L_2$ is context sensitive in the given case (proof below). However, I am not sure if this is your question, or whether you want to know if $L_1*L_2$ is only context sensitive (and not context free in general), or context sensitive and even contex free. The latter does not hold, see the answer by Yuval Filmus

Proof:

When $L_1$ is context sensitive, then there is an LBA $M_1$ that accepts $L_1$. When $L_2$ is context free, it is in particular context sensitive and there is also an LBA $M_2$ that accepts $L_2$.

Now build a new LBA $M_{1*2}$ that merges $M_1$ and $M_2$ in the following way:

• Alphabet is the union of the individual alphabets,
• set of states is the disjoint union of the individual sets of states (rename if necessary),
• initial state is taken from $M_1$,
• final state(s) are taken from $M_2$,
• Let $s$ be the initial state of $M_2$. For each final state $f$ of $M_1$ and for each symbol $A$ in the alphabet, add a transistion $\delta(f,A) = (s,A,S)$. These transitions allow to "switch machines" from $M_1$ to $M_2$ whenever machine $M_1$ would reach an accepting configuration.
• All other transitions are taken from $M_1$ and $M_2$.

It should be apparent that $M_{1*2}$ accepts $L_1*L_2$. Since it is an LBA, $L_1*L_2$ is context sensitive.