Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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..
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.
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.
