1
$\begingroup$

I have found an exercise where it tasks to provide a grammar and a pushdown automata for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

While finding a pushdown automata for it is quite easy (four states and two stack symbols $p$ and $t$, where $0^x$'s push $p$, $1^t$'s and $0^z$'s pop $p$ or push $t$ if there are no $p$'s, and $1^w$'s pop $t$), I am unable to find an equivalent grammar for it. Perhaps there is some trick for this?

$\endgroup$
2
$\begingroup$

Let's write the condition $x+w=y+z$ in a different way: $x-y=z-w$. We consider two cases: $x \geq y$ and $y \geq x$. If $x \geq y$, let $x = y+a$. Then we are interested in words of the form $$ 0^{y+a} 1^y 0^{w+a} 1^w = 0^a 0^y 1^y 0^a 0^w 1^w. $$ If $y \geq x$, let $y=x+b$. Then we are interested in words of the form $$ 0^x 1^{x+b} 0^z 1^{z+b} = 0^x 1^x 1^b 0^z 1^z 1^b. $$ We can generate words of the first form using the grammar \begin{align} &T_1 \to AW \\ &A \to 0A0 \mid Y \\ &Y \to 0Y1 \mid \epsilon \\ &W \to 0W1 \mid \epsilon \end{align} We can generate words of the second form using the grammar \begin{align} &T_2 \to XB \\ &X \to 0X1 \mid \epsilon \\ &B \to 1B1 \mid Z \\ &Z \to 0Z1 \mid \epsilon \end{align} Taking these two grammars together and adding a new rule $S \to T_1 \mid T_2$, we get a grammar for your language. Note that you can merge $X,Y,Z,W$. The resulting grammar is \begin{align} &S \to AX \mid XB \\ &A \to 0A0 \mid X \\ &B \to 1B1 \mid X \\ &X \to 0X1 \mid \epsilon \end{align}

$\endgroup$
1
$\begingroup$

I don't know if $x$, $y$, etc. can be $0$, so maybe there's something to fix (e.g., you'll need $S\rightarrow \varepsilon$ etc.), but you can try something like this:

$S\rightarrow 0S1 \mid 0A0 \mid 1B1 $
$A \rightarrow 0A0 \mid 1C0$
$B \rightarrow 1B1 \mid 1C0$
$C \rightarrow 1C0 \mid \varepsilon$

Suppose $w\geq x$, then the idea is first generating the string $0^x S' 1^x$, then adding $w-x$ $1$'s on the right of the first $0$'s and the same number of $0$'s on the left of the last $1$'s, and so on; the case $x\geq w$ is similar.

$\endgroup$
0

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.