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 ExpressionsThree Equivalent RepresentationsSlide 20EXAMPLE 1Finite (State) AutomataFinite AutomatonFinite State AutomataTransition GraphInitial ConfigurationReading the InputSlide 28Slide 29Slide 30Slide 31RejectionSlide 33Slide 34Slide 35Slide 36Another RejectionSlide 38Another ExampleSlide 40Slide 41Slide 42Slide 43Rejection ExampleSlide 45Slide 46Slide 47Slide 48Slide 49Finite AutomataExample FSALanguage accepted by FSAExample:Languages Accepted by FAsSlide 55Slide 56Slide 57Formal DefinitionInput AlphabetSet of StatesInitial StateSet of Accepting StatesTransition FunctionSlide 64Slide 65Slide 66Transition FunctionExtended Transition FunctionSlide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Language Accepted by FAsObservationSlide 78Slide 79Slide 80Deterministic FSA’sSlide 82Example DFSASlide 84Slide 85Slide 86Slide 87Slide 88Slide 89Example NFSASlide 91Slide 92Slide 93Slide 94Slide 95Slide 96Slide 97Slide 98Slide 99Slide 100Slide 101Slide 102How 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}, C*={12n: n=0,1,2,…}If B={0,1}, 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 automataThree Equivalent RepresentationsFinite automataRegularexpressionsRegular languagesEach candescribethe othersKleene’s Theorem: For every regular expression, there is a deterministic finite-state automaton that defines the same language, and vice versa.Regular Expression Regular Grammara*S   | aS(a+b)*S   | aS | bSa* + b*S   | A | BA  a | aAB  b | bBa*bS  b | aSba*S  bAA   | aA(ab)*S   | abSEXAMPLE 1 Consider the language { ambn | m, n  N}, which is represented by the regular expression a*b*. A regular grammar for this language can be written as follows: S  | aS | B B  b | bB.Finite (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