formal-notes/Formal Midterm Review.md

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}