1
$\begingroup$

Give a CFG for the languague L = $ \{ 1^n +1^m = 1^{n+m}| n,m \in N_{0}\} $ , with the alphabet $\Sigma =\{1,+,=\}$.

I am currently trying to solve the given task, I thought a good way is to split the Languague into two more simple languagues, but I am keep failing. May some can help

$\endgroup$
2
$\begingroup$

The idea is to start generating the ones of the first addend from the axiom $S$, while simultaneously adding the corresponding number of ones at the end of the sentential form. Then you have a production from $S$ to non-terminal $A$ which takes care of generating the second added, while still appending ones at the end of the sentential form.

When you are done generating the second addend you can replace $A$ with $=$ in order to split all the ones from the two addends (on the left side) from the corresponding number of ones on the right size.

$$ \begin{align*} S &\to 1S1 \mid +A \\ A &\to 1A1 \mid \,= \end{align*} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hello Steven, thx for your answer. But you did not consider that n/m can be 0. $\endgroup$ – Frank May 23 at 12:37
  • $\begingroup$ Why not? Here is an example where $n=0$: $S \to +A \to +1A1 \to +1=1$. Here is an example where $m=0$: $S \to 1S1 \to 1+A1 \to 1+=1$. Here is an example where $n=m=0$: $S \to +A \to +=$. $\endgroup$ – Steven May 23 at 12:40
  • $\begingroup$ Ohh, you are right. My fault, thank you very much. $\endgroup$ – Frank May 23 at 12:42
  • $\begingroup$ Since I am not able to upvote/declare this answer as correct, I will write it here : The answer from Steven is completly correct. $\endgroup$ – Frank May 23 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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