Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!agate!ig!uwmcsd1!leah!itsgw!nyser!njin!princeton!phoenix!pucc!EGNILGES From: EGNILGES@pucc.Princeton.EDU (Ed Nilges) Newsgroups: comp.software-eng Subject: Re: Soft-Eng Digest v5n13 Message-ID: <5444@pucc.Princeton.EDU> Date: 9 Jun 88 22:43:23 GMT References: <8806082028.AA14514@pcsc-sun.mitre.org> Reply-To: EGNILGES@pucc.Princeton.EDU Organization: Princeton University, NJ Lines: 77 Disclaimer: Author bears full responsibility for contents of this article In article <8806082028.AA14514@pcsc-sun.mitre.org>, nigam@pcsc-sun (Alok Nigam) writes: > >Date: Mon, 23 May 88 13:32:04 PDT >From: PAAAAAR%CALSTATE.BITNET@CUNYVM.CUNY.EDU >Subject: Gotos and Finite State Machines > >After all these years we're still discussing that old fourletter word. >Here comes a summary of much stomach chunning ... > "Chunning" is a nice new word, altho "churning" was intended, devil a doubt. > ..... >(6) I am currently modifying some code based on an undocumented and > erroneous Finite State Machine -- ARRRGH > You have my sympathy, but if you replace the string "Finite State Machine", the "ARRRGH" is still valid! This is not the case if you remove "undocumented and erroneous", but leave "Finite State Machine" in the original statement. Put the blame where it belongs! > >(7) A finite state machine is no more or less than a flowchart without > boxes (Ref - Any good text on the theory of Computabillity). No, a finite state machine is an alternative representation of a language of Chomsky type 3. See John E. Hopcroft and Jeffrey D. Ullman's FORMAL LANGUAGES AND THEIR RELATION TO AUTOMATA, Addison- Wesley, 1973, page 33: "Let G = (V(N),V(T),P,S) be a type 3 grammar. Then there exists a finite automaton M = (K,V(T),squiggle,S,F) with T(M) = L(G)" What this means in English is that a language whose syntax rules are of the form A::=aB or A::=a, where A and B are nonterminals (things like "noun" and "verb") and a is a terminal (things like "cat" and "John") can be parsed by a finite state machine which goes only one way on its input tape, can't write on its input tape, and is in one of a number of states. Graphical representations of finite state machines look the the horrible flowchart of yore; but the inability of the finite state automaton to act like a full-scale computer means that these type of "flowcharts" are much more disciplined (and consequently less hard to understand) than flowcharts of programs for real computers (which are Turing machines, much more powerful than finite state automata). For instance, the userid of the original submitter, PAAAAAAR, is a member of the language: ::= R ::= { N.B.: sorry } ::= P ::= A ::= A (the language consisting of PAR, PAAR, PAAAR ....) The work of constructing a automaton for recognizing these strings is left as an exercise for the reader. The fact that the Chomsky (yes, that's Noam Chomsky of the dreaded New York Review of Books in a mathematical, rather than political, incarnation) type 3 language maps so nicely onto finite state auto- mata means that if you acquire a feel for recognizing "languages" where they are type 3 means that you have a useful technique handy, finite state automata, for solving a problem. For example, messages coming over a communications line or the sequence of records in a structured file might form a type 3 language. The technique is most heavily used in the lexical analysis phase of compilers to recognize identifiers and such. I realize that this compressed introduction may be a bit confusing to some. Does anybody out there want to submit a tutorial on automata, languages, and their real-world application to this conference?