# Pumping Lemma

Show $L = \{0^n1^n | n=03 \text{ is not regular}\}$.
Assume $L$ is regular.

Pick a string and some pumping length, $P$.

$s=0^p1^p$

Now show that for any way to divide the string into $xyz$, pumping $s$ results in a string outside of the language.

$xy^2z$ contains symbols out of order, and more 0s than 1s.

# Finite State Machine

A finite automaton is a 5 tuple (Q, $\Sigma$, $\delta$, q, F) where
1) Q is a finite set called the states
2) $\Sigma$ is a finite set called the _alphabet_
3) $\delta = Q \times \Sigma \rightarrow Q$ is the transition function
4) $q \in Q$ is the start state
5) $F \subset Q$ is the set of accept state

# Chomsky Normal Form

Let $G$ be a Context Free Grammar (CFG). $G$ is in Chomsky Normal Form provided that all rules are of the form
1) $A \rightarrow AA$
2) $A \rightarrow u$

The start state cannot appear on the right hand side. Cannot $A \rightarrow \epsilon$ unless start state. 

# NFA that's the union of two languages



# Misc.

$\text{REG} \in \text{CFL}$
but
$\text{REG} \neq \text{CFL}$