Skip to main content
Referenced a good point about the necessary memory structure
Source Link
Luke Mathieson
  • 18.3k
  • 4
  • 59
  • 87

The problem with your approach is that you are not checking that $|u| \geq |v|$ - for example the string $0100$ would be accepted. Remember that the 'magic' of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to.

So in this case, you still need to check that the size of the two parts are suitable, for which we need1 a stack.

As a side note, $B$ can also be expressed as $\{u1v\mid u \in \Sigma^{\ast}, v \in \{0\}^{\ast}, |u| \geq |v|\}$, not that this really changes much, but it's a little simpler (in terms of the PDA).

Footnotes:

  1. As Babou points out in his answer, you don't need a stack as such, a simple counter suffices, but you do need something beyond what a DFA/NFA can manage.

The problem with your approach is that you are not checking that $|u| \geq |v|$ - for example the string $0100$ would be accepted. Remember that the 'magic' of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to.

So in this case, you still need to check that the size of the two parts are suitable, for which we need a stack.

As a side note, $B$ can also be expressed as $\{u1v\mid u \in \Sigma^{\ast}, v \in \{0\}^{\ast}, |u| \geq |v|\}$, not that this really changes much, but it's a little simpler (in terms of the PDA).

The problem with your approach is that you are not checking that $|u| \geq |v|$ - for example the string $0100$ would be accepted. Remember that the 'magic' of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to.

So in this case, you still need to check that the size of the two parts are suitable, for which we need1 a stack.

As a side note, $B$ can also be expressed as $\{u1v\mid u \in \Sigma^{\ast}, v \in \{0\}^{\ast}, |u| \geq |v|\}$, not that this really changes much, but it's a little simpler (in terms of the PDA).

Footnotes:

  1. As Babou points out in his answer, you don't need a stack as such, a simple counter suffices, but you do need something beyond what a DFA/NFA can manage.
Source Link
Luke Mathieson
  • 18.3k
  • 4
  • 59
  • 87

The problem with your approach is that you are not checking that $|u| \geq |v|$ - for example the string $0100$ would be accepted. Remember that the 'magic' of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to.

So in this case, you still need to check that the size of the two parts are suitable, for which we need a stack.

As a side note, $B$ can also be expressed as $\{u1v\mid u \in \Sigma^{\ast}, v \in \{0\}^{\ast}, |u| \geq |v|\}$, not that this really changes much, but it's a little simpler (in terms of the PDA).