# Context free grammar question

i have two context free grammar questions and I don't know how to do them.

1. $$\{(a^n)b(c^n) \mid n >0 \}$$ I'm having trouble with this one because I don't know how to account for $a$ or $b$ not having empty set.

2. $$\{(a^n)(b^m)(c^n) \mid n,m \ge 0\}$$

• Do you want to create a context-free grammar for each language given? – Michael Chen Dec 2 '13 at 20:54
• yes. Like S--> A , A ---> aAc | b....something like that – Abdul Dec 2 '13 at 20:56
• for the first one I have S -> A, A -> aAc | b, but it doesn't account for a or c being greater than 0. 2nd problem I have S -> A, A -> aBc|^|B, B -> bB|^ but i just realized how wrong it is. – Abdul Dec 2 '13 at 20:58
• Put what you've tried in your question. The community likes questions where some work has been attempted. – Michael Chen Dec 2 '13 at 20:59

## 3 Answers

HINT: I’m assuming that the problem is to create context-free grammars that generate these languages. You need basically the same idea for both, so I’ll just deal with the first one. The idea is to use a non-terminal symbol to pump out $a$’s on the left and $c$’s on the right, one at a time; a production like $S\to aSc$ does this. At some point you then let $S\to b$, and you’re left with $a^nbc^n$ for some $n\ge 0$. Of course you want to rule out $n=0$, so instead of collapsing $S$ to $b$ at the end, you collapse it to ... what?

• I didn't realize my question wasn't specific enough. Thank you. – Abdul Dec 2 '13 at 21:09
• @Abdul: You’re welcome. – Brian M. Scott Dec 2 '13 at 21:09
• Also, thank for the revision of the question. I appreciate it. – Abdul Dec 2 '13 at 21:18

You are close for the first:

$$S\to aAc,\qquad A\to S \mid b$$

and for the second $$S\to aSc \mid A\qquad A\to bA\mid\epsilon$$ should work

• Thank you very much. I never thought of letting A go back to S. – Abdul Dec 2 '13 at 21:05

In general, strings of the form $a^nb^n$ for $n > 0$ are derived from productions of the form $A \rightarrow aAb$. So a context-free grammar generating the language $a^nb^n$ for $n \geq 0$ will have produtions $A \rightarrow \lambda$ and $A \rightarrow aAb$. The second production will generate the leading and trailing $a$'s and $b$'s, while the $\lambda$-production will terminate a derivation. If the $\lambda$-rule is replaced with another rule, say $A \rightarrow u$, then the language generated by the grammar will be $a^nub^n$, because every derivation in the grammar will terminate with $A \rightarrow u$. Given that $A \rightarrow aAb$ generates $a^nAb^n$ for $n \geq 0$, you need to find an appropriate $u$ that will terminate derivations in the grammar to generate $a^nb^n$ for $n > 0$.

For the second language, again begin with the fact that $A \rightarrow aAc$ has partial derivations of the form $a^nAc^n$ for $n \geq 0$. Instead of terminating derivations with a single application of a rule $A \rightarrow u$ for some string $u$, we want to terminate derivations with a rule that allows the derivation of a finite number of $b$'s. In other words, we want a rule that derives $B \Rightarrow^* b^m$ for $m \geq 0$. You should know how to write such a rule, because you're presumably covered right and left-regular grammars.