1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$
    – Tonita
    Commented Mar 21, 2022 at 6:56
  • 2
    $\begingroup$ 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.) $\endgroup$
    – rici
    Commented Mar 21, 2022 at 16:18
  • $\begingroup$ 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$.) $\endgroup$
    – rici
    Commented Mar 21, 2022 at 16:24
  • $\begingroup$ Hmm, it looks like I might have added mess to confusion by my edit. $\endgroup$
    – John L.
    Commented Mar 22, 2022 at 0:48

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I edit my question:). 3k=i+2j. $\endgroup$
    – All
    Commented Mar 21, 2022 at 7:33
  • 2
    $\begingroup$ @All Its problematic to change the question after it has been answered $\endgroup$
    – lox
    Commented Mar 21, 2022 at 7:50
  • $\begingroup$ Can you give me some hint about this case that $3k=i+2j$? $\endgroup$
    – All
    Commented Mar 21, 2022 at 9:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Mar 21, 2022 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.