1
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ I’m voting to close this question because it has been asked and answered before. $\endgroup$ – Yuval Filmus Jan 18 at 10:59
  • $\begingroup$ @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? $\endgroup$ – user766787 Jan 18 at 11:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 18 at 11:03
  • $\begingroup$ Why am I not able to see anything? I am getting notified of comments but I don't see them here.. what is happening? $\endgroup$ – user766787 Jan 18 at 12:38
  • 1
    $\begingroup$ Does this answer your question? PDA recognising all strings with a $1$ in the second half $\endgroup$ – xskxzr Jan 31 at 1:18
1
$\begingroup$

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}

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – user766787 Jan 18 at 17:52
  • $\begingroup$ Well then, you have made some mistake. Unfortunately you cannot expect us to debug your PDA. $\endgroup$ – Yuval Filmus Jan 18 at 17:53
  • $\begingroup$ Yes, I understand. Thanks. $\endgroup$ – user766787 Jan 18 at 17:53
  • $\begingroup$ Just one more question, even if it's a nondeterministic pda, no branch should accept the string 10010000, right? $\endgroup$ – user766787 Jan 18 at 17:56
  • $\begingroup$ The PDA should accept a string in some branch iff it is in the language. $\endgroup$ – Yuval Filmus Jan 18 at 17:57

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.