【正文】 tb notb Example ? The set of strings that contain at most one b is accepted by the following DFA: ? (it is simpler than its regular expression ) ? We will omit labels when it is not necessary to refer to the states by name. b notb notb Example ? digit = [09] ? nat = digit+ ? signedNat = (+|)? nat digit digit digit digit digit + digit Example (cont) ? number = signedNat(“.” nat)?(E signedNat)? digit digit + digit digit digit . digit digit + digit E E Example ? {Pascal Comments} ? /* C Comments */ other { } other * / * / other * Actions ? When a transitions is made, the character from the input string is moved to a string that accumulates the characters belonging to a single token (lexeme of the token). ? When an accepting state is reached, the recognized token is returned. ? When an error state is reached, an error token is generated or backtracking is done. Actions Example 1 2 letter letter digit start in_id letter letter digit [other] finish return ID [ ] indicate that the delimiting character should be returned to the input string and not consumed. Uniting DFA’s ? In a typical programming language there are many tokens, and each token is recognized by its own DFA. ? If each token begins with a different character, then it is easy to unite their start states into one start state. – Example: :=, =, = = = return ASSIGN : = return LE return EQ Uniting DFA’s (cont) ? If several tokens begin with the same character, such as , =, and , we must arrange the diagram so that there is a unique transition to be made to each state. – The plexity of such task bees enormous, especially I fit is done in an unsystematic way. = return LE return NE return LT [other] ε transition ? An εtransition is a transition that may occur without consulting the input string (and without consuming any character). ? εtransitions are counterintuitive, they may occur “spontaneously”. ? They can express the choice of alternatives and allow to bine DFA?s. ε Expanding DFA ? Need to include ε in the alphabet: Σ U {ε} ? The value of transition function T is a set of states rather then a single state. – T allows each character lead to more than one state. ? The range of T is the power set of the set of states S (the set of all subsets of S). ? We denote the power set by P (S) Nondeterministic Finite Automation (NFA) ? An NFA M consist of – An alphabet Σ – A set of states S – A transition function T: S x (Σ U {ε}) P (S) – A start state s0 from S – The set of accepting states A from S ? The language accepted my M, written L(M), is the set of strings of characters c1c2…c n with ci from (Σ U {ε}) such that there exist states s1 in T(s0,c1), s2 in T(s1,c2),…, sn in T(sn1,) with sn an element of A. Some Notes ? Any of ci in c1c2…c n may be ε. The string that is actually accepted is the string with the ε?s removed. – The accepted string may actually have fewer than n characters. ? The sequence of states s1s2…s n will not always uniquely defined. ? NFA does not represent an algorithm. It can be simulated by an algorithm that backtracks through every nondeterministic choice. Example ε 4 a 1 2 3 a ε ε b The string abb can be accepted by either of the following sequences of transitions 1 2 4 2 4 1 3 4 2 4 4 This NFA accepts the language of the regular expression ab+|ab*|b* or (a | ε)b* (The paths from A to accepting states ) Example (cont) ? The language generated by (a | ε)b* is accepted by the following DFA: a b b b Implementation of DFA {starting in state 1} if the next character is a letter then advance the input。 {stay in state 2} e