Is my context free grammar here correct?

Question

So in preparation for an interview, I have been revising and studying by solving some CFGs, and here is a question, which I solved, but I feel like I haven't solved it right, given its boundary requirements.

Give a CFG for the set of all strings in the form $O^i 1^j 2^k 3^l$ where $0 \leq j \leq 2i$ and $k=l$.

My approach: When $j=2$, $i=2$, and $k=3$ I started solving this (do share some of your tips and hints in solving CFGs, it would help me alot and I would appreciate your expertise tips) I produced a string

$$011222333$$

And given that, after analyzing it, I came up with this grammar

$$S \to OA$$ $$A \to 1A1B|\epsilon$$ $$B \to 2BC|\epsilon$$ $$C \to 3c|\epsilon$$

I was able to produce that string from the above grammar, but I feel like I was intentionally selecting and choosing when to choose epsilon, almost forcing my grammar to work, it felt weird.

Your assistance, plus tips will greatly help!

Answer 1

First, split your language in two, that is, $L_1 = \{\mathtt{0}^i\mathtt{1}^j \mid 0 \leq j \leq 2i\}$ and $L_2 = \{\mathtt{2}^k\mathtt{3}^k \mid k \in \mathbb{N}\}$,

$$S \to L_1L_2.$$

Now, $L_2$ is simply

$$L_2 \to \mathtt{2}\,L_2\mathtt{3} \mid \varepsilon$$

while the first one can be done using this simple trick:

\begin{align} L_1 &\to \mathtt{0}\,L_1JJ \mid \varepsilon \\ J &\to \mathtt{1} \mid \varepsilon \end{align}

I hope this helps ;-)

Answer 2

Your grammar does not construct the language intended. $\newcommand{\Ze}{\mathtt{0}} \newcommand{\On}{\mathtt{1}} \newcommand{\Tw}{\mathtt{2}} \newcommand{\Th}{\mathtt{3}}$ For example, it can construct the following string: $$\begin{align} \color{red}{S} &\Rightarrow \color{blue}{ \Ze A } = \Ze \color{red}{A} \\ &\Rightarrow \Ze \color{blue}{ \On A \On B } = \Ze \On \color{red}{A} \On B \\ &\Rightarrow \Ze \On \color{blue}{ \On A \On B } \On B = \Ze \On \On \color{red}{A} \On B \On B \\ &\Rightarrow \Ze \On \On \color{blue}{\varepsilon} \On B \On B = \Ze \On \On \On \color{red}{B} \On B \\ &\Rightarrow \Ze \On \On \On \color{blue}{ \Tw B C } \On B = \Ze \On \On \On \Tw \color{red}{B} C \On B \\ &\Rightarrow \Ze \On \On \On \Tw \color{blue}{\varepsilon} C \On B = \Ze \On \On \On \Tw \color{red}{C} \On B \\ &\Rightarrow \Ze \On \On \On \Tw \color{blue}{\varepsilon} \On B = \Ze \On \On \On \Tw \On \color{red}{B} \\ &\Rightarrow \Ze \On \On \On \Tw \On \color{blue}{\varepsilon} = \Ze \On \On \On \Tw \On \end{align}$$ which is not in the desired language.

In fact, you can easily show that every string your grammar constructs has only one $\Ze$. Working a bit more, you can show that the language your CFG constructs is (abusing notation somewhat) $$ \{ \Ze \On^n ( \On \Tw^* \Th^* )^n : n \geq 0 \}.$$

(dtldarek's answer provides a CFG for the grammar in question.)