編譯原理教學(xué)課件：lec 3 fa

1、Introduction to Finite AutomataAdapted from the slides of Stanford CS1542Informal ExplanationFinite automata finite collections of states with transition rules that take you from one state to another.Original application sequential switching circuits, where the “state” was the settings of internal b

2、its.Today, several kinds of software can be modeled by FA.3Representing FASimplest representation is often a graph.Nodes = states.Arcs indicate state transitions.Labels on arcs tell what causes the transition.4Example: Recognizing Strings Ending in “ing”nothingSaw iiNot iSaw inggiNot i or gSaw inniN

3、ot i or nStart5Automata to CodeIn C/C+, make a piece of code for each state. This code:Reads the next input.Decides on the next state.Jumps to the beginning of the code for that state.6Example: Automata to Code2: /* i seen */c = getNextInput();if (c = n) goto 3;else if (c = i) goto 2;else goto 1;3:

4、/* ”in” seen */. . .7Deterministic Finite AutomataA formalism for defining languages, consisting of:A finite set of states (Q, typically).An input alphabet (, typically).A transition function (, typically).A start state (q0, in Q, typically).A set of final states (F Q, typically).“Final” and “accept

5、ing” are synonyms.8The Transition FunctionTakes two arguments: a state and an input symbol.(q, a) = the state that the DFA goes to when it is in state q and input a is received.9Graph Representation of DFAs Nodes = states.Arcs represent transition function.Arc from state p to state q labeled by all

6、those input symbols that have transitions from p to q.Arrow labeled “Start” to the start state.Final states indicated by double circles.10Example: Graph of a DFAStart10ACB100,1Previousstring OK,does notend in 1.PreviousString OK,ends in a single 1.Consecutive1s havebeen seen.Accepts all strings with

7、out two consecutive 1s.11Alternative Representation: Transition Table01AABBACCCCRows = statesColumns =input symbolsFinal statesstarred*Arrow forstart state12Extended Transition FunctionWe describe the effect of a string of inputs on a DFA by extending to a state and a string.Induction on length of s

8、tring.Basis: (q, ) = qInduction: (q,wa) = (q,w),a)w is a string; a is an input symbol.13Extended : IntuitionConvention: w, x, y, x are strings.a, b, c, are single symbols.Extended is computed for state q and inputs a1a2an by following a path in the transition graph, starting at q and selecting the a

9、rcs with labels a1, a2,an in turn.14Example: Extended Delta01AABBACCCC(B,011) = (B,01),1) = (B,0),1),1) = (A,1),1) = (B,1) = C15Language of a DFAAutomata of all kinds define languages.If A is an automaton, L(A) is its language.For a DFA A, L(A) is the set of strings labeling paths from the start sta

10、te to a final state.Formally: L(A) = the set of strings w such that (q0, w) is in F.16Example: String in a LanguageStart10ACB100,1String 101 is in the language of the DFA below.Start at A.17Example: String in a LanguageStart10ACB100,1Follow arc labeled 1.String 101 is in the language of the DFA belo

11、w.18Example: String in a LanguageStart10ACB100,1Then arc labeled 0 from current state B.String 101 is in the language of the DFA below.19Example: String in a LanguageStart10ACB100,1Finally arc labeled 1 from current state A. Resultis an accepting state, so 101 is in the language.String 101 is in the

12、 language of the DFA below.20Example ConcludedThe language of our example DFA is:w | w is in 0,1* and w does not havetwo consecutive 1s Read a set former as“The set of strings wSuch thatThese conditionsabout w are true.21Regular LanguagesA language L is regular if it is the language accepted by some

13、 DFA.Note: the DFA must accept only the strings in L, no others.Some languages are not regular.Intuitively, regular languages “cannot count” to arbitrarily high integers.22Example: A Nonregular LanguageL1 = 0n1n | n 1Note: ai is conventional for i as.Thus, 04 = 0000, e.g.Read: “The set of strings co

14、nsisting of n 0s followed by n 1s, such that n is at least 1.Thus, L1 = 01, 0011, 000111,23Another ExampleL2 = w | w in (, )* and w is balanced Note: alphabet consists of the parenthesis symbols ( and ).Balanced parens are those that can appear in an arithmetic expression.E.g.: (), ()(), (), ()(),24

15、But Many Languages are RegularRegular Languages can be described in many ways, e.g., regular expressions.They appear in many contexts and have many useful properties.Example: the strings that represent floating point numbers in your favorite language is a regular language.25NondeterminismA nondeterm

16、inistic finite automaton has the ability to be in several states at once.Transitions from a state on an input symbol can be to any set of states.26Nondeterminism (2)Start in one start state.Accept if any sequence of choices leads to a final state.Intuitively: the NFA always “guesses right.”27Formal

17、NFAA finite set of states, typically Q.An input alphabet, typically .A transition function, typically .A start state in Q, typically q0.A set of final states F Q.28Transition Function of an NFA(q, a) is a set of states.Extend to strings as follows:Basis: (q, ) = qInduction: (q, wa) = the union over

18、all states p in (q, w) of (p, a)29Language of an NFAA string w is accepted by an NFA if (q0, w) contains at least one final state.The language of the NFA is the set of strings it accepts.30Equivalence of DFAs, NFAsA DFA can be turned into an NFA that accepts the same language.If D(q, a) = p, let the

19、 NFA have N(q, a) = p.Then the NFA is always in a set containing exactly one state the state the DFA is in after reading the same input. 31Equivalence (2)Surprisingly, for any NFA there is a DFA that accepts the same language.Proof is the subset construction.The number of states of the DFA can be ex

20、ponential in the number of states of the NFA.Thus, NFAs accept exactly the regular languages.32Subset ConstructionGiven an NFA with states Q, inputs , transition function N, state state q0, and final states F, construct equivalent DFA with:States 2Q (Set of subsets of Q).Inputs .Start state q0.Final states = all those with a member of F.33Subset Construction (2)The transition function D is defined by:D(q1,qk, a) is the union over all i = 1,k of N(qi, a).34Proof of Equivalence: Subset ConstructionShow by induction on |w| thatN(q0, w) = D(q0, w)