Pushdown Automata

The machines in flowchart

  Introduce a new way to pictorialize the FA, we used to use circles, edges and some symbols to represent a DFA pictorially, now we're to use some different graphics to do the same thing.
  Let the INPUT TAPE denoted by \tt TAPE becomes a infinitely long tape with cells, each of which could hold a single letter, and those cells are filled with \Delta denoting blank cells by default, you can fill the \tt TAPE from left to right, cell by cell, each time fill a letter to the current cell, the index of the cells are named by roman numerals \rm cell_i, \rm cell_{ii}, \rm cell_{iii}, etc. For example, the \tt TAPE of aaabbb will be like

there might be infinitely many \Deltas and most of the cells will be filled with it. We assume that rest of the whole tape will be blank(\Delta) once the first blank cell(\Delta) being encountered. The tape is designed as a data structure to hold the strings that're about to be sended into a machine.
  From now on, we're about to use flowcharts to represent the machines, let

denotes accept, reject and start state, by which means that the \tt ACCEPT will be some final states involved a dead loop, and \tt REJECT will be some non-final states involved a dead loop; while both of them will be halt states. We also introduce a new state called \tt READ, the \tt READ state indicates that the machine should read a letter from tape \tt TAPE, and it will be depicted by a box in diamond

be noticed that once a blank cell is read, the input string is considered ended, so the machine will goes into either an \tt ACCEPT state, or a \tt REJECT state; other things such as edges labeled with characeters will be reserved and undertake the same responsibility.
  This new pictorial representation is very similar to flowcharts, and it is indeed that sort of things, the \tt READ state is a diamond box because it's a condition branch

Pushdown stack

  The new machine we're intended to build has a new part called PUSHDOWN STACK which makes it differs from DFA, a PUSHDOWN STACK, abbr. \tt STACK, is a LIFO data structure with infinitely many cells which allows letters to be pushed in and popped out, it is bound with two instructions, \tt POP and \tt PUSH where the former one "pops out" the character at the top of the stack, the later one does exactly opposite, it "pushes" a character onto the top of stack. both of these two operations affect the arrangement of characters left in the stack, \tt PUSH will move all the characters in the stack one cell down to accommodate new character, and \tt POP will move all of them one cell up to fill the blank cell of the removed character. It is legal to call \tt POP when \tt STACK is empty, but it will only result in a \Delta, which means a blank cell. Be careful about the truth that both \tt PUSH and \tt POP operations operate on exactly one single topmost character on the stack, not some of them or any one of them, the stack can only takes action on the topmost element, it can neither interfere what happens below, nor check who is the bottommost character or count the number of the characters in it
  The flowcharts also reserve places for \tt PUSH and \tt POP operations as it did to the \tt READ operations, the \tt PUSH operation will be a square box with a character indicates what is going to be pushed onto the stack, and the \tt POP operation is a diamond box with outgoing edges labeled with characters, just like those \tt READ operations; only \tt POP operation is a condition branch by which means only \tt POP operation could have more than one edges, the \tt PUSH operations have only one outgoing edge, all it can do is push a character onto the stack.
  We call such FAs with \tt STACK, \tt PUSH, and \tt POP operations as pushdown automata, abbr. PDA, the \tt STACK can be considered as a storage device like memory units, its recognizing capability of languages increases substantially because of that stack. Also be aware that the \tt PUSH operation won't consume any letter on \tt TAPE, we use \Gamma to denotes the character(not letter) that can be pushed onto stack to avoid ambiguity, because the stack's alphabet table can be different from the machine's input string.

Nondeterminism

  There're two major classes classified all PDAs, deterministic, and nondeterministic, they're conceptually similar to the definition of DFAs and NFAs, a deterministic pushdown automata, abbr. DPDA, is a PDA that owns an unique path for every string; nondeterministic pushdown automata, abbr. NPDA, on the other hand, allows multiple edges with same label derive from the condition branching state, \tt READ or \tt POP, this implies that NPDAs will allow multiple paths to pass the machine. If strings can reach the \tt ACCEPT by at least one of those paths, we say that the string is accepted by this PDA; if all the paths lead the string into a \tt REJECT, we say that the string is rejected by this PDA. The nondeterminism also allows us to create a state with incomplete edge set, for instance, a b is read from the tape \tt TAPE while we're stucking at a state without any outgoing b edges; this will lead to a crash in TGs or NFAs, the string will be rejected once such circumstance occurs on PDAs.

Recognizing capability

  The additional stack brings a substantial improvement on language recognizing capabilities, the FAs can never recognize languages like a^nb^n because they have no external states, and no external storage, the only way to recognize a such language is to find a way to memorize the occurrences of a, then we can count number of b according to the number of a, since all FAs have is finitely many internal states, the job is therefore impossible, it can only use some circuits to tolerate those infinitely many letters which make it hard to distinguish the a^nb^n and a^{n+1}b^n. The PDAs are different, the additional stack is just like an external state/storage can be used to memorize a lot of things including but not limited to orders and occurrences. In order to accept a string in a^nb^n, all we need to do is push an a onto the stack at each time we read an a, and pop them out after we met our first b, no more a can be read once the pop operation is started; then we say the string is accepted if the stack and tape are both empty at end, otherwise rejected, the PDA can be represented by

  Since the PDAs can recognize languages that FAs cannot, we say that PDAs is more powerful than FAs, the following Venn diagram shows the relationship between FAs, DPDAs, NPDAs' language set

