-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!

$\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
    Jun 11 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.
    Jun 12 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
    Jun 12 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.
    Jun 12 at 21:20

1 Answer 1

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

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

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.