3
$\begingroup$

I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$:

$$ \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*} $$

I know this is a grammar, but I need a PDA for this language, and intuition how $\{xy: |x|=|y|,x \neq y\}$ is a CFL while $\{xy: |x|=|y|,x=y\}$ is a CSL but not a CFL. How is this possible?

Improve this question
$\endgroup$
7
  • $\begingroup$ How do you derive $aaab$? Oh, damn my description was imprecise. I meant what if $x$ and $y$ have even length? Also, you can generate words of non-equal length using $A$ and $B$. $\endgroup$
    – ThreeFx
    Commented Dec 2, 2016 at 15:33
  • $\begingroup$ Regarding the distinction between your problem (which is a CFL) and the similar problem (which is a CSL): In your case you accept a word when you found a non-equal pair of characters. For a non-valid input the PDA will potentially loop forever. If you require the words to be equal, you have to check the condition for every possible pair $x_i$ and $y_i$ and remember if you have already checked $i$. Since a PDA cannot do this, it will have to loop forever on correct inputs and you cannot distinguish between a valid input looping and an invalid input looping. $\endgroup$
    – ThreeFx
    Commented Dec 2, 2016 at 16:09
  • 1
    $\begingroup$ Please ask only one question per post. For your first question, what have you tried? A construction for converting a grammar to a PDA is found in almost every textbook on automata theory; there is little reason for us to laboriously repeat it here. We expect you to do research on your own to try to answer your own question before asking here. $\endgroup$
    – D.W. ♦
    Commented Dec 2, 2016 at 16:54
  • $\begingroup$ Yeah i know the algorithm and there are many simulators too. . . But i just want the intuition like the language of equal number of a's and b's can be done by pushing a symbol for a's and popping symbol for b's. . so for this type of intuition i posted it here. And i will ask only one question per post $\endgroup$
    – Pavan Kumar Munnam
    Commented Dec 2, 2016 at 17:42
  • 1
    $\begingroup$ I second the point made by Yuval and D.W.: going from CFG to NPDA is an algorithmic task with well-established solutions. That does, however, not provide any insight. Here are two hints: 1) Check even length and $x \neq y$ separately. 2) Use non-determinism to "find" a position where $x$ and $y$ differ. $\endgroup$
    – Raphael
    Commented Dec 3, 2016 at 20:00

1 Answer 1

Reset to default
5
$\begingroup$

You are asking two questions: how to construct a PDA for the language, and why this language is context-free while the same language with the condition $x \neq y$ replaced by the condition $x = y$, is not. I will only answer the second, since for the first question there are known algorithms.

The reason that your language is context-free is that we can rewrite it as follows: $$ \{ \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j : i,j \neq 0 \} \cup \{ \Sigma^i b \Sigma^i \Sigma^j a \Sigma^j : i,j \neq 0 \}. $$ This gives a different description of the language as the union of concatenations of context-free languages. A similar trick just doesn't work for the language $\{ xy : x=y \}$.

Here is a different example. Consider the following two collections of natural numbers (without zero):

  • $A = \{ x \cdot y : x \neq y \}$.
  • $B = \{ x \cdot y : x = y \}$.

The set $A$ consists of all natural numbers other than $1$, whereas the set $B$ consists of all squares. Even though we defined them in a similar way, the set $A$ has a much simpler description, while $B$ doesn't.

Improve this answer
$\endgroup$
3
  • $\begingroup$ i was thinking like this , correct it if i am thinking wrong. I was assuming a deterministic machine with different states so for example of input size 3 there will be 3 different states where x(i) will be compared to y(i) for 0<i<4 so these three states cannot be simulated at the same instant, but all can be simulated using one stack at different instances , so if one case fails we can say unequal , but for it to be equal it should be match in all cases , so equality cannot be generated . am i thinking right? $\endgroup$
    – Pavan Kumar Munnam
    Commented Dec 2, 2016 at 17:49
  • 1
    $\begingroup$ Showing that a language isn't context-free requires proof. Intuition isn't enough. $\endgroup$
    – Yuval Filmus
    Commented Dec 2, 2016 at 17:52
  • $\begingroup$ I know that it is cfl , I was talking intuition about how npda works $\endgroup$
    – Pavan Kumar Munnam
    Commented Dec 2, 2016 at 17:56

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.