0
$\begingroup$

i need to convert this CFL to CFG

$$ L = \{\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\;\} $$

I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm gonna blow my mind..If somebody can help i will be so grateful..

$\endgroup$
1
  • 1
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$
    – Nathaniel
    Dec 23, 2021 at 20:24

1 Answer 1

2
$\begingroup$

We want to generate strings of the form $1^n 0^m 1^k 0^p$ with the same number of $0$ and $1$. This language can be generated by distinguishing two cases.

The first approach is to draw a diagram what happens if we keep counting the difference between the numbers of $0$ and $1$. This difference between the cases is whether the count drops below zero or not.

The two examples correspond to $1^5 0^3 1^2 0^4 = 1^2\; (1^3 0^3) \; (1^2 0^2) \; 0^2$ and $1^2 0^4 1^5 0^3 = (1^2 0^2) (0^2 1^2) (1^3 0^3) $.

The structure of the diagram indicates which pairs of $0$ and $1$ can be generated together by the CFG.

enter image description here

Observe that such a diagram more or less represents how a push-down automaton would keep track of the string.

Alternatively we can do the math.

Let us assume here that $m \ge n$. This means there is a number $t$ such that $m = n+t$. Since we want to have $n+k = m+p = n+t+p$ we also need $k= t+p$.

Thus this string is of the form $1^n\, 0^m\, 1^k\, 0^p = 1^n\, 0^{n+t}\, 1^{t+p}\, 0^p = 1^n 0^n\; 0^t 1^t\; 1^p 0^p $.

Strings of this form are easy to generate by a CFG. In constructing that CFG include the requirement that $n\ge 2$, and $k,m,p \ge 1$.

The case $m\le n$ is handled analogously. The two parts of the grammar can be joined in the standard way, using the construction for union of context-free languages. See the reference question.

$\endgroup$
3
  • $\begingroup$ i got it thanks sir u really helped so much i was trying the same thing with letter k but i couldn't do it right thanks again $\endgroup$ Dec 23, 2021 at 20:32
  • $\begingroup$ i generated cfg both m≥n and m≤n cases now what should i do for the final answer combining the two cfgs ? can u help me just one more time plz $\endgroup$ Dec 23, 2021 at 21:21
  • $\begingroup$ i got it sir thank you so much you helped a lot $\endgroup$ Dec 24, 2021 at 3:33

Your Answer

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

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