0
$\begingroup$

I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the input is read fully or not).

I can guess PDA with the new definition of acceptance is less powerful, and easy to see every language accepted by this PDA is accepted by some PDA with the conventional definition. But, can anyone give some idea how to show some languages are not accepted by the new PDA?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Prefixes. How would you accept both $a$ and $aa$ ?

Improve this answer
$\endgroup$
2
  • $\begingroup$ So, If it accepts 'a', then it has to accept $a\{a,b\}^*$? $\endgroup$
    – Saravanan
    Nov 26, 2020 at 11:25
  • $\begingroup$ @saravanan Indeed, that is a better formulation than mine! $\endgroup$
    – Hendrik Jan
    Nov 26, 2020 at 11:59

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.