Finite-State Machines with No Output Longin Jan Latecki Temple UniversityKleene closureSlide 3Regular ExpressionsRecursive DefinitionExamplesLanguages of Regular ExpressionsDefinitionDefinition (continued)ExampleSlide 11Slide 12Slide 13Slide 14Equivalent Regular ExpressionsSlide 16Example: LexingImplementing Regular ExpressionsFinite (State) AutomataFinite AutomatonFinite State AutomataTransition GraphInitial ConfigurationReading the InputSlide 25Slide 26Slide 27Slide 28RejectionSlide 30Slide 31Slide 32Slide 33Another RejectionSlide 35Another ExampleSlide 37Slide 38Slide 39Slide 40Rejection ExampleSlide 42Slide 43Slide 44Slide 45Slide 46Finite AutomataInput AlphabetSet of StatesInitial StateSet of Accepting StatesTransition FunctionSlide 53Slide 54Slide 55Transition FunctionExerciseLanguage accepted by FSAExample:Slide 60Slide 61Slide 62Extended Transition FunctionSlide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Language Accepted by FAsObservationSlide 73Slide 74Slide 75Deterministic FSA’sExample FSAExample DFSASlide 79Slide 80Slide 81Slide 82Slide 83Slide 84Example NFSASlide 86Slide 87Slide 88Slide 89Slide 90Slide 91Slide 92Slide 93Slide 94Slide 95Slide 96Slide 97How to Implement an FSAThe table-driven program for a Deterministic FSAFinite-State Machines with No Output Longin Jan Latecki Temple UniversityBased on Slides by Elsa L Gunter, NJIT,and by Costas BuschKleene closure•A and B are subsets of V*, where V is a vocabularyThe concatenation of A and B isAB={xy: x string in A and y string in B}•Example: A={0, 11} and B={1, 10, 110}AB={01,010,0110,111,1110,11110}•What is BA?•A0={λ}An+1=AnA for n=0,1,2,…Let A be any subset of V*.Kleene closure of A, denoted by A*, is0*kkAAExamples:If C={11}, then C*={12n: n=0,1,2,…}If B={0,1}, then B*=V*.Regular ExpressionsRegular expressions describe regular languages Example: describes the language*)( cba    ,...,,,,,*, bcaabcaabcabcaRecursive Definition,, 112121*rrrrrrAre regular expressionsPrimitive regular expressions:2r1rGiven regular expressions andExamples )(*  ccbaA regular expression: baNot a regular expression:Languages of Regular Expressions : language of regular expressionExample  rLr   ,...,,,,,*)( bcaabcaabcacbaLDefinitionFor primitive regular expressions:       aaLLLDefinition (continued)For regular expressions and 1r2r     2121rLrLrrL      2121rLrLrrL     **11rLrL     11rLrL ExampleRegular expression:  *aba   *abaL     *aLbaL    *aLbaL        *aLbLaL        *aba    ,...,,,, aaaaaaba ,...,,,...,,, baababaaaaaaExampleRegular expression    bbabar  *   ,...,,,,, bbbbaabbaabbarL ExampleRegular expression   bbbaar ** }0,:{22 mnbbarLmnExampleRegular expression*)10(00*)10( r)(rL= { all strings with at least two consecutive 0 }ExampleRegular expression)0(*)011(r)(rL= { all strings without two consecutive 0 }Equivalent Regular Expressions•Definition:• Regular expressions and• are equivalent if 1r2r)()(21rLrL Example L= { all strings without two consecutive 0 } )0(*)011(1r)0(*1)0(**)011*1(2rLrLrL  )()(211r2randare equivalentregular expr.Example: Lexing•Regular expressions good for describing lexemes (words) in a programming language–Identifier = (a  b  …  z  A  B  …  Z) (a  b  …  z  A  B  …  Z  0  1  …  9  _  ‘ )*–Digit = (0  1  …  9)Implementing Regular Expressions•Regular expressions, regular grammars reasonable way to generates strings in language•Not so good for recognizing when a string is in language•Regular expressions: which option to choose, how many repetitions to make•Answer: finite state automataFinite (State) Automata•A FA is similar to a compiler in that: –A compiler recognizes legal programs in some (source) language.–A finite-state machine recognizes legal strings in some language. •Example: Pascal Identifiers–sequences of one or more letters or digits, starting with a letter:letterletter | digitSAFinite Automaton• Input“Accept” or“Reject”StringFiniteAutomatonOutputFinite State Automata•A finite state automation over an alphabet is illustrated by a state diagram:– a directed graph– edges are labeled with elements of alphabet,–some nodes (or states), marked as final–one node marked as start stateTransition Graph initialstate accepting statestatetransition0q1q2q3q4qab ba5qaabbba,ba,Initial Configuration• 1q2q3q4qab ba5qaabbba,Input Stringab baba,0qReading the Input• 0q1q2q3q4qab ba5qaabbba,ab baba,• 0q1q2q3q4qab ba5qaabbba,ab baba,• 0q1q2q3q4qab ba5qaabbba,ab baba,• 0q1q2q3q4qab ba5qaabbba,ab baba,0q1q2q3q4qab baaccept5qaabbba,ab baba,Input finishedRejection• 1q2q3q4qab ba5qaabbba,ababa,0q• 0q1q2q3q4qab ba5qaabbba,ababa,• 0q1q2q3q4qab ba5qaabbba,ababa,• 0q1q2q3q4qab ba5qaabbba,ababa,0q1q2q3q4qab ba5qaabbba,rejectababa,Input finishedAnother Rejection• 1q2q3q4qab ba5qaabbba,ba,0q• 1q2q3q4qab ba5qaabbba,ba,0qrejectAnother Exampleabba,ba,0q1q2qabaabba,ba,0q1q2qabaabba,ba,0q1q2qabaabba,ba,0q1q2qabaabba,ba,0q1q2qabaacceptInput finishedRejection Exampleabba,ba,0q1q2qab babba,ba,0q1q2qab babba,ba,0q1q2qab babba,ba,0q1q2qab babba,ba,0q1q2qab brejectInput finishedFinite State Automata•A finite state automation M=(S,Σ,δ,s0,F) consists of •a finite set S of states, •a finite input alphabet Σ, •a state transition function δ: S x Σ  S, •an initial state s0, •F subset of S that represent the final states.Finite Automata•Transitions1 a s2•Is read ‘In state s1 on input “a” go to state s2’•If end of input–If in accepting state => accept–Otherwise => reject •If no transition possible (got stuck) => reject•FSA = Finite State AutomataInput Alphabet • 0q1q2q3q4qab ba5qaabbba, ba,ba,Set of States • Q0q1q2q3q4qab ba5qaabbba, 543210,,,,, qqqqqqQ ba,Initial State • 0q1q2q3q4qab ba5qaabbba,ba,0qSet of Accepting