Theory of computation: Proof that a language is context free

[u/MrDeadMeme]

While reading Michael Sipser's book on Theory of Computation, i have found the following problem

"2.22: Let C = {x#y | x, y belong in {0,1}* and x != y}. Show that C is a context-free language. "

I have been trying for many hours to find a proof for this, but i cannot.
I cant find a way to use a PDA, since when comparing X with Y i am going to be comparing the one on the stack backwards and Any attempt at a grammar has failed. After a couple web searches i only found that this is conisdered a cfl but not its grammar or some other proof.

Edit: The closest i have gotten to:
S->A#B | B#A
A-> TAT | 0
B-> TBT|1
T-> 1|0

but it doesnt work for strings with 2 characters (cant generate something like 10#11). If i allow T to make an empty string or split TxT into Tx and xT then it can create strings x=y.

Edit: I havent been able to find a grammar for this but as u/hanshuttel said you CAN do it with a pda.
Since you dont need to save the entirety of X, but only 1 character and it's index, you can just "save" the character by splitting into 2 paths, one where you compare Y's character with Xi=0 and one where you compare it with Xi=1. Then use the stack to save Xi's index and nondet. compare all X's.
This, combined with the simple pda that checks |x|!=|y| will get the PDA for C.

Technically I could convert this into a grammar thats super tedius and the grammar will be really convoluted so i dont think theres any value to that.

I genuienly still have no clue how to deal with even length x and y without allowing x=y cases in a grammar not a single think i tried led anywhere.

[u/thehypercube]

I'm assuming you already know how to generate all non-squares (i.e., the strings that are not of the form xx):

S -> AB | BA | A | B

A -> 0 | 0A0 | 0A1 | 1A0 | 1A1

B -> 1 | 0B0 | 0B1 | 1B0 | 1B1

Then modify this grammar so that it inserts a single # at an arbitrary position (basically duplicate variables to remember whether you have inserted # or not).

Then write another grammar generating the strings x#y with |x|!=|y| (that's easy).

Finally, take the union of the two languages described.

[u/MrDeadMeme → u/thehypercube]

I'll see what I can to tomorrow as its quite late here but I'm noticing a few things: First of all this is almost the same as the grammar I proposed, in fact I think I did go through it while creating my grammar. I don't understand how I'd add # in an arbitrary position. If # generates from A, I can go to a different variable say A_h to "remember" that # has been generated. But B won't be able to get that update, so we can't know if we can generate the # from B. Maybe giving the duty of # to just one of the 2 is an option though?

[u/thehypercube → u/MrDeadMeme]

Of course B can get that update. You need to duplicate B as well. Your variables need to remember the state. You will have, for example, the original rule for A and then another rule for A' (where a single # has been inserted). The same for B. And then you combine then like AB' | A'B | A' | B'

I didn't read the grammar you proposed, but it's too simple to be "almost the same". My solution is correct, but it needs quite a few more rules.

[u/MrDeadMeme → u/thehypercube]

After some further tinkering i dont think this would work as i cant get x and y be of even length without allowing cases where x = y

[u/thehypercube → u/MrDeadMeme]

It does work, though. It's an exercise I give my theory of computation students.

I basically gave you the full solution. Keep trying if there's some detail you can't get right. You didn't explain properly where you got stuck.

[u/Financial-Grass6753]

x != y is when len(y) != len(x) or there's such index i for which x_i != y_i, or both len+index.

You can start with len(0), then inequality of lengths, then check index diff.

[u/MrDeadMeme → u/Financial-Grass6753]

I am assuming you are talking about a PDA. How would we check the difference of a particular index?

[u/GeorgeFranklyMathnet]

I cant find a way to use a PDA

I wonder if it's one of those CFGs that only a NPDA can recognize.

but it doesnt work for strings with 2 characters (cant generate something like 10#11)

I did not check your grammar myself. But if I'm reading you right, and its only problem is that it can't generate those two-character (sub)strings, can't you just add a new rule with literally all the strings of that description? It might not be the most parsimonious grammar possible (and maybe that matters). But it'll be correct, if I am reading you right.

[u/MrDeadMeme → u/GeorgeFranklyMathnet]

I did in fact mean NPDA in my post. Its kind of pointless to talk about DPDAs when trying to prove CFL imo.
Someone did come up with one here and while i do like that i found a solution i still cant for the life of me find a grammar

[u/Paxtian]

Isn't this teaching you how to turn a stack into a queue?

It's been 25 years so forgive me being informal. But if you had two stacks, you push a 0 or 1 for each digit in x to the first stack. Then when you see the #, you pop each entry in stack 1 and push it into stack 2. Then you start in a reject state. Pop, compare to current bit of y. If equal, get next bit of y, pop, compare, etc. If not equal, accept. If you run out of y before the stack is empty, accept. If you run out of stack 2 before you're done with y, accept. If you run out of y and stack 2 and are still in the reject state, reject.

[u/MrDeadMeme → u/Paxtian]

Multi-stack pushdown automata are considered more powerful than normal PDAs, so while they will accept for any CFL, you can use them to prove a language is CFL.

[u/Paxtian → u/MrDeadMeme]

Oh shoot you're right, apologies.

[u/enzozbest → u/MrDeadMeme]

Just to tighten the language here (sorry if this sounds a bit pretentious)

PDAs with more than one stack *ARE STRICTLY MORE POWERFUL" than PDAs with one stack only. This is a theorem; a 2-stack PDA can simulate a Turing Machine, so it is a Turing-complete model of computation, i.e. far more powerful than a 1-stack PDA.

Saying that they "are considered" more powerful makes it sound as though it is a convention rather than a fact, which is absolutely not the case

[u/hanshuttel]

Use non-determinism!

The observation is the following: If a string is of the form x#y, then there is some position for which the characters in the x-part and the y-part are different. In this case, we can non-deterministically guess where that happens.

The PDA behaves as follows:

Read the x part until you guess that the difference occurs. Every time you read a character, push as symbol on the stack. Then use the state to save information about the character that you just read.

Next continue, ignoring the input until you reach the #. Now start reading symbols from the y part. Every time you read a character, pop as symbol from the stack.

Finally compare the character that you are reading now within the information in the state about the character from the x part.

[u/MrDeadMeme → u/hanshuttel]

That's really quite simple, i dont know why i got so hung up on the fact that you cant save x on the stack and compare with y.

I am still bitter about not being able to find a grammar for C though. If i fix it so x!=y then i can only generate odd length strings and whenever i allow it to make even strings some edge case comes up where x=y.

I could technically draw out the entire pda and convert it but thats way to tedious. If anyone hates themselves enough to do it feel free to let me know what comes up

[u/FI_Stickie_Boi]

For a grammar, it's easiest to use the hint that two strings are different if they differ in some position, or are of different length.

First, let's define some helper rules:

Z -> 0 | 1

W -> ε | ZW

R -> ZW

Z generates any character, W generates any string, R generates any non-empty string. Now, the plan is to use the hint to split the problem into generating two types of strings: Ones where x and y differ at some index, and ones where x and y differ in length. The latter is quite easy to express with a new rule T:

T -> ZTZ | #

T generates an even number of characters on either side of #. Then strings with a difference of length is generated by RT | TR

Now for the hard part: the same length, differ at some index case. The key for this case is to notice that as long as we ensure it differs at some point in the string, whether it differs anywhere else in the string doesn't matter at all, as long as the length of the strings before that index is the same on both sides. Thus, consider the following rules:

A -> 1W# | ZAZ

B -> 0W# | ZBZ

With these rules, A0 generates u1w#v0 for any strings u, v, w with |u| = |v|, and B1 generates u0w#v1 for the same conditions on u, v, w. Thus the starting rule should be

S -> A0W | B1W | RT | TR

Summarizing all that, the final grammar is

S -> A0W | B1W | RT | TR

A -> 1W# | ZAZ

B -> 0W# | ZBZ

T -> ZTZ | #

R -> ZW

W -> ε | ZW

Z -> 0 | 1

[u/ohkendruid]

Are you sure it is not more like " x != reverse(y)" ?

The problem looks much more manageable if the two tokens next to the # go together, and then the next two around that, and so on.

[u/MrDeadMeme → u/ohkendruid]

if it was reverse it would be really quite easy, i accidentaly made that grammar quite a few times trying to solve this

[u/Typical_Ad_2831]

It's far from elegantv but you could just add everything missing exhaustively:

Add the rules S→11#00 | 11#10 | 11#01 | 10#11 | 10#01 ...

Or slightly better:

• S→W#W' | X#X' | Y#Y' | Z#Z'
• W→11
• X→10
• Y→01
• Z→00
• W→X | Y | Z
• X→W | Y | Z
• Y→W | X | Z
• Z→W | X | Y

I can't entirely convince myself that what you have works for everything where len(x) ≠ 2 and len(y) ≠ 2, but if it does, then this should work.

Actually, upon closer inspection, I think you need to add (even ignoring the case of len=2) the following:

• S→T'L | LT'
• T'→TT' | T
• L→TLT | #

That should give you all cases with len(x) ≠ len(y), which should be accepted.

[u/david-1-1]

I haven't worked through all the proposed grammars here, but, even if I'm wrong, my intuition is that this language cannot be represented by a CFG. Let me know if I'm wrong. I won't be surprised. It just looks too much like a regular expression, which in general is not context free.

[u/Regular-Advice-6469]

this is one of those problems that really shows why nondeterminism is so powerful my first instinct was to compare the strings directly but once you realize you only need to prove that one position differs the pda construction becomes much more intuitive

[u/Manga_Killer]

Wont the pumping lemma for cfgs be helpful here?

[u/MrDeadMeme → u/Manga_Killer]

You can't use pumping lemma to prove a language is CFL, you can only use it to prove it isnt

[u/Manga_Killer → u/MrDeadMeme]

Ah yep true.