2
$\begingroup$

I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt:

Question: $L = \{a^n b^m c^p \mid n = m + p + 2\}$

My Attempt: 

S -> aaBC

B -> aBb | ^

C -> ?  (Now how can i increase length of `a` Terminal by C as i increased from B)

Is this language not context free / impossible ?

$\endgroup$
2
  • $\begingroup$ Welcome to SE Computer Science. WHat do you call an "impossible" language? Why do you use the tag automata when there is no automata issue in your question? $\endgroup$
    – babou
    Jun 28, 2015 at 7:25
  • 1
    $\begingroup$ You may be interested in our reference questions. $\endgroup$
    – Raphael
    Jun 28, 2015 at 9:48

2 Answers 2

5
$\begingroup$

You'll need to "wrap" the Bs in the Cs:

S -> aaC
C -> aCc | B
B -> aBb | ɛ

With that, we have

$L(B) = a^m b^m$,

$L(C) = a^p \cdot L(B) \cdot c^p = a^p a^m b^m c^p$ and

$L(S) = a^2 \cdot L(C) = a^2 a^p a^m b^m c^p = a^{m+p+2} b^m c^p$.

$\endgroup$
0
2
$\begingroup$

As noted by Raphael in one of the comments an appraoch to this question is given in one of the reference questions: "How to prove that a language is context-free?".

Try to write the language in such a way that the nesting structure can be handled by a CFG.

$L=\{a^nb^mc^p\mid n=m+p+2 \} = \{a^{m+p+2}b^mc^p\mid m,p\ge 0 \}$

This does not work, so reorder:

$L=\{a^{p+m+2}b^mc^p\mid m,p\ge 0 \} = \{a^pa^ma^2 b^mc^p\mid m,p\ge 0 \} $.

Then apply nesting, peeling the layers of the string like an onion.

$S\to aSc$, $S\to T$, $T\to aTb$, $T\to a^2$.

$\endgroup$
1
  • $\begingroup$ this method cannot be used when i have condition like n = m + p - 2 $\endgroup$ Jun 29, 2015 at 7:40

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.