PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1

Question

Consider the language $\{ uv : \text{$|u| \ge |v|$ and $v$ contains a 1}\}$.

I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if there's a 1 in the $v$ portion?

The question has previously been posted here but I couldn't figure out much from the answers to that. PDA recognising all strings with a $1$ in the second half

Answer 1

A pushdown automaton accepting this language proceeds as follows:

1. Push a marker $S$ to the top of the stack.
2. Push $A$ to the stack for each input symbol read.
3. At some point, nondeterministically transition to the second phase.
4. Pop $A$ from the stack for each input symbol read, marking whether you ever read $1$.
5. Fail if you encounter $S$.
6. Succeed if you successfully read the entire input, and encountered $1$ during the second phase.

It is also easy to give a context-free grammar for this language, using $\Sigma$ as a shortcut for the alphabet: \begin{align} &S \to \Sigma S \mid \Sigma S \Sigma \mid \Sigma T 1 \\ &T \to \Sigma T \Sigma \mid \epsilon \end{align}