# Context-free grammar for $\{1^i0^j1^k \mid i+2j=k\}$

Suppose $$L=\{1^i0^j1^k\mid i+2j=k\}$$

How can I construct a context-free grammar for $$L$$?

This is homework. Here is my attempt for the case when $$L$$ is defined with $$i+2j=3k$$ instead.

\begin{align*} S&\to aaaSc| bbbBcc| abBc| aabBc|\lambda\\ B&\to bbbBcc| \lambda \end{align*}

But it's not true because it accepts the string $$s=a^2b^4c^3 \notin L$$. How can I correct the above grammar?

• The straightforward idea is to think in terms of PDA and then extract the LL-grammar from it. What is to be collected in the stack? How to represent these stack elements as nonterminals (a hint: they have constant derivations). Mar 21 at 6:56
• You should always ask the question you want to ask. If you ask a different question and someone answers it, and you then change the question, you make the answer look ridiculous. That's not a nice way to treat people who are trying to help you. Putting "edited" in the question doesn't help. (Also, you use $\Sigma = \{0, 1\}$ in the start of the question and $\Sigma = \{a, b, c\}$ in your proposed solution; although it's possible to guess what you meant, it's not as clear as it could be.)
– rici
Mar 21 at 16:18
• Anyway, your second and fourth productions for $S$ are wrong. The fourth one doesn't preserve the condition (two $a$s and one $b$ cannot be balanced by any number of $c$s because $2 + 2*1$ is not a multiple of 3) and the second one is redundant with the first production for $B$.)
– rici
Mar 21 at 16:24
• Hmm, it looks like I might have added mess to confusion by my edit. Mar 22 at 0:48

The simplest solution to problems of this form is usually to just rearrange the terms.

We know that $$k = i + 2j$$, which is the same as $$2j + i$$. So the language's sentences are of the form $$1^i0^j1^{2j+i}$$. We can regroup that as $$1^i(0^j1^{2j})1^i$$. (Parentheses used only for grouping.)

You should be able to just read the grammar off of that.

• I edit my question:). 3k=i+2j.
– All
Mar 21 at 7:33
• @All Its problematic to change the question after it has been answered
– lox
Mar 21 at 7:50
• Can you give me some hint about this case that $3k=i+2j$?
– All
Mar 21 at 9:43
• Assume another condition: i and j are divisible by 3. So you start with S, replace S with 111 S 1 any number of times, then replace with T, then replace T with 000 T 11 any number of times, and remove the T. Then you handle the cases where you have I = j = 1 or I = 1 = 2 leftover. Mar 21 at 16:32