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, and underscores, but not containing adjacent underscores 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 j ust above, one might have thefollowing session:% fsasim 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 alphabet 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 n amefinal state n amedenoting 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 sequen ce 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 s tandard 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 equal to that ofc2.4 FSASIM: Finite-State Automata SimulatorChapter 3: Using fsasim 53 Using fsasimTo invoke fsasim from a shell, typefsasim [-v] [--verbose] [--deterministic] [--limit=limit] [inputfile ...]The first inputfile contains the machine description. In the absence of and inputfile, allinput comes from the standard input (which is also denoted by an inputfile of -).The input strings to be tested may either be appended to the FSA d escription, followingthe keyword input, placed in subsequ ent inputfiles, or (if there is at least one inputfile) inthe standard input.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 –deterministic option causes fsasim to reject any non-deterministic machine descrip-tion. The –limit option issues a warning if the machine has more than limit states. The–verbose option causes fsasim to print out various explanatory messages. Finally, -v simplyprints the fsasim version number and exits.6 FSASIM: Finite-State Automata
View Full Document
Unlocking...