The defects of Deterministic Pushdown Automata

We're now going to explain why NPDA is more powerful than DPDA by showing that some languages cannot be accepted by a DPDA but a NPDA.
  Let language \text{PALINDROMEX}, abbr. \mathcal{P_x}, be sXreverse(s), which means a s and a reverse(s) and a X in between, X is just letter X, not some sort of placeholders, we can build a DPDA accepts this language, so it is obviously that

\lbrace a,aXa,b,bXb,abXba,abaXaba,baXab,... \rbrace

are words in \mathcal{P_x}, the reason why we add an X is that it works like a beacon to tell the machine that the string has reached its middle, so we can start to empty the stack instead of pushing more characters, the corresponding DPDA is

the machine is separated into two sections, the upper section pushes characters according to the letters it read, and transferred to lower section once the letter X is read, then pops an a if reads an a, pops a b if reads a b, if anything doesn't match, the string is rejected. This machine is deterministic because for every conditional branching state there're exactly four outgoing edges corresponding to the mutual exclusive alphabet letters a,b,X and blank symbol \Delta, hence every string has an unique path on this machine.
  Now make a subtle change on \mathcal{P_x}, we introduce language \text{ODDPALINDROME}, abbr. \mathcal{P_o}, \mathcal{P_o} is similar to \mathcal{P_x} with only one difference, the letter X in \mathcal{P_x} has been changed to a or b in P_o, which means this time we cannot identify the middle of the string by finding some special letters, DPDAs can do almost nothing in this case, it can never know when to stop pushing in and start popping out, PDAs are not "forward-looking", they cannot check the middle of string by observing how many letters are left on the tape. DPDAs are incapable in this case.

A more powerful machine: Nonterministic Pushdown Automata

  The previous example can be easily achieved by using NPDA: change the X edge between two \tt READ into a,b(which means a or b) edge, this will make the original DPDA becomes nondeterministic because the first \tt READ will derive two a edges and two b edges, we know that the two part of the machine must be transferred in a very precise point, which is when the middle letter of the string is read, we changed the label X, now the transfer can be executed at any time in many possibilities, and be noticed, the possibility of execution being transferred to the second part at the right time is also included in the "many possibilities", therefore there is at least one(actually it's exactly one in this case) possibility to accept the string, this fit the definition of NPDA which says a string is said to be accepted by an NPDA if there is at least one path that leads to the \tt ACCEPT
  Another example with a subtle difference is \text{EVENPALINDROME}, abbr. \mathcal{P_e}, it is a language of all palindromes with even length:

\mathcal{P_e}=\lbrace x\text{ concatenated with }reverse(x) \text{ for } x\in (\boldsymbol{a}+\boldsymbol{b})^\ast \rbrace

this one can be implemented by using same idea, the read of each letter involves two possibilities about treat this letter as part of the first half or the second half of the string, if it is in the first part, we push it onto the stack, if it's the second part, we pops a character from stack and check if they're identical, the whole NPDA can be depicted as:

there might be a lot of possibilities that will lead a string in \mathcal{P_e} to \tt REJECT, but there do exist at least one possibility that leads the string to \tt ACCEPT, so this NPDA accepts \mathcal{P_e}

Formal definition of Pushdown Automata

  A pushdown automata, abbr. PDA, is a collection of:

  1. An alphabet of input letters denoted by \Sigma
  2. An input tape \tt TAPE with infinitely many cells in one direction, the string is placed onto the tape according to the direction intially, all the left cells are blank
  3. A pushdown stack \tt STACK with infinitely many cells in one direction. Initially, all the cells are blank
  4. An alphabet of characters of \tt STACK denoted by \Gamma
  5. State set Q
  6. Start state q\in Q
  7. Set of accept states F\sube Q
  8. Finite subset \delta of transtions relation Q\times\lbrace \Sigma\cup \Lambda\rbrace\times \Gamma\times Q\times \Gamma^\ast(this actually also implies that each state could have as many labels as they need, which means the machine is nonterministic), this could means that if a (q,a,s,q_0, S)\in\delta, then the PDA is in state q, the topmost character on stack is s, maybe read the current input a, set state to q_0, pop s out of the stack, and push a S onto the stack, the \Sigma\cup\Lambda shows that the PDA could decide to read a letter from input tape or leave the tape alone(for instance, the push or pop operation do not need to read letter)

A string is said to be accepted by a PDA, if there exists a path for that string leads to the \tt ACCEPT, and the \tt STACK must be empty by that time the string reaches the accept state

Theorem 1

For every regular languages L, there exists a PDA accepts it

Proof

  The proof is quite simple, every FA itself is a PDA with a stack untouched, so every regular language that can be accepted by FA can also accepted by PDA

Theorem 2

For every PDA M, there exists a PDA M' accepts the same language while ensures that both \tt STACK and \tt TAPE are blank before reaches the \tt ACCEPT

Proof

  We've about to show how to turn a PDA with redundant characters on \tt TAPE and \tt STACK when accepts string into a PDA without them
  For each \tt ACCEPT

add two extra states before it to consume the letters and characters left on the tape \tt TAPE and stack \tt STACK

and now the PDA will exhausts the tape and stack before it actually turned to \tt ACCEPT state, while recognizing the same language.


乱我心者,今日之日多烦忧