# 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. – Yuval Filmus 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? – user766787 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. – Yuval Filmus 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? – user766787 Jan 18 at 12:38
• Does this answer your question? PDA recognising all strings with a $1$ in the second half – xskxzr 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. – user766787 Jan 18 at 17:52
• Well then, you have made some mistake. Unfortunately you cannot expect us to debug your PDA. – Yuval Filmus Jan 18 at 17:53
• Yes, I understand. Thanks. – user766787 Jan 18 at 17:53
• Just one more question, even if it's a nondeterministic pda, no branch should accept the string 10010000, right? – user766787 Jan 18 at 17:56
• The PDA should accept a string in some branch iff it is in the language. – Yuval Filmus Jan 18 at 17:57