Prove that language is context-free $C=\{x\#y \mid x,y\in \{a,b\}^*\wedge x\neq y\}$

Question

Prove that this language is context-free: $C=\{x\#y|x,y\in \{a,b\}^*\wedge x\neq y\}$.
I try to construct a grammar:
$S\rightarrow C_a\#C_b|C_b\#C_a$
$C_a\rightarrow XC_aX|a$
$C_b\rightarrow XC_bX|b$
$X\rightarrow a|b$

Is it good ? I can try to prove it.

Edit
$S\rightarrow C_abY|C_baY$
$C_a\rightarrow XC_aX|aY\#$
$C_b\rightarrow XC_bX|bY\#$
$Y\rightarrow Ya|Yb|\epsilon$
$X\rightarrow a|b$
$S\rightarrow RT | TR$
$R\rightarrow aRa | aRb|bRa|bRb |\#$
$T\rightarrow a|b|Ta|Tb$

Do you think that your grammar produces the word $a^n#a^{n+1}$ I mean different lengths and only one word so you have to add some rules to include this but this is a good start — Elaqqad, Apr 23 '15 at 22:40

score 4 · Accepted Answer · answered Apr 24 '15 at 19:35

4

I can’t come up with a good hint this time, but I still want to leave some work for you, so I’ve written the following context-free grammar:

$$\begin{align*} &S\to XA\mid YB\\ &X\to aXa\mid aXb\mid bXa\mid bXb\mid bZ\#\\ &Y\to aYa\mid aYb\mid bYa\mid bYb\mid aZ\#\\ &A\to aZ\\ &B\to bZ\\ &Z\to aZ\mid bZ\mid\lambda \end{align*}$$

It almost works, but not quite: there are some words in the language that it doesn’t generate. The missing ones can quite easily be generated separately, but first you’ll have to figure out what this one is doing. To get you started: basically it’s designed to ensure that the two parts of the word differ in at least one position.

answered Apr 24 '15 at 19:35

Brian M. Scott

616,228

Look at my edition first :) – user220688 Apr 24 '15 at 19:36
1

@user220688: It’s a lot better, but it doesn’t quite work: as it stands, you get at most one letter after the mismatched pair. You need to change the $Y$ productions a little. (But yes, it’s a very similar idea to mine.) – Brian M. Scott Apr 24 '15 at 19:45
Yes, at first sight it's easy to see similarity. But I don't get your advice. The only thing that my grammar is wrong is: $a^k#a^l\wedge k\neq l$, $b^k#b^l\wedge k\neq l$ – user220688 Apr 24 '15 at 20:17
1

@user220688: You also don’t get $aaa#baa$. – Brian M. Scott Apr 24 '15 at 20:24
I edited again. Now, do you see other examples , besides found by me ? – user220688 Apr 24 '15 at 20:45
1

@user220688: I don’t think so; that’s the edit that I originally had in mind. I’ve not checked carefully, but I think that your grammar now generates the same language as mine, or very close to it. – Brian M. Scott Apr 24 '15 at 20:48
I have just edited. – user220688 Apr 24 '15 at 20:54
@user220688: You’ll need to do the same for $b$. And are you sure that you get $ab#abab$, for instance? I’m fairly sure that you don’t. You could fix that problem, though, by changing the added bit to cover all cases of $x#y$ where $|x|\ne|y|$. – Brian M. Scott Apr 24 '15 at 21:00
Yes, I know about the same situation for $b$. Yeah, you are right. I have to cover every case such that $|x|\neq |y|$ – user220688 Apr 24 '15 at 21:03
What about current corrected solution ? – user220688 Apr 26 '15 at 11:57
1

@user220688: I didn’t recheck every detail, but it looks okay to me. – Brian M. Scott Apr 26 '15 at 19:17
Thanks you very much, it was very intresting task! – user220688 Apr 26 '15 at 19:18

user2566092 · Answer 2 · 2015-04-23T22:49:11.773

1

Your current grammar will only produce string x#y where x and y both have odd length, and the only characters guaranteed to be different between x and y are in the exact middles of the two strings. There are more possibilities for x and y and more ways that the two strings could be different, e.g. being the same length but only guaranteed to be differing in another position besides the middle, or simply being different lengths even if x and y are all "a" or all "b". In fact if the string lengths of x and y are different then x and y could be anything.

edited Apr 23 '15 at 22:49

answered Apr 23 '15 at 22:42

user2566092

26,142

I edited my first post – user220688 Apr 24 '15 at 19:31

Prove that language is context-free $C=\{x\#y \mid x,y\in \{a,b\}^*\wedge x\neq y\}$

2 Answers2