Let $L = \{ w^m \mid m = 2k +1, k \ge 1 \}$. Please give some idea to write a Context sensitive grammar for $L$. Will it be like $L' = \{www \mid w \in \{a, b\}^*$? Then for each $w$ we have to introduce one nonterminal?

  • $\begingroup$ Yes, the idea for www carries over. $\endgroup$ – Raphael Feb 22 '16 at 13:38
  • $\begingroup$ No, we cannot introduce one non-terminal for each $w$. We need to find a way without introducing $m$ non-terminals. Because $m$ can be as large as possible. $\endgroup$ – Shreesh Feb 22 '16 at 17:23
  • $\begingroup$ Also, as Raphael mentioned, please specify $w$ as $\{a,b\}^*$ in $L$, because I think that is what you want. I mentioned $w$ being fixed as a joke. Actually you can have $w \in L'$ for any context-sensitive-language $L'$. $\endgroup$ – Shreesh Feb 22 '16 at 17:25
  • 1
    $\begingroup$ Like @Raphael says, the idea for www carries over. As a first step, make your grammar create a string of an odd number of $A$ (as "seeds" for the words), and then use the same idea as for a word repeated thrice. $\endgroup$ – vonbrand Feb 23 '16 at 13:44
  • $\begingroup$ @vonbrand Most copy grammar for www like this one (cs.stackexchange.com/questions/33853/…) use as many non-terminals as the number of copies like $A_1A_2A_3$. So, at least that idea does not carry over. $\endgroup$ – Shreesh Feb 23 '16 at 16:33

If $w$ in the question is a fixed string (or even from a finite set of finite strings) then you can write a context free grammar for it. Every context free grammar is also a context sensitive grammar. So following grammar suffices.

$S \rightarrow wwS\ |\ w$

If $w \in \{a,b\}^*$ then you will have to do something like (https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language) but with variable number of copies.

Also first try to solve for $L = \{w^m\ \ | \ \ m\geq 1, w \in \{a,b\}^*\}$.

It should be possible to write a context-sensitive-grammar because we can easily construct a linear bounded automata. Write $1^m$ non-deterministically in a separate track, copy it as $0^m$, $1^m$, $0^m$ through out the tape in that track, and then check it all contain the same copy of $w$ in the input track. (note you can also ensure odd number of copies here). Also note that even though we may not go right or left of input, we can still use different tracks by choosing a larger tape alphabet.

With this program if we apply the Myhill-Landweber-Kuroda Theorem (A language is accepted by a LBA iff it is context sensitive) we can easily get a context sensitive grammar.

Or taking ideas from the LBA, we can write the CSG in following way: first generate something like $BA_aA_bA_aA_a...A_aFDD...$ odd number $...DE$. Then whenever $A_a$ and $A_b$ transpose with $D$ they will leave behind $a$ and $b$. $D$ will start transposing only when it is touched by marker $F$ which will turn to $G$ to prevent further transposing. $D$'s will generate $a$' and $b$'s until it toucher $B$. $D$'s will create marker $H$ when they touch $B$, $H$ will move right and when it encounter $A_a$ or $A_b$ it will become $I$. $A_a$'s and $A_b$'s will have to move to the right of $a$'s and $b$'s to enable $I$ to get to $G$. This $I$ when it touches $G$, it will become $F$ which will start another round of substituting and generating $w$. $A_a$'s and $A_b$'s will vanish when they touch $E$. $B$ stands for beginning symbol, $D$ for delimiter symbol, and $E$ for end symbol. So combining all the ideas you get the following (We treat the case $w = \epsilon$ separately):

$S \rightarrow BTFUE \ | \ \epsilon$
$T \rightarrow TA_a\ |\ TA_b\ |\ A_a\ |\ A_b$
$U \rightarrow UDD\ |\ D$

Above is a straight forward CFG to generate the pattern that we want. Now are CSG rules. I will write the rules as non-contracting grammar.

$FD \rightarrow DG$
$A_aD \rightarrow DaA_a$
$A_bD \rightarrow DbA_b$
$aD \rightarrow Da$
$bD \rightarrow Db$
$A_aa \rightarrow aA_a$
$A_ab \rightarrow bA_a$
$A_bb \rightarrow aA_b$
$A_bb \rightarrow bA_b$
$BD \rightarrow BH$
$Ha \rightarrow aH$
$Hb\rightarrow bH$
$HA_b\rightarrow A_bI$
$HA_a\rightarrow A_aI$
$IA_a\rightarrow A_aI$
$IA_b\rightarrow A_bI$

Now a few more rules which do not follow the rules of non-contracting grammar.

$IG \rightarrow F$
$FE \rightarrow E$
$B \rightarrow \epsilon$
$A_aE \rightarrow E$
$A_bE \rightarrow E$
$E \rightarrow \epsilon$

If we convert the above grammar to a non-contracting grammer we can then convert it to a CSG for the language. This can be done if we do not use markers ($B$, $E$, $D$, $F$, $G$, $H$, and $I$, markers or their avatars need to be removed by replacing with $\epsilon$ at the end of production) but instead use real symbols for markers. The idea remains the same but the grammar becomes a little more complicated. $D$'s, $E$ and $F$ should stand for last letter of $w$, $B$ should stand for first letter of $w$. The last run should generate $w$ while vanishing $A_a$ and $A_b$.

  • $\begingroup$ "If w in the question is a fixed string" -- good point. I doubt that's what the OP is required to do; they should clarify. $\endgroup$ – Raphael Feb 22 '16 at 13:39
  • $\begingroup$ FWIW, we also have a post on finding a CSG for www. $\endgroup$ – Raphael Feb 22 '16 at 13:40
  • $\begingroup$ CSG for fixed number of copies is easy, but of variable number of copies is a little difficult. Even though CSL's are closed under union, we can't say the same about an infinite union. $\endgroup$ – Shreesh Feb 22 '16 at 13:57

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.