Regular LanguagesHow a finite automaton worksThe language of a machineFormal definition of a finite automatonOur automaton formalizedFormal definition of computationDesigning finite automataNFAs (Nondeterministic Finite Automata)Slide 9Formal definition of a nondeterministic finite automatonExampleFormal definition of acceptingWhat language does this NFA recognize?What language does this DFA recognize?Equivalence of NFAs and DFAsThe subset constructionExample of applying the subset constructionThe resulting DFARemoving unreachable statesTesting in workRegular operationsRegular expressionsRegular languagesExercising reading regular expressionsRegular languages and DFA-recognizable languages are the sameThe limitations of the power of DFAsNon-regular languagesA DFA recognizing DRegular LanguagesRegular LanguagesChapter 1 Giorgi Japaridze Theory of ComputabilityHow a finite automaton works1.1.aGiorgi Japaridze Theory of Computabilityq2q0q10001110 1 1 0 0The language of a machine1.1.bGiorgi Japaridze Theory of Computabilityq2q0q1000111L(M), “the language of M”, or “the language recognized by M” --- the set of all strings that the machine M acceptsWhat is the language recognized by our automaton A?Formal definition of a finite automaton 1.1.cGiorgi Japaridze Theory of ComputabilityA (deterministic) finite automaton (DFA) is a 5-tuple (Q, , , s, F), where:Q is a finite set whose elements are called the states is a finite set called the alphabet is a function of the type Q  Q called the transition functions is an element of Q called the start stateF is a subset of Q called the set of accept statesOur automaton formalized1.1.dGiorgi Japaridze Theory of Computabilityq2q0q1000111Q:::s:F: 0 1q0 q1 q2 A = (Q, , , s, F)Formal definition of computation1.1.eGiorgi Japaridze Theory of ComputabilityM = (Q, , , s, F)M accepts the string u1 u2 … un iff there is a sequence r1, r2, …, rn, rn+1 of states such that:• r1=s• ri+1 = (ri,ui), for each i with 1 i  n• rn+1 Fq2q0q1001110 1 1 0 0q0 q2 q0 q0 q2 q1u1 u2 … unr1, r2, …, rn, rn+10Designing finite automata1.1.fGiorgi Japaridze Theory of ComputabilityTask: Design an automaton that accepts a bit string iff it contains an even number of “1”s.NFAs (Nondeterministic Finite Automata)1.2.aGiorgi Japaridze Theory of Computabilityq1q2q30,11 0,10 1 0 1 0q1q1 q2q1 q3q1 q2q1q1 q301010NFAs (Nondeterministic Finite Automata)1.2.aGiorgi Japaridze Theory of Computabilityq1q2q30,11 0,1What language does this NFA recognize?Formal definition of a nondeterministic finite automaton1.2.bGiorgi Japaridze Theory of Computability An NFA is a 5-tuple (Q, , , s, F), where:Q is a finite set whose elements are called the states is a finite set called the alphabet is a function of the type Q  P(Q) called the transition functions is an element of Q called the start stateF is a subset of Q called the set of accept statesExample1.2.cGiorgi Japaridze Theory of ComputabilityQ:::s:F: a b 1 2 3 A = (Q, , , s, F) 3 21aaba,bbFormal definition of accepting1.2.dGiorgi Japaridze Theory of ComputabilityM = (Q, , , s, F)M accepts the string u1 u2 … un iff there is a sequence r1, r2, …, rn, rn+1 of states such that:• r1=s• ri+1 = (ri,ui), for each i with 1 i  n• rn+1 FWhen M is a DFAM accepts the string u1 u2 … un iff there is a sequence r1, r2, …, rn, rn+1 of states such that:• r1=s• ri+1  (ri,ui), for each i with 1 i  n• rn+1 FWhen M is an NFAWhat language does this NFA recognize?1.2.eGiorgi Japaridze Theory of Computability0000000What language does this DFA recognize?1.2.fGiorgi Japaridze Theory of Computability00000005 4321Equivalence of NFAs and DFAs1.2.gGiorgi Japaridze Theory of ComputabilityTwo machines are said to be equivalent if they recognize the same language.Theorem 1.39 Every NFA has an equivalent DFA.Proof. Consider an NFA N = (Q, , , s, F)We need construct an equivalent DFA D = (Q’, , ’, s’, F’)using a procedure called the subset construction described on the next slide.The subset construction1.2.hGiorgi Japaridze Theory of ComputabilityConstructing DFA D = (Q’, , ’, s’, F’) from NFA N = (Q, , , s, F)• Q’ = P (Q)• ’(R,a) = {q | q=(p,a) for some pR} • s’ = {s}• F’= {R | R is a subset of Q containing an accept state of N} D obviously works correctly: at every step in the computation, it clearly enters a state that corresponds to the subset of states that N could be in at that point.Example of applying the subset construction 1.2.iGiorgi Japaridze Theory of ComputabilityQ’::’:s’:F’: a b  {1}{2}{3}{1,2}{1,3}{2,3}{1,2,3} N = (Q,  , , s, F) 3 21aaba,bb•Q’ = P (Q)• ’(R,a) = {q | q=(p,a) for some pR}• s’ = {s}• F’= {R | R is a subset of Q containing an accept state of N}The resulting DFA 1.2.jGiorgi Japaridze Theory of Computability{3}{1}{1,3}{2,3}{1,2}{1,2,3}{2}ba,baabababba,babaDRemoving unreachable states 1.2.kGiorgi Japaridze Theory of Computability{3}{1}{2,3}{1,2,3}ba,baabbabaDTesting in work 1.2.lGiorgi Japaridze Theory of Computability{3}{1}{2,3}{1,2,3}ba,baabbabaD3 21aaba,bbNb a aRegular operations1.3.aGiorgi Japaridze Theory of ComputabilityUnion: L1  L2 = {x | xL1 or xL2} {Good,Bad}  {Boy,Girl} ={0,00,000,…} {1,11,111,…} =L  =Concatenation: L1  L2 = {xy | xL1 and yL2}{Good,Bad}{Boy,Girl} ={0,00,000,…}{1,11,111,…} =L   =Star: L* = {x1…xk | k0 and each xi is in L}{Boy,Girl}* = {0,00,000,…}* = * =Regular expressions1.3.bGiorgi Japaridze Theory of ComputabilityWe say that R is a regular expression (RE) iff R is one of the following:1. a, where a is a symbol of the alphabet2. 3. 4. (R1)(R2), where R1 and R2 are RE5. (R1)  (R2), where R1 and R2 are RE6. (R1)*, where R1 is a REWhat language is represented by the expression:{a}{}The union of the languages represented by R1 and R2The concatenation of the languages represented by R1 and R2The star of the