# Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity

I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $$x\#y$$ where $$x$$ and $$y$$ are strings of 1s and 0s such that there must be at least one difference and at least one similarity between $$x$$ and $$y$$. Here is the meaning of one similarity. Let $$x=x_1x_2\cdots x_m$$ and $$y=y_1y_2\cdots y_n$$, where $$x_1,x_2 \cdots, x_m, y_1,y_2, \cdots, y_n\in\{0,1\}$$, then there exists an index $$i$$ such that $$x_i=y_i$$.

I understand that I must have two separate cases, with one case assuming that $$|x| = |y|$$ and one case where $$|x| \not= |y|$$. Right now I am only working on the case where $$|x| = |y|$$. So far, I am using nondeterminism to find the $$i$$-th value of $$x$$, matching it against the $$i$$-th value of $$y$$. However, this only determines if there is at least one difference between $$x$$ and $$y$$. I am failing to see a solution where I can also determine that there is at least one similarity. If anybody can point me in the right direction, it would be much appreciated.

• Please fix your formatting using LaTeX. – orlp Apr 4 '19 at 0:48
• Yes that is correct – emcnier Apr 4 '19 at 1:01
• Welcome to Computer Science! Adding to orlp's comment, see here for a short introduction to LaTeX formatting. – dkaeae Apr 4 '19 at 7:09

Here is the critical observation. We can combine the two conditions, there must be at least one difference and there must be at least one similarity between $$x$$ and $$y$$ into the following one condition.

Let $$x=x_1x_2\cdots x_m$$ and $$y=y_1y_2\cdots y_n$$, where $$x_1, x_2,\cdots, x_m,y_1, y_2,\cdots, y_n\in \Sigma$$. Then $$x\#y$$ is a word in the language if and only if there exists an index $$i$$ such that

• $$x_i\not=y_i$$ and $$x_{i+1} =y_{i+1}$$ or,
• $$x_i=y_i$$ and we do not have $$x_{i+1} =y_{i+1}$$.

The precise meaning of "we do not have $$x_{i+1} =y_{i+1}$$" is either exactly one of $$x_{i+1}$$ and $$y_{i+1}$$ is defined or $$x_{i+1}\not= y_{i+1}$$.

The basic motivation of the idea above is that an PDA can only keep track of one unbounded counter. So we should compress two unbounded counters, the index of the similarity and the index of the difference into one unbounded counter.

• "An PDA can only keep track of one unbounded counter. So we should compress two unbounded counters, ..." should be "an PDA can only keep track of one unbounded counter at any point of time. So we should compress two interleaved unbounded counters, ..." – John L. May 26 '19 at 6:40