0
$\begingroup$

How could I build a PDA on $Σ = \{a,b\}$ that accepts if there is an "a" in the second half of the string?

Formally the language is the following: $L = \{xy \mid x ∈ Σ^*, y ∈ Σ^*aΣ^* \land |x| ≥ |y|\}$.

$\endgroup$
1
$\begingroup$

The PDA has three phases. In the first phase, it adds $A$ to the stack per character. It switches to the second phase nondeterministically. In the second phase, it removes $A$ per character. It switches to the third phase nondeterministically, during which it empties the stack. The PDA accepts if it encountered an $a$ during the second phase.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.