7
$\begingroup$

I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages for example how do i proceed on this kind of question.

Give a context-sensitive (not just length-increasing) grammar for $\{www : w ∈ \{a, b\}^⋆\}$.

Ideas or approaches on how to deal with this kind of questions is much appreciated.

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ Idea: every time you generate an "a", generate also "a'" and "a''" (same goes with "b"s). Now, a'' can switch with a non-primed letter to its right (but not with a primed, or doubled primed one.). At the end, get rid of the primes. $\endgroup$ – Ran G. Dec 5 '14 at 0:52
  • 1
    $\begingroup$ Hint: "www" is not context-free so you'll have to make use of the additional facilities context-sensitive grammars give you. A common theme is switching non-terminal, effectively moving them around the sentence. Hence, it's easy to simular a TM head with the grammar. How would you decide "www" algorithmically? $\endgroup$ – Raphael♦ Dec 5 '14 at 12:43
5
$\begingroup$

Intuitively you want to generate three intermediate symbols at a time, and allow the symbols to sort themselves. Let $S$ be the start symbol. The generation rules are:

$$S \rightarrow S A_1 A_2 A_3$$ $$S \rightarrow S B_1 B_2 B_3$$ The sorting rules are as follows: For symbols $X_i,Y_i \in \{A_1,A_2,A_3,B_1,B_2,B_3\}$ such that $j < i$ add the rule: $$X_i Y_j \rightarrow Y_jX_i$$ In the end we have to turn the intermediate symbols into terminal symbols. Turn the start symbol into another symbol $S_1$ to end the generation phase. $$S \rightarrow S_1$$ Push $S_1$ through the string converting symbols to terminal symbols on the way and increment the subscript when done with one word $w$. For all $i \in \{1,2,3\}$ add the rules: $$S_i A_i \rightarrow a S_i \; | \; a S_{i+1}$$ $$S_i B_i \rightarrow b S_i \; | \; b S_{i+1}$$ The subscript of $S$ ensures that the symbols are converted in the proper order as the subscript can not decrease. In the end remove $S_3$. $$ S_3 \rightarrow \varepsilon $$

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Although your grammar comes close, it is neither contextsensitive (which User_1234 asked for) due to rules such as "$AB \rightarrow BA$" nor monotone due to $S_3 \rightarrow \epsilon$. $\endgroup$ – lukas.coenig Jan 4 '15 at 20:41
  • $\begingroup$ @lukas.coenig The epsilon rule is indeed not allowed (should be easy to fix), but otherwise the grammar is in Kuroda normal form. Not every definition of CSGs admit it, but it's famously an equivalent definition. If the OP (or any reader) has to use another definition, they can use constructions taking from equivalence proofs of the definitions and apply them (mechanically) to this solution. $\endgroup$ – Raphael♦ Feb 18 '16 at 14:00
  • 1
    $\begingroup$ @Raphael. Thank you, but I don't think it is that easy. Consider the word $aaa$ for ex. To obtain that word, you have to start with $S\to SA_1A_2A_3$. The length of this sentential form is 4, while the length of $aaa$ is 3, so somewhere down the road you would have to decrease the length of the sentential form. However, this is not allowed in a context-sensitive grammar since it is non-decreasing, that is, for every production $x\to y$, one must have $\|x\|\le \|y\|$. If I'm not wrong, this means that the solution of jnalanko is all wrong. However, I can't seem to find a correct solution... $\endgroup$ – Barbara May 9 '18 at 8:39
  • 1
    $\begingroup$ @Barbara It seems we're misunderstanding each other. I meant to refactor the whole grammar; you'd start with $A_1^0A_2A_3$; upper indices $i$ would replace "right of $S_i$". Abstractly speaking, all constant-sized "overhead" can be folded into special symbols. (I think.) $\endgroup$ – Raphael♦ May 9 '18 at 13:25
  • 1
    $\begingroup$ @Barbara At this point, I think you should open a new question. If the way from here to what you need is not as simple as I thought it was, a discussion in the comments is not the right way to clarify. $\endgroup$ – Raphael♦ May 9 '18 at 13:26
2
$\begingroup$

The answer for your specific example is there, but the general question remains.

In very many years, in both theoretical and applied computer science, I do not recall having to write a CS grammar as such.

Still, if I may give an advice, it should not be seen at all like producing a CF grammar, were you must contrive the rules to get everything in place and coordinated exactly right as it is produced.

CS grammars are a lot more algorithmic, and you can pretty much mimic a Turing machine (working in finite space, proportional to input size, which means Linear Bounded Automaton - LBA) in order to move things around as needed. So it is much more a programming exercise.

You can pretty much generates the first ingredients to build one of the words in the language, then move them around algorithmically. You can use special symbols (possibly in various flavors corresponding to finite state) to act as heads that you move around with appropriate rules, do as to check what is to be done. And so on.

A good reading may be to look at the proof of equivalence between CSG languages and LBA languages, i.e. the CS languages.

Remember that nearly all algorithms that we work with can be performed by a LBA, hence correspond to a CSG definable language. That should give you an idea of the available algorithmic power.

But a bit of imagination helps elegant solutions, as in the example you gave.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So, for the language provided in User_1234's question, how might one go about designing an LBA for it? I'm only experienced with designing Turing Machines for languages with separators; For example: $\{w\#w\#w:w \in \{a,b\}^*\}$, which seems to make things easier. $\endgroup$ – David Smith Dec 7 '14 at 4:42
  • $\begingroup$ @DavidSmith For $www$ there is a simple specific solution given in the first Ran G comment and with details in the previous solution. This is a bit different from TM which are usually constructed as acceptors (recognizers), while here you want a constructor. One other way to do it is to generate a string $w$, then to add 2 symbols $#$ on one side, and then replace each symbol $#$ by a copy of the string $w$. This is more complex, but it will work for any number of copies of $w$, just by increasing the number of symbols $#$. $\endgroup$ – babou Dec 7 '14 at 9:29
  • $\begingroup$ @DavidSmith A LBA is an acceptor, which you "program" pretty much like a TM. In this case, if you are given $www$ and want to recognize it, you can simply have a first computation that somehow (many ways) count the symbols to place the two $#$ at the right place. Alternatively, you can rely on non determinism, and place the two $#$ in random places on the input string. One choice of them will be good, if the string is in the language. $\endgroup$ – babou Dec 7 '14 at 9:30
1
$\begingroup$

this is just an additional answer that can be thought of as a general solution. CSLs, context sensitive languages are modelled by LBAs, linear bounded automata. a LBA is a Turing machine that can accept or reject given a work tape that is no larger than a constant times the size of the input tape. so if you can figure out a computer program that can process the input in constant space, then its a CSL. idea: a program that would work for this problem would do something like enumerate permutations in constant space.

|cite|improve this answer
$\endgroup$

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.