Context free grammar question

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\}$$

Answer 1

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?

Answer 2

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

Answer 3

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.