NANJING UNIVERSITY Finite Automata What Are They? Vho Needs‘em? An Example:Scoring in Tennis 1
What Are They? Who Needs ‘em? An Example: Scoring in Tennis Finite Automata 1
效绵县 What is a Finite Automaton? A formal system. Remembers only a finite amount of information. Information represented by its state ■ State changes in response to inputs. Rules that tell how the state changes in response to inputs are called transitions. 2
What is a Finite Automaton? ◼ A formal system. ◼ Remembers only a finite amount of information. ◼ Information represented by its state. ◼ State changes in response to inputs. ◼ Rules that tell how the state changes in response to inputs are called transitions. 2
效绵鼎 Why Study Finite Automata? Used for both design and verification of circuits and communication protocols. Used for many text-processing applications. An important component of compilers. Describes simple patterns of events,etc. 3
Why Study Finite Automata? ◼ Used for both design and verification of circuits and communication protocols. ◼ Used for many text-processing applications. ◼ An important component of compilers. ◼ Describes simple patterns of events, etc. 3
效绵鼎 Tennis Like ping-pong,except you are very tiny and stand on the table Match 3-5 sets. ■ Set 6 or more games. 4
Tennis ◼ Like ping-pong, except you are very tiny and stand on the table. ◼ Match = 3-5 sets. ◼ Set = 6 or more games. 4
效绵鼎 Scoring a Game One person serves throughout. ■ To win,you must score at least 4 points. You also must win by at least 2 points. Inputs are s=“server wins point'”ando= 66 opponent wins point..” .5
Scoring a Game ◼ One person serves throughout. ◼ To win, you must score at least 4 points. ◼ You also must win by at least 2 points. ◼ Inputs are s = “server wins point” and o = “opponent wins point.” 5