0

I'm studying automata and I have this problem related to PDAs I asked this question on stack overflow but then thought this place is more appropriate.

Construct a PDA for the language

$L = \{ w = x_1y_1x_2y_2\dots x_ny_n \mid \text{ where $w$ belongs to } \{0,1\}^*$, and the string $y_1y_2\dots y_n$ is the same as $x_1x_2\dots x_n$ except the $1$’s in $y$ come after the $0$’s $\}$

For example the string 100111 belongs to $L$ since x=101 and y=011. So do the strings 0011, 00, 1111, 100001, etc. However, the strings 0110, 11111001, 1100, 01, 10 do not belong to $L$. For simplicity, in the construction of the PDA assume the input consists of pairs of symbols in which the first belongs to $x$ and the second to $y$. Thus the input alphabet is $\Sigma = \{00, 01, 10, 11\}$.

I realize I have to push/pop from the stack in a way that guarantees that the same input in $x$ appears in $y$ where 0's come before 1's a but the problem is how to check that the 0's in $y$ come before the 1's.

A hint for the solution is really appreciated

Hendrik Jan
  • 1,910
Ike
  • 3

1 Answers1

1

The $y_i$ in the string are on every second position, and it is not very hard to keep the $0$'s before the $1$'s in that subsequence. You do not have to know what moment to switch, just use nondeterminism and guess.

The second task is to check that the number of $0$'s and $1$'s in the $x_i$ and $y_i$ subsequences match. But since these sequences have the same length it suffices to check only one of these symbols. You can used the pushdown stack for that purpose.

Hendrik Jan
  • 1,910