1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you want to create a context-free grammar for each language given? $\endgroup$ – Michael Chen Dec 2 '13 at 20:54
  • $\begingroup$ yes. Like S--> A , A ---> aAc | b....something like that $\endgroup$ – Abdul Dec 2 '13 at 20:56
  • $\begingroup$ 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. $\endgroup$ – Abdul Dec 2 '13 at 20:58
  • $\begingroup$ Put what you've tried in your question. The community likes questions where some work has been attempted. $\endgroup$ – Michael Chen Dec 2 '13 at 20:59
5
$\begingroup$

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?

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

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

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

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.

$\endgroup$

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.