3
$\begingroup$

I've got a problem with this task. I should declare a context-free grammar for this language:

$\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$

My idea is: We need a start symbol, for example $S$. I know that I can generate the first $a$ and the last $a$ by $S \to a a$. I don't know what is the next idea to solve this task.

Improve this question
$\endgroup$
  • $\begingroup$ Exercise 6.2.a, due May 31st. $\endgroup$ – Raphael♦ May 30 '12 at 8:01
  • $\begingroup$ @Raphael What's the point of the above comment? If it's not constructive, please delete it (and this too). $\endgroup$ – Patrick87 May 30 '12 at 14:17
  • 1
    $\begingroup$ @Patrick87: It serves to document a) the sources of the questions user1594/1671 has been posting and b) that they have dumping their homework. People might want to hold back on full answers until after the due date. $\endgroup$ – Raphael♦ May 30 '12 at 14:40
  • $\begingroup$ @Raphael This question seems too generic to require a reference; anybody could come up with such a question, so attribution isn't necessary. Regarding the date... alright, you can remove it after May 31, if you remember. $\endgroup$ – Patrick87 May 30 '12 at 16:24
  • $\begingroup$ @Patrick87: I hope my meta answer here explains my reasons for the comment sufficiently. Please remove all but the first comment if you agree. $\endgroup$ – Raphael♦ May 30 '12 at 20:38
9
$\begingroup$

First, rewrite $a^nb^ma^{n+m}$ as $a^nb^ma^ma^n$. Now, from the outside in, you need rules to (1) add an $a$ to the front and back of your strings, and (2) to add $b$ to the front and $a$ to the back. It's also helpful to imagine building strings from the inside out... you can either add a $b$ to the front and an $a$ to the back, or an $a$ to both ends.

The first, working from the outside, rule is straightforward: 

S := aSa

Notice that once you start adding $b$, you cannot go back to adding only $a$... so we need a new nonterminal:

S := B
B := bBa

Since the empty string is in your language, add another production to allow $B$ to generate the empty string. So we get:

S := aSa | B
B := bBa | -
Improve this answer
$\endgroup$
  • $\begingroup$ i've got a question you notice three times S. Do you mean that we've got only two nonterminal S and A or three with B too? $\endgroup$ – user1594 May 28 '12 at 15:39
  • $\begingroup$ @user1594 Edited to clarify. One grammar, two nonterminals. $\endgroup$ – Patrick87 May 28 '12 at 15:48
  • $\begingroup$ i've understand it but can we also prove it except by trying? $\endgroup$ – user1594 May 28 '12 at 16:28
  • $\begingroup$ @user1594: Of course. For one direction you will have to do induction over the number of derivation steps (or structural induction) and for the other direction nested induction over $n$ and $m$ (some tricks are possible). $\endgroup$ – Raphael♦ May 28 '12 at 16:41
  • $\begingroup$ How would see the induction i can't imagine it. Thanks $\endgroup$ – user1594 May 29 '12 at 23:12
3
$\begingroup$

Hint: Develop grammars for the simple languages $\{a^nb^n \mid n \in \mathbb{N}\}$ and $\{a^nb^m \mid m,n \in \mathbb{N}\}$, respectively, and combine (variations of) them to generate your $L$.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Why the downvote? $\endgroup$ – Raphael♦ May 28 '12 at 12:15

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.