CS 3100 -- Models of Computation -- Fall 2010

August 26, 2010

• Review Ch1Slides.pdf
  
  
• Do you follow these?
  • Tape, 'tape head', accepting state, rejecting state
  • State
  • Transition
  • Alphabet
    • What is the alphabet for Morse Code?
    • How do you recognize ``SOS''
    • Recall S = ... O = --- and of course E = .
    • So how do you tell apart from S and three Es?
    • So what is really the alphabet?!
• Writing practice: Write these mathematically
  • Empty string
  • Empty set
  • Set containining empty string
  • Set containining empty set
  • Set containining an empty string and an empty set (now, why would you do that?!)
  • String containing an empty set (Groan! Can you do this?)
  • Union of set {a} and itself
  • The result of inserting a and b into {a}
• So can you model a tic-tac-toe game as an FA (a DFA)?
  • Symbols
  • Alphabet
  • States
  • Transitions
  • Transition table
  • Accept states
  
  
  
• Repeat above exercise for Chess and then your favorite card game
  
  
• Discuss Homework 1
  
  
• Finish-up on the problem
  
  L_any3hastwo1s = { all  strings  over  {0,1}   |   block_condition }
  
  where
  
  block_condition = every block of three consecutive symbols has at least two 1s
  
  
• Approaches to DFA construction
  • Premature optimization is bad
  • Later you'll be using tools to build and optimize (minimize)
  • Later you'll be using NFA to arrive at a DFA (``FA'') faster
  • Some DFA WILL be exponential no matter what!
  • That said, some tricks do work ofte

• Got terrible automaton without optimization
• Used minimization tool to get better machine
• Then said ``aha, look back is bad'' ; keep state = ``seen so far''
• That worked well!
• Need something better!
  • Consider ``Nth last symbol must be a 0'' Þ FA has size 2^N
  • Reverse of this guy is great and small!
  • ORDER IN WHICH YOU FEED INFO TO A DFA MAKES ALL THE DIFFERENCE!!!!!
  • Error-correcting DFA
  • Error-free case for 01001
  • All one-bit errors over 01001 Þ Groan! DFA is UGLY
  • NFA will make BOTH THESE problems simpler than baby-food
  • regular expressions -- your door-way to tell a computer what NFA you want !!
  
  
  
• How I used regular expressions to process your email using sed
  
  
• History of Alan Turing http://www.turing.org.uk/turing/
  
  
• DFA for predicting the onset of Epileptic seizures! See paper DFA-to-predict-epileptic-seizures.pdf in class dir.

This document was translated from L^AT_EX by H^EV^EA.