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.

$\endgroup$
5
  • $\begingroup$ Exercise 6.2.a, due May 31st. $\endgroup$
    – Raphael
    May 30, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 20:38

2 Answers 2

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 | -
$\endgroup$
5
  • $\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, 2012 at 15:39
  • $\begingroup$ @user1594 Edited to clarify. One grammar, two nonterminals. $\endgroup$
    – Patrick87
    May 28, 2012 at 15:48
  • $\begingroup$ i've understand it but can we also prove it except by trying? $\endgroup$
    – user1594
    May 28, 2012 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, 2012 at 16:41
  • $\begingroup$ How would see the induction i can't imagine it. Thanks $\endgroup$
    – user1594
    May 29, 2012 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$.

$\endgroup$
1
  • 1
    $\begingroup$ Why the downvote? $\endgroup$
    – Raphael
    May 28, 2012 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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