1 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Finite Automata (FA) •  FA also called Finite State Machine (FSM) –  Abstract model of a computing entity. –  Decides whether to accept or reject a string. –  Every regular expression can be represented as a FA and vice versa •  Two types of FAs: –  Non-deterministic (NFA): Has more than one alternative action for the same input symbol. –  Deterministic (DFA): Has at most one action for a given input symbol. •  Example: how do we write a program to recognize the Java keyword “int”? i n t q1 q2 q0 q3 2 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. RE and Finite State Automaton (FA) •  Regular expressions are a declarative way to describe the tokens –  Describes what is a token, but not how to recognize the token •  FAs are used to describe how the token is recognized –  FAs are easy to simulate in a programs •  There is a 1-1 correspondence between FSAs and regular expressions –  A scanner generator (e.g., lex) bridges the gap between regular expressions and FAs. String stream scanner Finite Regular automaton expression program Scanner generator Tokens 3 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Inside scanner generator RE Main components of scanner generation (e.g., Lex) Thompson construction – Convert a regular expression to NFA a non-deterministic finite automaton (NFA) Subset construction – Convert the NFA to a DFA determinstic finite automaton Minimization (DFA) Minimized DFA – Improve the DFA to minimize DFA simulation Scanner the number of states generator – Generate a program in C or some other language to Program “simulate” the DFA 4 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Automata Non-deterministic Finite (FA) •  NFA (Non-deterministic Finite Automaton) is a 5-tuple (S, Σ, δ, S0, F): –  S: a set of states; –  Σ: the symbols of the input alphabet; –  δ : a set of transition functions; »  move(state, symbol)  a set of states –  S0: s0 ∈S, the start state; –  F: F ⊆ S, a set of final or accepting states. •  Non-deterministic -- a state and symbol pair can be mapped to a set of states. •  Finite—the number of states is finite. 5 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Transition Diagram •  FA can be represented using transition diagram. •  Corresponding to FA definition, a transition diagram has: –  States represented by circles; –  An Alphabet (Σ) represented by labels on edges; –  Transitions represented by labeled directed edges between states. The label is the input symbol; –  One Start State shown as having an arrow head; –  One or more Final State(s) represented by double circles. •  Example transition diagram to recognize (a|b)*abb a a b b q1 q2 q0 q3 b 6 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Simple examples of FA a start 0 a 1 a a* start 0 a start a 0 1 a+ a a, b start 0 start (a|b)* 0 b 7 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Procedures for defining a DFA/NFA •  Defining input alphabet and initial state •  Draw the transition diagram •  Check –  Do all states have out-going arcs labeled with all the input symbols (DFA) –  Any missing final states? –  Any duplicate states? –  Can all strings in the language can be accepted? –  Are any strings not in the language accepted? •  Naming all the states •  Defining (S, Σ, δ, q , F) 0 8 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Example of constructing a FA •  Construct a DFA that accepts a language L over the alphabet {0, 1} such that L is the set of all strings with any number of “0”s followed by any number of “1”s. •  Regular expression: 0*1* •  Σ = {0, 1} •  Draw initial state of the transition diagram Start 9 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc. Example of constructing a FA 0 1 •  Draft the transition diagram 0 1 Start •  Is “111” accepted? •  The leftmost state has missed an arc with input “1” 0 1 0 1 Start 1 10 CMSC 331, Some material © 1998 by Addison Wesley Longman, Inc.