FSASIM: A Simulator for Finite-State AutomataP. N. HilfingerChapter 1: Overview 11 OverviewThe fsasim program reads in a description of a finite-state recognizer (either deterministicor non-deterministic), and a sequence of strings. It reports which strings are recognized.For example, here is a description of a (deterministic) FSR for the language describedby the regular expression ‘(01)*00’:alphabet [01]start state Begin[0] -> Zerostate Zero[0] -> Done[1] -> Beginfinal state DoneThe alphabet declaration describes the alphabet used by the machine, in the format usedby the lex program to denote a pattern that matches one of a set of sin gle characters.The start state, state, and final state declarations introduce new states. Use startstate to introduce the initial state (by default, the first state declared). Use final stateto introd uce a final state.The lines containing -> denote transitions out of the last state declared. Each transi-tion has the f orm of a character-set pattern as in lex followed by an arrow, followed by adestination state.Here is another example, this time for Ada identifiers, which start with a letter, followedby letters, digits, an d underscores, but not containing adjacent und erscores and not endingwith an underscore:alphabet [a-zA-Z0-9_]start state 0[a-zA-Z] -> 1final state 1[a-zA-Z0-9] -> 1[_] -> 2state 2[^_] -> 1As in lex, the notation ‘[^...]’ u sed under state 2 means “any character in the alphabetother than. . . .”Here is an example of a non-deterministic machine’s description.# Recognizer for 0 (01)*1|(0|1)*0alphabet [01]start state A[0] -> B[01] -> A[0] -> Cfinal state Cstate B[0] -> B1[1] -> D2 FSASIM: Finite-State Automata Simulatorstate B1[1] -> Bfinal state DThe following alternative machine description recognizes the same language, and uses epsilontransitions.# Recognizer for 0 (01)*1|(0|1)*0alphabet [01]start state Init-> A1 # Epsilon transition-> B1 # Epsilon transitionstate A1[0] -> A2[1] -> A1state A2-> F-> A1state B1[0] -> B2state B2-> B4[0] -> B3state B3[1] -> B2state B4[1] -> Ffinal state FAfter reading in the machine description, fsasim will process any number of quoted inputstrings from a file or the standard input. For the machine just above, one might have thefollowing session:% fsasim -f desc.fsm sample.inp"" rejected."001010" accepted."001011" accepted."110001" rejected."110000" accepted.where ‘sample.inp ’ contains"""001010""001011""110001""110000"Chapter 2: FSA Descriptions 32 FSA DescriptionsFSA descriptions are in free format; that is, you may insert additional whitespace(blanks, tabs, newlines) freely except in the middle of keywords or charsets (describedbelow). You may also insert comments between declarations (but not within them). Acomment starts with the character ‘#’ and proceeds to the end of the line.An FSA description has the following format• An optional alphabet declaration of the formalphabet charset(See the description of charsets below). If this declaration is absent, the alphab et istaken to consist of all characters between blank and delete (i.e., between ASCII codes32 and 127), inclusive.• Any number of state declarations, consisting of− A header line having one of the three formsstate namestart state namefinal state namedenoting a state labeled name that is, respectively, an ordinary state, the startingstate (there should be only one), or a final state (of which there may be anynumber). The label name may be any sequence of letters, digits, periods, hyphens,underscores, and dollar signs.− Zero or more transition d eclarations having one of the two formatscharset -> state-> stateDenoting, respectively, a transition on any of the characters in charset or an epsilontransition.CharsetsOrdinary transitions and the alphabet declaration use charsets to describe sets of char-acters. These consist of a sequence of characters or character ranges surrounded in squarebraces ([]). If the first ch aracter is ‘^’, the charset denotes the complement of the characterset s pecified by the remaining characters, relative to the declared alphabet (this form maynot be used in the alphabet declaration itself). You may use any characters in a charset,but to include the special characters ‘]’, ‘\’, ‘^’, or ‘-’, you should precede them with abackslash (‘\’). You can use the standard C escape characters for tabs, newlines, returns,etc.You may denote a range of characters as ‘c1-c2’, which is the same as listing all char-acters whose codes are greater than or equal to that of c1 and less than or equ al to that ofc2.4 FSASIM: Finite-State Automata SimulatorChapter 3: Using fsasim 53 Using fsasimTo invoke fsasim from a shell, typefsasim [-v] [-V] [ -d] [-l limit] [-f descfile] [inputfile]The optional descfile argument indicates the file containing the FSA description to be u s ed .It defaults to inp utfile.The input strings to be tested may either be appended to the FSA description, followingthe keyword input, or placed in the file inputfile, which defaults to the standard input.When the -f option is not used, the input strings always follow the FSA after the keywordinput.Each input string is surrounded in double quotes. Any embedded doub le quotes mustbe preceded by a backslash (‘\’). You may also use the usual C/C++ conventions for specialcharacters (e.g., ‘\n’ for newline). You m ay optionally use whitespace to separate inputstrings.The -d option causes fsasim to reject any non-deterministic machine description. The -loption issues a warning if the machine has more than limit states. The -V option causesfsasim to print out various explanatory messages. Finally, -v simply prints the fsasim versionnumber and exits.6 FSASIM: Finite-State Automata
View Full Document
Unlocking...