-1
$\begingroup$

I am trying to convert the follow language

$$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$

We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though and I am freaking out because I have no idea how to do them. Could anyone give me a hint or get me started on this example?

$\endgroup$
  • 2
    $\begingroup$ I think learning PDAs in two days is ambitious, but you can try reading a textbook and solving some exercises. You don't need us for that. $\endgroup$ – Yuval Filmus Mar 9 '16 at 21:13
  • 2
    $\begingroup$ Do you know how to do context-free grammars? If so, you can transform those into PDAs quite straightforwardly, see e.g. here. $\endgroup$ – G. Bach Mar 9 '16 at 21:50
  • $\begingroup$ That is the step I am confused with @G.Bach I am not really sure how to do this specific one into a CFG :/ $\endgroup$ – bob afro Mar 9 '16 at 22:12
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Mar 10 '16 at 15:06
  • 1
    $\begingroup$ "the professor didn't teach us much about PDA's" -- then get yourself material and learn about them! Or, you know, use the search function and look at any question tagged pushdown-automata. $\endgroup$ – Raphael Mar 10 '16 at 15:06
1
$\begingroup$

If you've seen nondeterministic PDAs then this is a fairly easy construction. The key idea here is that for every string in your language, each $0$ must be matched with either a single $1$ or two $1$s, so when reading the input, nondeterministically place one or two markers on the stack for each $0$ seen. Then, for every $1$ seen, pop a marker off the stack and accept if the stack is empty after processing all the characters in the string. If the input is in your language, there will be at least one sequence of moves that will leave you in the final state, which is all you need.

| cite | improve this answer | |
$\endgroup$

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.