Question

give a PDA for the language {a₁a₂: where the length of a₁ equals the length of a₂, a₁ contains an odd amount of 0’s and a₂ contains an odd amount of 0′s}

a₁, a₂ ∈ {0, 1}*

Answer 1

since we dont know the middle of the string, we would need a PDA which non-deterministically guesses the middle of string and then counts the number of 0's in the string.

So firstly we keep track of number of 0's before the middle of strings (transition only if it is odd), then we guess the middle of sring and then count the number of 0 in the right half.

The PDA is:

the states are marked even, odd based on numbers of 0 encountered. starting at q0 #0 is 0, if 1 comes we stay at the same state, if 0 comes we move to odd state, we also push 'x' to stack which we would use to match te length of either side of the string. from state q1 we non deterministically guess that it is the middle of string ,so we transition to other part of the PDA which would count the #0 in right half and also checks the length.