# 2.1 Context-Free & PDA

## The Chomsky Hierarchy

Grammar | Rules | Machine |
---|---|---|

Regular | A -> a or A -> aB | DFA |

Context-free | A -> alpha | PDA |

Context-sensitive | alpha -> beta | Turing Machine with bounded memory |

Arbitrary | / | Turing Machine |

*alpha & beta means combinations of both terminal and non-terminal symbols*

## Ambiguity

A grammar is called **ambiguous** if it produces two different parse trees for the same string.

We can use such hierarchies to disambiguate grammars.

The problem of determining whether a given grammar is ambiguous is undecidable.

## PDA

+stack

### Transition Notation

Notation | Means |
---|---|

a,b|cb | on input a with b on top of the stack, push c (on top of b) |

a,b|c | on input a with b on top of the stack, pop the stack and push c |

a,b| | on input a with b on top of the stack, pop the stack |

ID Analysis: (State, remained input, stuffs on the stack)

from top of the stack to the bottom: from left to right

## PDA <=> Context-Free Grammar

### Context-Free Grammar => PDA

construct a PDA that has only one state Q accepted by empty stack

- begin:
- for :
- for terminal symbol a:

this PDA just use epsilon to push the rule to the stack, cancel out corresponding chars and do it over and over again until both the stack and the string are empty

### PDA => Context-Free Grammar

Chomsky is a f**king genius.

construct a huge grammar between any possible states