Find a CFG for $\{a^n b^m c^k \mid m=n+k\}$

Question

I am trying to build the CFG to $\{a^n b^m c^k \mid m=n+k\}$ but does not working.

I tried $S \to aSc$, $S \to S_1$, $S \to \epsilon$, $S_1 \to bS_1c$, $S_1 \to \epsilon$ but it does not work.

I guess that I done S → aSc S → S1 S → e S1 → bS1c S1 → e @DonThousand — Vagner Wentz, May 16 '21 at 22:36
You don't want $S\to aSc$ This increases the number of $a$'s and $c$'s and leaves the number of $b$'s fixed. Every time you add an $a$ or a $c$ you must add a $b$ and vice versa. — saulspatz, May 16 '21 at 22:44

score 2 · Accepted Answer · answered May 17 '21 at 04:05

2

Observe that your language can be written as the product of two context-free languages $$ \{a^nb^{n+k}c^k \mid n, k \geqslant 0 \} = \{a^nb^n \mid n \geqslant 0\}\{b^kc^k \mid k \geqslant 0\} $$ which naturally leads to the grammar \begin{align} S &\to S_0S_1 \\ S_0 &\to aS_0b + 1 \\ S_1 &\to bS_1c + 1 \end{align}

answered May 17 '21 at 04:05

J.-E. Pin

40,163

The $+1$ seems like an odd notation. Don’t you mean $\mid \epsilon$ or something similar? – Erick Wong May 17 '21 at 04:27
@Erick_Wong This is just the algebraic notation, which seems appropriate for a Math site. $1$ denotes the identity of the free monoid, that is the empty word. The $+$ notation is natural when you associate an equation to the grammar. For instance, the language ${a^nb^n \mid n \geqslant 0}$ is the least solution of the equation $S = aSb + 1$. – J.-E. Pin May 17 '21 at 06:04
1

Interesting, thanks for the explanation (I hadn't seen Chomsky's paper on CFG algebras before). It still seems like a mixed metaphor to use the algebraic notation on the RHS in conjunction with the production rule arrow rather than a more conventional equals sign. – Erick Wong May 17 '21 at 06:52

Find a CFG for $\{a^n b^m c^k \mid m=n+k\}$

1 Answers1