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

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.

• What do you think? – Yuval Filmus Jun 5 '19 at 13:28

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.

• Thank you, I edited the qustion – dor navon Jun 5 '19 at 14:04
• @dornavon Please don't edit the question to invalidate existing answers. It's impolite to the answerers, and may also confuse future readers. – xskxzr Jun 7 '19 at 4:36

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.

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.

• thank you! for you answer – dor navon Jun 5 '19 at 16:26