patternMinor
Context-sensitive grammar for the language of words concatenated with themselves
Viewed 0 times
theconcatenatedwithwordslanguagegrammarforcontextsensitivethemselves
Problem
I'm looking for a context-sensitive grammar that describes the following language:
$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .
I've got problems with the fact that no rules such as $X \to \varepsilon$ are allowed and therefore I can't place any nonterminal indicating the "middle" of the word. Is there any trick to the problem?
$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .
I've got problems with the fact that no rules such as $X \to \varepsilon$ are allowed and therefore I can't place any nonterminal indicating the "middle" of the word. Is there any trick to the problem?
Solution
Indeed, there is a simple trick that allows you to add extra information at a certain position: just replace a letter adjacent to the position and mark it with the information, and the original letter.
In your example, have a nonterminal $M$ for the middle, but as it can not be deleted, it also counts as a normal letter. Thus we have two copies $M_a$ and $M_b$ to indicate the letters replaced.
In the end of the derivation the markers should be replaced by their letter content, by simple productions like $M_a\to a$.
In most cases the application of $M_a\to a$ needs to be performed at the end of the derivation process. In some constructions this does not need to be "timed": when the $M$ disappears too soon, the derivation cannot find a proper position and the process will not stop successfully. In other cases one does need a kind of control. This is sometimes done by introducing a nonterminal as a signal that moves along the letters. Again, this signal should also carry a terminal otherwise you end up in the same problems.
Moving information around is easy in so-called monotonic grammars ($\alpha\to \beta$ with $|\alpha|\le\beta|$) using rules like $XA \to AX$, which can be seen as $X$ jumping over $A$. For proper context-sensitive grammars one needs to split this in three steps: $XA \to XA^X, XA^X\to AA^X, AA^X\to AX$. in each production one letter is changed in a proper context. It takes quite some imagination to see this process does not interact with other parts of the derivation. E.g., what happens when the $A$ in the last step is first involved in another derivation step?
This might not work for very short words, when there is more information than positions available. The most simple solution to that is to ignore short strings in your construction, and generate them separately.
In your example, have a nonterminal $M$ for the middle, but as it can not be deleted, it also counts as a normal letter. Thus we have two copies $M_a$ and $M_b$ to indicate the letters replaced.
In the end of the derivation the markers should be replaced by their letter content, by simple productions like $M_a\to a$.
In most cases the application of $M_a\to a$ needs to be performed at the end of the derivation process. In some constructions this does not need to be "timed": when the $M$ disappears too soon, the derivation cannot find a proper position and the process will not stop successfully. In other cases one does need a kind of control. This is sometimes done by introducing a nonterminal as a signal that moves along the letters. Again, this signal should also carry a terminal otherwise you end up in the same problems.
Moving information around is easy in so-called monotonic grammars ($\alpha\to \beta$ with $|\alpha|\le\beta|$) using rules like $XA \to AX$, which can be seen as $X$ jumping over $A$. For proper context-sensitive grammars one needs to split this in three steps: $XA \to XA^X, XA^X\to AA^X, AA^X\to AX$. in each production one letter is changed in a proper context. It takes quite some imagination to see this process does not interact with other parts of the derivation. E.g., what happens when the $A$ in the last step is first involved in another derivation step?
This might not work for very short words, when there is more information than positions available. The most simple solution to that is to ignore short strings in your construction, and generate them separately.
Context
StackExchange Computer Science Q#13327, answer score: 6
Revisions (0)
No revisions yet.