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
效绵 Server s Wins 40-Love s Ad-in 30-Love 0 s 40-15 0 0 s 0 Start 15-Love 30-15 40-30 s s 0 0 0 Love 15-all 30-all deuce 0 s S 0 15-30 30-40 Love-15 S 0 0 0 s Love-30 15-40 0 Ad-out Love-40 0 0 Opp'nt Wins 6
6 Love Start Love -15 15 -Love so Love -30 15 -all 30 -Love s s o o Love -40 15 -30 30 -15 40 -Love sssooo Server Wins Opp ’nt Wins so 40 -15 15 -40 30 -all sssooo 30 -40 40 -30 ss so oo deuce s s o o Ad -out Ad -inso so so
效绵鼎 Acceptance of Inputs Given a sequence of inputs (input string )start in the start state and follow the transition from each symbol in turn. Input is accepted if you wind up in a final (accepting)state after all inputs have been read. 7
Acceptance of Inputs ◼ Given a sequence of inputs (input string ), start in the start state and follow the transition from each symbol in turn. ◼ Input is accepted if you wind up in a final (accepting) state after all inputs have been read. 7
效绵 Example:Processing a String oSOSOSOSOSS Server Wins 40-Love Ad-in 30-Love 40-15 0 Start 15-Love 0 0 30-15 40-30 0 0 0 Love 15-al0 30-al deuce 米 Love-15 15-30 30-40 0 Love-30 0 15-40 Love-40 Ad-out Q Opp'nt 8 Wins
Example: Processing a String 8 Love Start Love-15 15-Love s o Love-30 15-all 30-Love s s o o Love-40 15-30 30-15 40-Love s s s o o o Server Wins Opp’nt Wins s o 40-15 15-40 30-all s s s o o o 30-40 40-30 s s s o o o deuce s s o o Ad-out Ad-in s o s o s o s o s o s o s o s o s s *
效绵 Example:Processing a String SOSOSOSOSOSS Server Wins 40-Love Ad-in 30-Love 0 米 40-15) 0 Start 15-Love 0 0 30-15 40-30 S 0 0 0 Love 15-al0 30-al deuce Love-15 15-30 30-40 0 Love-30 0 15-40 Love-40 Ad-out Q Opp'nt 9 Wins
Example: Processing a String 9 Love Start Love-15 15-Love s o Love-30 15-all 30-Love s s o o Love-40 15-30 30-15 40-Love s s s o o o Server Wins Opp’nt Wins s o 40-15 15-40 30-all s s s o o o 30-40 40-30 s s s o o o deuce s s o o Ad-out Ad-in s o s o s o s o s o s o s o s o s s *
效绵 Example:Processing a String SOSOsOsOsOss Server Wins 40-Love Ad-in 30-Love 0 40-15 0 Start 15-Love 0 0 30-15 40-30 S 米 0 0 0 Love 15-all 30-al deuce Love-15 15-30 30-40 0 Love-30 0 15-40 Love-40 Ad-out Q Opp'nt .10 Wins
Example: Processing a String 10 Love Start Love-15 15-Love s o Love-30 15-all 30-Love s s o o Love-40 15-30 30-15 40-Love s s s o o o Server Wins Opp’nt Wins s o 40-15 15-40 30-all s s s o o o 30-40 40-30 s s s o o o deuce s s o o Ad-out Ad-in s o s o s o s o s o s o s o s o s s *