18 views

Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one  $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$.

1. Give a PDA that recognizes $B$.
2. Give a CFG that generates $B$.
| 18 views