Deterministic and Non Deterministic PDA's

The use of a stack, otherwise said of memory, in push down automata gives us the ability to describe strings that until now we have been unable to describe.

For our machine we will use an alphabet of only two letter for the stack X as a token and Z representative of the empty stack. Each arrows state label now consists of three parts, the alphabet the stack token, which is also an alphabet, and the previous stack token, empty state or pop command. For 0,X,XX we have received a zero so we stay on the first node the next symbol in our notation gives the current state of the stack, Z when it is empty, to show what it is that is being put on the stack, the third value XZ shows us that we are putting X on top of Z. This notation is not always used, but it is often that which is found in text books today.

Value received, the state of the stack followed by the operation, however with this transition alone, we can not accept our target string, for this we will have to add another transition, one that will accept another token, when there is already a token on the stack. For this we add a transition with the values 0,X,XX, upon receiving a zero, if the token is X then add it to the stack XX.

If the machine receives a 1 then it moves on to its next state node, and the stack is popped, here we write pop in the nodes arrows alphabet description. Some books use e to denote this.

0^n1^n

The annotation found beside each path of this push down automatons nodes represent: the symbol of the alphabet that has been seen, the symbol on the top of the stack, the next symbol to be put on the stack, or the command to pop the symbol from the top of the stack.

e nuance

The presence of an e, unlike the case for regular languages where the symbol implies that the machine is non deterministic; The e move does not necessarily represent a choice in these diagrams, extra information about the stack also accompanies the symbol, and as such we only follow the e move when the appropriate letter for the next state is also present.

Upon receiving the empty state when on what is our Pop node, if the stack is empty, or rather when it, contains and presents a Z then we are done. A stack action Z technically means that we push a null or a nothing onto the stack, which is not quite the same thing as doing nothing at all.

We have added a stack enabling us to read the string 0^n1^n, this was not possible with a simple finite state machine. When using a stack we must first define our stack alphabet, it can be as long as you want to make it, in this case was simply X, the push down automata state machine with a simple single symbol alphabet is a particular case of machine that does not have all of the power of a full PDA.

A stack with only one symbol is called a counter, because all that it can do is count, it could not for example read a palindrome, because it lacks the memory to contain the order, you need two counter to simulate a general stack and four counters to make a Turing machine.

Palindromes

The alphabet ww^R or w∈(0+1)^* means any string of zero's and one's that is followed by its reverse, or otherwise said, a palindrome. We are going to write a push down machine that can determine a palindrome, we will try to make that machine deterministic.

The difficulty here seems to be in knowing when it is that we have reached the middle of our string and thus when to start checking for the reverse pattern. In order to better understand this, and for an initial simplification of the problem, we can alter our language description to include a 2 that will indicate the middle of the string, it is often the case in the fields of both computer science and mathematics that when a problem initially appears to difficult to solve, first solving a simpler problem leads to the solution for the more complex one.

We will start of with a simple push state that will read in the string and as it receives 0's and 1's it will push X's and Y's.

We do not draw in the fail states on push down machines because there are so many of them, but if on the matching half of this machine we encounter either an 0 that does not accompany an X or a 1 that does not accompany a Y then the machine moves into the fail state.

Our machine is now non-deterministic, we can still read a palindrome and finish with the machine in the end state but we must guess when to swap over to the pop state, non determinism is essentially this, guessing. We can imagine that every possible path is taken, and that those which do not complete are erased and like this the guess seems somewhat less haphazard. It is inevitable that the machine will, if the string is a palindrome, eventually hit the right moment to change states and discover the reverse of the initial string.

The compliment of ww^R, remembering that context free languages are not closed under compliment, that there is a way to get even length palindromes does not imply that there is a way to get their compliment, we can not simply toggle the final and non final states as we did for deterministic machines.

Deterministic context free languages are closed under compliment, which means that if you take the compliment of a deterministic context free language, you get another deterministic context free language. Whereas if you take the compliment of a non deterministic context free language, you don't necessarily get another.

We can do the same toggling trick for deterministic context free languages as we did for finite state machines, but this trick will not work for non determinism as it did not work for non determinism in finite state machines either. If you toggle the states in a non deterministic finite state machine, you do not get the compliment language.

• DCFL's closed under compliment
• CFL's closed under union

This can be proven with this language, it is the union of two deterministic machines, the result of which requires a non deterministic machine to be accepted, providing a counter example to the hypothesis that they be closed under union.

To accept this sting requires non determinism, the two halves of the language that have been joined under union can not be mixed deterministically. Neither one of the two halves are closed under intersection because intersection would require two out of the three operations of union compliment and intersection. If either of the two were closed under compliment and union, then it would be closed under intersection, neither one of our two half's of the grammar are closed under both compliment and union.

Our initial grammar gave us even length palindromes and we want the compliment of that, as such our machine must only accept odd length strings that are not palindromes, to achieve this we make a simple machine that will track odd and even state.

We can notice from this machine that a finite state machine, such as the one that we are using to determine whether the length of our string is odd or even, can be a push down machine also, the nuance being that it is not using its stack during the particular part of the process.

Next having already accepted only strings that are odd lengths, next we will accept only string that are not palindromes that do not have their second half match the reverse of their first half.

When using push down machines we can make guesses, but we must then check whether or not the guess has worked out, we can not accept a string after making such a guess as the half way mark, unless we then check that the guess was correct. To check our guess as to the position of the centre of the string we must pop symbols for the entirety of the remaining string, verifying that we have the empty string when the stack has been emptied.

We construct this machine in several parts first to select for only odd length strings and secondly to test that the reverse of the string after the centre symbol do not match, and finally to check that the guess as to which is the centre was correct.

The only way that we can get to an accept state in our machine is if we have either an even length string or a mismatch in the symbols of the comparison of the two halves of the string, with one reversed.

Another solution

There is another way of doing the bottom half of our previous machine, using the same to detect for even strings another way to determine that the string is not a palindrome, using a different idea.

This other way is to check at a point some distance into the string, that the symbol that is found the same distance from the end of the string is not the same, if we find only one instance where they are not matched we have shown that the string is not a palindrome.

This time we will just count as we go into the string putting an X onto the stack for both 0's and 1's without remembering what the symbols are, and at some undetermined point we are going to stop and look at that particular symbol and remember what it is.

This is another example of our non determinism being used as a higher level of guessing, in order to check that a condition of the state machines acceptance requirements has been met.

A harder problem

It is not possible to make a push down machine that can accept ww but we can make a machine that will find its compliment, however the way that it can be done is not easy to see.

The key to understanding how this machine will work is in understanding that in order to ascertain that two halves of a string are not identical we need to make two guesses, firstly as to which symbol is the symbol that differs and secondly as to where the centre of the string is, doing this is exactly the same as tracking the length of half of the string.

Which is to say that twice the length of the string consumed before deciding which symbol to check plus the length that remains after that symbol before the halfway point, brings you to the symbol in the second half of the string that is to be checked.

By pushing onto the stack until we get to the symbol and then popping until empty, followed by pushing half the length back onto the stack will leave us on the symbol that is to be verified. ~he number of symbols on the stack should now be the same as the length of the remaining string.

This gives us both our conditions for the required guesses to make a comparison, to find a mismatch and the length of the string that should remain to insuring that the position of both symbols was the same in each halve of the string.

We can push onto the stack for duration of a until we select a symbol to test, then pop until the empty stack from where we can then guess at b the distance from our symbol test to the midway point of the string, pushing onto the stack until we reach the next symbol to test, then popping b to confirm that we have chosen the correct centre point if we arrive with an empty stack at the end of the string.