Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?

Let $$S = \{ w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star ; (∃i < k) w_i\neq w_{i + 1}^r$$ , i.e., not every string $$w_i$$ is equal to the reversal of $$w_{i+1}$$. Note $$S ⊆ \{0, 1, \#\}^\star$$.

Show that S is a CFL by a PDA, P, that accepts it.

I have been stuck on this question for approximately 20+ hours. I tried to sketch the PDA about 20 pages but still fail some cases. My friend's suggestion as store the word $$w_i$$ then the next state is to compare $$w_{i + 1}$$ to $$w_i$$, however, what I'm struggling is how do we compare $$w_{i + 2}$$ to $$w_{i + 1}$$ after comparing $$w_{i + 1}$$ to $$w_{i}$$. This seems impossible since the stack has to be pop out an element in order to compare the previous word. Once it's empty, we can never fill up the stack with the same elements that already popped.

Another way that I found is referring to this link: https://cseweb.ucsd.edu/classes/su99/cse105/hw2sol.pdf.

On question 3, it has a construction for non-palindrome over $$\{0,1\}^\star$$. Which is similar to our case but we have a $$\#$$ sign between words. I.e., we have many different strings instead of this construction only need to handle one string and compare it's left and right. I have been stuck for a long time, I think I'm missing something here. Any suggestions?

• Use nondeterminism to avoid checking all consecutive pairs. – Hendrik Jan Feb 13 at 9:52

Use nondeterminism to guess an index $$i$$ for which $$w_i \neq w_{i+1}$$. The machine reads its input until it nondeterministically chooses a $$w_i$$ and places it on the stack. Afterwards, it compares $$w_{i+1}$$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.
I suggest you try some special cases. First, can you handle the special case where we force $$k=2$$? If not, work out how to solve that first, before handling the full problem. Next, try to handle the case where $$k=3$$. I recommend using the techniques in How to prove that a language is context-free? (specifically, look at the closure properties). Once you can solve those two easier versions of the problem, I suspect you should be able to solve the full problem. I would not expect you to write down a PDA for the entire thing from zero: instead, build it up from smaller pieces.
• For instance, if 1#_(empty string), then this should be acceptable state. My construction of the PDA is $q_0$ read 1 and restore 1 into stack, then read #-transition to $q_1$, $q_1$ is essentially popping everything out to make sure both size having same elements. But then how do we pop if we read an empty string, I can simply read $\epsilon$ and pop 1, but other non-acceptable strings(like 1#1) could also use this condition to make the PDA accepts it. – Patrick Feb 13 at 6:53