2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Jun 5 at 13:28
4
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you! for you answer $\endgroup$ – dor navon Jun 5 at 16:26

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.