CF grammar for a Language.

Question

I am trying to formulate a CF grammar for a language of alphabet { a , b, c} with a condition that the number of characters a standing anywhere in the word before this given c larger by 3 than the double of the number of characters b standing anywhere in the word after the given c. for example aababcaacaaacb is in L (the second c is OK), babaabca ∈ L, as well, however aabcabaacbbab , aac and ε are not elements of L. This was a question that i found in a pdf when practicing but could not get to a solution.

Answer 1

If I understand correctly, the language consists of words which contain a 'c' for which the number $n_1$ of 'a's before this 'c' and the number $n_2$ of 'b's after this 'c' satisfy

$n_1 = 2n_2+3$.

Okay so we want to do two things:

1. Handle the case where you have three a's (and an arbitrary number of b's and c's) before a 'c', followed by a string containing no b's
2. Handle adding two a's to the front and a b to the back.

For the first, we can do

$X = [bc]^*a[bc]^*a[bc]^*a[bc]^*c[ac]^*$

For the second,

$Y = [bc]^*a[bc]^*a[bc]^*X[ac]^*b[ac]^*$

assuming I didn't make any mistakes, anyway.

Answer 2

The following context-free grammar appears to generate $L$:

$$\begin{align*} S&\to AASB\mid AAAc\\ A&\to bA\mid cA\mid Ab\mid Ac\mid a\\ B&\to aB\mid cB\mid Ba\mid Bc\mid b \end{align*}$$

$A$ and $B$ generate the regular languages corresponding to the regular expressions $(b+c)^*a(b+c)^*$ and $(a+c)^*b(a+c)^*$, respectively. Any derivation is going to begin

$$S\Rightarrow^n A^{2n}SB^n\Rightarrow A^{2n+3}cB^n\;;$$

each $A$ will generate a single $a$, possibly surrounded by a ‘halo’ of $b$s and $c$s, and each $B$ will generate a single $b$, possibly surrounded by a ‘halo’ of $a$s and $c$s.