Context-free grammar (CFG)

Question

How do I generate a context free grammar for a language
$$\Sigma = \{0, 1\},\ L = \{1^i0^j1^k \mid i, j, k \geq 0\}$$
Thanks already

Answer 1

Denote our context free grammar by $G=(V, \Sigma, R, S)$ whereby $V=\{S,S_1, S_2, S_3\}$ is our set of variables, $S$ denotes the start variable and $\Sigma=\{0,1\}$ is our set of terminals. Then our rules $R$ are given by \begin{alignat}{1}S &\to 1S_1\\\ S_1 &\to 1S_1\ |\ S_2\ \\ S_2 &\to 0S_2\ |\ S_3\ \\ S_3 &\to 1S_3\ |\ \epsilon \end{alignat}

We can generate the following words:

• $101$
• $1\cdots 01$
• $101\cdots$
• $10\cdots 1$
• $10 \cdots 1 \cdots$
• $1 \cdots 0 \cdots 1$
• $1 \cdots 0 \cdots 1 \cdots$

EDIT

The above grammar is only valid for the given language for $i,j,k >0$ as @rici correctly pointed out in the comments.

Here is the set of rules for $i,j,k \geq 0$ for the grammar $G=(V, \Sigma, R, S)$ with $V=\{S,S_1,S_2, S_3\}$.

\begin{alignat}{1}S &\to S_1\ |\ S_2\\\ S_1 &\to 0S_1\ |\ S_3\ |\ \epsilon\ \\ S_2 &\to 1S_2\ |\ S_1\ |\ \epsilon \\ S_3 &\to 1S_3\ |\ \epsilon \end{alignat}

This can generate the following words:

• $\epsilon$ (if $i=j=k=0$)
• $1$
• $0$
• $1\cdots$
• $0\cdots$
• $0\cdots 1 \cdots$
• $1\cdots 0 \cdots$
• $1\cdots 0 \cdots 1 \cdots$

Note: with $\cdots$ I mean zero or more repitions.