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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\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$ 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.