4
$\begingroup$

I understand the differences between Regular, Context-Free, and Context-Sensitive languages. Designing a Regular Grammar can be easier if you have a DFA. Designing a CFG isn't too hard for the palindromic strings, but not easy per say for other combinations. But when asked to produce a CSG for Context-Sensitive language (not regular, not context-free), with restrictions on the terminals with respect to other terminals, it becomes difficult. I'm having trouble coming up with the production rules.

Is there some recommended process or method that people use to come up with the rules? Or do they just keep trying out example strings to "capture the essence" of them?

I would post an example, but this is for an assignment, so I can't give it away. In general I would just like to be better at coming up with the grammars.

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! This is exactly the right way to ask a homework question: not "Here's my homework exercise. Do it for me." but "Please explain this thing for me, so I can do my homework better, on my own." We should frame this and put it on the wall. 😃 $\endgroup$ – David Richerby Feb 3 at 20:29
  • 3
    $\begingroup$ Unfortunately, I suspect the answer is "no". My guess would be that 98% of the CSGs that have ever been written were homeworks of computation theory students, and 50% of the rest were by the professors of their courses. But I hope somebody can post a proper answer. $\endgroup$ – David Richerby Feb 3 at 20:33
  • 1
    $\begingroup$ We know that a language is context-sensitive iff it can be accepted in nondeterministic linear space, so outside of a homework context, usually it's enough to design the latter. I suggest hinting to the professor that perhaps it's time to take context-sensitive grammars off the curriculum. $\endgroup$ – Yuval Filmus Feb 4 at 3:39
2
$\begingroup$

The hint by Yuval in his comment is the right one. An approach to writing context-sensitive grammars is to design them like a machine. Send messages over the string. This is very close to writing a linear bounded automaton (or linear space Turing machine). In such a machine the reading/writing head scans over the tape while updating the string. This head (with the machine state) can be modelled by a production, like $ap\to qb$ for "in state $p$ while reading $a$, write $b$ and move left, changing state to $q$", where we assume the state is written to the right of the position of the head.

There are differences. The CSG is more flexible as one can insert letters in the middle of the string, and moreover there can be parallel processes going on at the same time. The latter can be a nuisance when arguing the approach is correct.

Lets see how the messages work in an example: $L = \{ww\mid w\in\{a,b\}^*, |w|\ge 1 \}$, or squares.

Start with left and right sides of the string with the rule $S\to LR$. As markers and messengers cannot disappear in a CSG they must represent a letter in the final string. This letter can be $a$ or $b$ so we have two rules instead: $S\to L_aR_a\mid L_bR_b$. Now the left marker generates new letters and a messenger that becomes a copy at the other half of the string. $L_\sigma\to L_\sigma aM_a\mid L_\sigma bM_b$. Everywhere in these rules $\sigma,\tau$ may take the values $a,b$. Messengers move over other letters: $M_\sigma\tau\to \tau M_\sigma$. At the beginning of the second half write the letter: $M_\sigma R_\tau \to R_\tau \sigma$.

We should end the derivation by removing the boundary markers $L_\sigma\to\sigma$, $R_\sigma\to \sigma$. We have a problem when the right marker is gone, while there is still a messenger under way. This can be solved by extra symchronization. However, no terminal string will be generated this way; the drivation is lost, so there is no real problem.

I tried a similar approach here for the language $\{a^ib^jc^{ij} \mid i,j\ge 1\}$. Here a hint for squares (numbers) $\{a^{n^2} \mid n\ge 1\}$. As you see, I practise a lot.

PS. I hope you mean a monotonic grammar rather than a "real" context-sensitive one. Those are harder, but there is a standard (boring) transformation.

$\endgroup$
  • $\begingroup$ Thank you for your reply. Yes, monotonic. $\endgroup$ – delrocco Feb 4 at 15:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.