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

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

• I’m voting to close this question because it has been asked and answered before. Jan 18 at 10:59
• @Yuval Filmus I still am stuck. I am not able to solve it. You can vote to close this, that's okay. But can you help me with this question? Jan 18 at 11:01
• The first step is to link to the previous post, and to explain why you couldn’t understand any of the answers. Any new answer should be added there. Jan 18 at 11:03
• Why am I not able to see anything? I am getting notified of comments but I don't see them here.. what is happening? Jan 18 at 12:38
• Does this answer your question? PDA recognising all strings with a $1$ in the second half Jan 31 at 1:18

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}

• Thank you so much. I have tried to draw a pda. But it's accepting some strings that it should not. I will think about it more. Jan 18 at 17:52
• Well then, you have made some mistake. Unfortunately you cannot expect us to debug your PDA. Jan 18 at 17:53
• Yes, I understand. Thanks. Jan 18 at 17:53
• Just one more question, even if it's a nondeterministic pda, no branch should accept the string 10010000, right? Jan 18 at 17:56
• The PDA should accept a string in some branch iff it is in the language. Jan 18 at 17:57