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.