-1
$\begingroup$

To those of you who saw my post from an hour ago - I deleted it because I came up with an idea.

To summarize, I have to design a PDA for this language, without using the usual method of firstly defining a CFG then transforming it to a PDA.

$ L = \{ a^{3n}b^{2n} | n \ge 0 \}$

Here is my proposed solution: enter image description here

Since I didn't know how to implement non-determinism, I limited the number of "a"'s on the stack to the number of b's to be read. Then I just pop the $a$s from the stack.

My question is, is this a valid PDA for this language? If not, can anyone give a few examples of strings that are either wrongfully discarded or wrongfully admitted by the PDA, and a possible solution or hint?

Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ @user19121278 what string from $a^{3n}b^{2n}$ doesn't it accept? The principle I was going after is that the numbers of "a" (after reading all symbols of "a") should be the same as the number of "b" to be read. That way, I can pop one $a$ for every read $b$. $\endgroup$
    – john doe
    Commented Jun 11, 2022 at 15:32
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Jun 12, 2022 at 4:46
  • $\begingroup$ @D.W. Hello! Thanks for your input. Unfortunately, I the characterization of my question with just "please check whether my answer is correct" is a bit insulting as I have put in real effort to format my post to the best of my abilities and to provide matter for discussion. If you are unsure about my question, see the sentence directly under the photo which pertains to me providing an alternative way of solving it, which I was unsure about because I did not know how to implement non-determinism. Unfortunately, I will not be editing my post. $\endgroup$
    – john doe
    Commented Jun 12, 2022 at 8:56
  • $\begingroup$ I understand that you put a lot of effort into formatting the post, but unfortunately a well-formatted "please check whether my answer is correct" is still unlikely to be useful to others in the future, as they're unlikely to have exactly the same question. (We're not here for discussion.) Instead, we encourage people to think about whether there is some broader conceptual issue that might be useful to others, that they can ask about, so the question will be useful to others even if they aren't facing exactly the same exercise and aren't considering exactly the same solution. $\endgroup$
    – D.W. ♦
    Commented Jun 12, 2022 at 21:20

1 Answer 1

Reset to default
2
$\begingroup$

Your language is DCFL. But you made NPDA because in state $q_5$ the transitions $(q_5,\epsilon,a)\neq\emptyset$ and $(q_5,\epsilon,A)\neq\emptyset$ made your diagram NPDA as I previously said. Below the image is DPDA:enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Doesn't this PDA accept $aaabbb$ which shouldn't be accepted? $\endgroup$
    – john doe
    Commented Jun 11, 2022 at 16:01
  • $\begingroup$ @johndoe corrected, check it. $\endgroup$
    – the_tomato
    Commented Jun 11, 2022 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.