2
$\begingroup$

Find a context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ where $L \in DCSL \setminus CFL$.

I find this task from old exam but there is no solution. I try for solve it for practice, I needed many hour for my solution I write here but I don't think it works.. But I think I almost have it!

So my start symbol is $S \rightarrow AC, BX \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $AC$ end with $a$ and $BC$ end with $b$

$A \rightarrow aAY, bAZ, a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ Create $a$ on the left side

$B \rightarrow aBY, bBZ, b\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ Create $b$ on the left side

$YC \rightarrow aC$

$YX \rightarrow aX$

$ZC \rightarrow bC$

$ZX \rightarrow bX$

$C \rightarrow a$

$X \rightarrow b$

$Ya \rightarrow aY$

$Yb \rightarrow bY$

$Za \rightarrow aZ$

$Zb \rightarrow bZ$

Here we want make sure we move everything to the right so we get the same word.

For example I don't get the wordd $aabbaabb$ and there are some ways so my grammar don't even end.. I mean there are some non terminals left but you can't continue. I hope you can say how do this correct because I don't find it and I try it many hours and I think I have it correct almost..

I also try to make grammar where you make same word twice and sort the second but didn't work either.

Improve this question
$\endgroup$
5
  • $\begingroup$ And what's your question? $\endgroup$
    – Raphael
    Commented Jan 7, 2018 at 22:59
  • $\begingroup$ @Raphael Hi my grammar is almost correct I think but something make it work wrong and I don't know what is the problem how it can be fixed the grammar? $\endgroup$
    – eyesima
    Commented Jan 7, 2018 at 23:02
  • $\begingroup$ Why do you think that? Have you tried proving it correct? $\endgroup$
    – Raphael
    Commented Jan 7, 2018 at 23:12
  • $\begingroup$ @Raphael I don't do proof it (by induction like in the link proposed) but I try several different word that are accepted by the language. Some did work very well ($aaaa, bbbb, aabaab$) but some didn't work ($aabbaabb$) and for some word my grammar don't ended at all.. :( From this I know something don't work good or is missing. $\endgroup$
    – eyesima
    Commented Jan 7, 2018 at 23:18
  • $\begingroup$ Here is a possible solution based on Kuroda normal form. $\endgroup$
    – Mapio
    Commented Feb 20, 2019 at 15:47

0

Reset to default