Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I can't create formal grammar for the language like

$wcw$ where $w$ is the word in $\{a,b\}^\ast$ and $c$ is just a letter

Thanks!

share|improve this question
    
I see this is your first post, so just to be sure: Is this a homework? If yes, you should tag it with homework and you should read this. –  Martin Sleziak Jan 6 '12 at 10:16
    
Michael: In case the hint in my post was not sufficient to help you solve this, feel free to ping me; so that we can discuss this further. –  Martin Sleziak Jan 8 '12 at 8:30

1 Answer 1

Hint (but I did not check all details, so I apologize if I've overseen some problem there):

Would you be able to make a grammar in which this would be a derivation?

$S \Rightarrow^* ABBS \Rightarrow^* A_1B_1B_1S_1A_3B_3B_3 \Rightarrow^* abbcabb$

Of course, $S$, $A$, $B$, $A_1$, $B_1$, $A_2$, $B_2$, $A_3$, $B_3$ are non-terminals, $a$, $b$ are terminals.

EDIT: I've added two more non-terminals. (In the approach I have in mind I will need them to distinguish whether the letter has already "moved" to the right half.)


I've tried too google a little, mainly for the reason that I did not want put energy into writing up a solution if it was already given elsewhere.

Searching for "formal language" grammar "wcw" and similar phrases led me to this paper. Some grammar for this language is given there. But it is not the type of grammar you're looking for - it's a Boolean grammar. But since the author mentions that this is one of the standard examples of non-context-free constructs, this suggest that this should probably not be too difficult and this example could occur in some standard textbooks.

The fact that it is not context-free should be provable using pumping lemma; a complete proof of this fact is given in Johan Jeuring, Doaitse Swierstra: Grammars and Parsing, which is basically a collection of solved exercises (with solutions).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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