1
$\begingroup$

We know that $L = \{ xy | x, y \in (0 + 1)^*, |x| = |y|, x≠y\}$

is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by checking one $0$ against three $1s$ but how can we check $x ≠ y?$

$\endgroup$
6
  • 2
    $\begingroup$ This looks like a duplicate of cs.stackexchange.com/q/307/755. In particular, see the answer there, and convert that context-free grammar to a PDA. $\endgroup$
    – D.W.
    May 9, 2022 at 3:28
  • $\begingroup$ @D.W. your linked answer I already seen, and that based on cfg, but I want to design pda and want to check $x=!y$. $\endgroup$
    – S. M.
    May 9, 2022 at 3:31
  • 2
    $\begingroup$ You said, you already know that the language is context-free, but you are still seeking for a PDA for it. Does it mean you have a CFG for the language? If so, there is a general way of converting a CFG to a PDA. You can easily search for it. But here is a link you can check. $\endgroup$
    – Russel
    May 9, 2022 at 3:31
  • 2
    $\begingroup$ Does this answer your question? PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it $\endgroup$ May 9, 2022 at 9:13
  • 2
    $\begingroup$ Also Raphael explained how to build how to build a PDA for the same language: Pushdown Automaton for L={w1w2:|w1|=|w2|,w1≠w2} $\endgroup$ May 9, 2022 at 9:24

2 Answers 2

9
$\begingroup$

If two strings $w_1, w_2$ of the same length are different from each other, then you can find a specific position where they differ:

$$w_1 = \underbrace{\square\ldots \square}_{k\text{ symbols }}\;x\;\underbrace{\square\ldots\ldots \square}_{\ell\text{ symbols }}$$

$$w_2 = \underbrace{\square\ldots \square}_{k\text{ symbols }}\;y\;\underbrace{\square\ldots\ldots \square}_{\ell\text{ symbols }}$$

$$x\neq y$$

You may already know the trick that when you concatenate the two strings, you can re-subdivide them:

$$w_1w_2 = \underbrace{\square\ldots \square}_{k\text{ symbols }}\;x\;\underbrace{\square\ldots\ldots \square}_{\ell\text{ symbols }}\;|\;\underbrace{\square\ldots \square}_{k\text{ symbols }}\;y\;\underbrace{\square\ldots\ldots \square}_{\ell\text{ symbols }}$$

$$w_1w_2 = \underbrace{\square\ldots \square}_{k\text{ symbols }}\;x\;\underbrace{\square\ldots\square}_{k\text{ symbols }}\;|\;\underbrace{\square\ldots\ldots \square}_{\ell\text{ symbols }}\;y\;\underbrace{\square\ldots\ldots \square}_{\ell\text{ symbols }}$$

You can do this because the $\square$ symbols can be anything. When you divide them this way, you can more easily see how a context free grammar can recognize the language.


Based on this trick, here is a definition of a PDA to recognize the language.
  1. The PDA has four states, $P$, $Q_0$, $Q_1$, and $R$. The initial state is $P$.

  2. When in state $P$, the machine will nondeterministically guess the position $k$ where the two strings differ.

    Specifically, in state $P$ the machine may read a character from the input (ignoring it), and push the symbol $A$ onto the stack. It may do this as many times as it likes.

  3. When in state $P$, the machine may decide that it will inspect the character in the current position. It reads the character at the current input (what I called $x$ above). If it reads $x=0$, the machine transitions to state $Q_0$. If it reads $x=1$, the machine transitions to state $Q_1$ instead.

    In this way, the machine uses its finite state to remember the value of $x$ for later.

  4. When in state $Q_0$ or $Q_1$, the machine first consumes $k$ characters of input. Specifically, it pops the symbol $A$ from the stack and consumes one character of input (ignoring it) until the stack is empty. (If it runs out of characters, the computation fails because the value of $k$ was invalid.)

  5. Next, while in state $Q_i$, the machine nondeterministically guesses the value of $\ell$. As before, it does this by consuming one character of input (ignoring it) and pushing $B$ onto the stack. It may repeat this process any number of times.

  6. When in state $Q_i$, the machine may decide that it will inspect the character in the current position. It reads the character at the current input (what I called $y$ above).

    If it is in state $Q_0$ and reads $y=1$, we've found a mismatch! If it is in state $Q_1$ and reads $y=0$, we've found a mismatch!

    Otherwise, there is no mismatch at the chosen position. The machine should fail.

  7. If the machine finds a mismatch, let it transition to state $R$. In state $R$, it should remove all the $B$ symbols from the stack, consuming one character from the input for each one. At the end of this process, it should be exactly at the end of the string and the stack should be empty. (If not, it has picked invalid values for $k$ and $\ell$.)

  8. Overall, if $w_1$ and $w_2$ are different strings of the same length, one of the nondeterministic guesses of this machine will succeed, so the overall PDA will accept. Otherwise, all of the branches will fail, and the PDA will reject. This is the desired behavior.

$\endgroup$
6
  • 1
    $\begingroup$ Clear explanation and illustration! $\endgroup$
    – John L.
    May 9, 2022 at 5:25
  • $\begingroup$ @user326210 could write the transition function, then it will be better for me? $\endgroup$
    – S. M.
    May 9, 2022 at 15:12
  • $\begingroup$ @user326210 see this, if I did mistake, please correct me. I am unable to reach final state. $\endgroup$
    – S. M.
    May 9, 2022 at 17:39
  • $\begingroup$ @Xavier's Looks good to me! I notice one error---remember it's okay if $k=0$ and/or $\ell=0$, so your transitions between states should also allow the empty stack $Z_0$, not just $A$ or $B$. For example, simulate your machine on the string "01". $\endgroup$
    – user326210
    May 9, 2022 at 20:33
  • $\begingroup$ @user326210 check my diagram, if I did any mistake. $\endgroup$
    – S. M.
    May 10, 2022 at 1:05
0
$\begingroup$

I understand the @user326210 algorithm and on basis of my understanding I design the below NPDA.

enter image description here

$\endgroup$

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.