1

I won't deny that this is not my homework question, but I've been thinking for a couple of hours and still have no understand

$L = \{w | w ∈ \{0, 1\}^*\}$, w is a list of unary integers separated by 1’s that are not in ascending order.

E.g. 00101000, 00010001000, 001010 are all acceptable but 010010000 is not.

I'm able to check the count for two set of 0's but I don't get how to do it for three or more? Nondeterministic PDA is also an option but again, I'm unable to get how to use it. I would like to know how to work with such languages.

Harshil Sharma
  • 149
  • 3

1 Answers1

1

HINT: You’ll want to make the PDA non-deterministic, and I think that it’s easiest to have it accept by final state. The basic idea is to let it start by reading symbols without doing anything else. At any point when it’s reading a $0$ it can ‘decide’ to treat that $0$ as the beginning of a block of $0$s. Starting with that $0$ it pushes a symbol onto the stack for each $0$ until it reads a $1$ or runs out of input. Assuming that it reads a $1$, it then pops a symbol off the stack for each $0$ in the next block of $0$s. If it empties the stack, it goes into an acceptor state: the string cannot be strictly increasing. If not, it goes back to reading symbols as it did at the beginning.

If you don’t allow consecutive $1$s, you’ll have to do a little extra processing in the finite state part of the automaton, both before and after you detect a non-increasing pair of blocks of $0$s, but that’s a relatively minor complication.

Brian M. Scott
  • 616,228