Wrap-up of automata theory:

Finite State Machines (deterministic and non-deterministic)

- -regular expressions: terminals and concatenation, alternative, Kleen Star -FSMs are closed under Union, Intersection, and Complement
- Union: guess which one to run Intersection: build cross product FSM. Complements are aquired by making it deterministic, add fail transitions, and reverse the accept/reject states

Accept DFA (Deterministic Finite Automata) = Given a DFAF + astring W, does F accept W? AcceptNFA can reduce to the DFA. EmptyDFA Does DFA F accept any strings (can do by flooding)

- Empty? (F union G) (complementG) union (F)

Equivelent- Do DFAs F&G accept some language? Push Down Automata

- - Context free Grammars: Nonterminal³ nonterminals or terminals or (epsilon)

Turing Machines:

-Grammars: can be created using nonterminals & terminals ³ Nonterminals and terminals

Linear Bounded Automata: Ontecs Sensitive, Grammars, |Lft Side| < |Right Side< With CFGs the terminals are set by the rules and don¡¦t dissappear. With Grammars, the terminals are only determined by the input string and can be changed

- (0/1 or general language, deterministic/ non-deterministic, semi-infinate or infinite tape, 1 or more tapes, 1 or more heads, 1D or 2D¡K)

Decidision: Prolems: computaoi

Accpet PDA: is decidable Empty PDA is decidable

Every FSM is recognizable by Push-Down Automata

Turing machingi= and pk I can write a TM that takes as an input, that takes as an input M-descrippiol, W- input to that T, M It what M would do on W?

Z+ |1, 2, ...(\n) Z |0, 1, -1, 2, -2,¡K (\n) Q or Z2 |¡K (\n)

Each list means the same thing as they can be mapped to each other

R proof by contradiction:

- Assume countable and make a list I will construct w (an element in) R Show that w isn¡¦t on the list

(Diagonalism) If nth digit of nth # is 3, nth digit of w is 7. Otherwise, nth digit of w is 3

There are a countable number of Turing machines: (there exists) countably many TMs. 1. 0 2. 1 3. 00 4. 01 5. 10 6. 11 2n strings of n (if continued); these are an ordered list of finite strings of arbitrary length. Check syntax and cross out the ones that aren¡¦t TMs.

For a language, say 0*1*, you can create a bit string stating whether the binary list from above is following that language. (111101) ³This means that if I could count languages, I could define a language not on the list. But I can¡¦t.

Halt(M,w)

- Yes if TM M runs on w nd stops No if TM M infinite loops or just doesn¡¦t stop.

Why isn¡¦t running Univ. Machine the answer?

- Because running M on Mw+ might not stop

Proof by contradiction: Assume Halt exists. Build Halt¡¦(M)=Halt(M, M) Now build P(M)={run Halt¡¦ on M=Halt(M, M)

- If yes, return no If no, return yes}

P(P)?=(not)Halt¡¦(P1)= not( Halt(P,P))

Church Turing: Any model of effective computation will resort to a Turing Machine.