-1
$\begingroup$

As I've already asked my Question about the solving Context Free Grammar $L = \{a^n b^m c^p \mid n = m + p + 2\}$

Can this language be defined by a Context Free Grammar?

Now i have just changed n = m + p - 2 and still can't figure out, Here is my attempt:

S -> Cc
B -> aBb | ^
C -> aCc | Bb

(In this Grammer i can't handle string like bb , cc , abbc , abcc etc)

How to make such type of grammars where n = m + p - x .Can anyone explain how to solve such kind of grammars:

$K = \{a^n b^m c^p \mid n = m + p - 2\}$

$\endgroup$
5
  • 2
    $\begingroup$ We have to switch between 2 pages to read the language definition..Don't be lazy, rewrite it here please. $\endgroup$
    – François
    Jul 1, 2015 at 6:13
  • 3
    $\begingroup$ 1. Please make your question self-contained. People should be able to understand your question by reading just this post here; they shouldn't have to click on a link to read necessary information. 2. We want to help you learn concepts, but we're not here to solve your exercise for you. We frown on "problem dumps". Please try to either ask a more general question that's more likely to be useful to others in the future and is not so specific to this one specific exercise; or show what you've tried and try to identify a narrower, more focused question about some specific aspect of your approach. $\endgroup$
    – D.W.
    Jul 1, 2015 at 6:58
  • $\begingroup$ possible duplicate of Converting to CFG from a CFL? $\endgroup$
    – D.W.
    Jul 1, 2015 at 7:00
  • $\begingroup$ possible duplicate of How to prove that a language is context-free? $\endgroup$ Jul 1, 2015 at 7:21
  • $\begingroup$ @FrançoisGodi and D.W thanks you very much for answering my question and appreciation , well if I've just copied from that question, it may be considered copy according to stackexchange rules. $\endgroup$ Jul 1, 2015 at 14:52

1 Answer 1

1
$\begingroup$

$K = \{a^n b^m c^p \mid n = m + p - 2\}$. This can be solved by observing the nesting structure (see "How to prove that a language is context-free?") and an extra trick.

Thus we have words of the form $a^{p'+m'} b^{m'}b^i c^j c^{p'}$, where $i+j=2$. We have set aside the two symbols that are not counted for $n$.

Apply nesting $S\to aSc$, $S\to Tb^i c^j$ (all 3 possibilities $i+j=2$), $T\to aTb$, $T \to \varepsilon$.

$\endgroup$
0

Your Answer

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

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