EGNILGES@pucc.Princeton.EDU (Ed Nilges) (06/10/88)
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: <userid> ::= <userid_head>R <userid_head> ::= <peeee><sigh> { N.B.: sorry } <peeee> ::= P <sigh> ::= A <sigh> ::= <sigh>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?
daveb@geac.UUCP (David Collier-Brown) (06/13/88)
| In article <8806082028.AA14514@pcsc-sun.mitre.org>, nigam@pcsc-sun (Alok Nigam) writes: | (6) I am currently modifying some code based on an undocumented and | erroneous Finite State Machine -- ARRRGH In article <5444@pucc.Princeton.EDU> EGNILGES@pucc.Princeton.EDU writes: | You have my sympathy, but if you replace the string "Finite State | Machine", the "ARRRGH" is still valid! For mere humans, there is a good FSA compiler in the Kermit distribution, called "wart". Use of it makes 1) the notation a fair bit easier to follow, and 2) the ugly generated/required code irrelevant. I have an upgraded version, available by mail for anyone with a C compiler. Please note that Wart does not have to genrate C: FORTRAN II would probably be ok. You need a C compiler to compile Wart itself. A short description follows: WART(1) NAME wart -- a dfa compiler SYNOPSIS wart [file] DESCRIPTION Wart is a program which takes a yacc-like file of code and directives and generates a c program from it. The directives define a deterministic finite automaton (DFA), and are primarily for producing protocol engines, such as are used by C-Kermit. The format of the file is: lines to be copied %states <list of state names> %events <list of event names> %% event { block of code to be executed } ... <state[,state]> event { block of code to be executed } <state> event { more code... } ... %% more lines to be copied Wart therefor implements a small subset of the Unix 'lex' lexical analyzer generator. Unlike lex, wart may be distributed without requirement for a Unix license. Wart is intended for production of state table switch- ers. It allows a set of states to be defined, along with a function for getting input, and a table of state transi- tions. A C program is generated which performs actions and switches states based on the current state and the input. [...] HISTORY Wart was written by Jeff Damens of the Columbia Center for Computing Activities, November, 1985, to facilitate development of Unix Kermit. It was updated by David Brown of Tesseract Technologies in February, 1986. The program is Copyright (C) 1985, the Trustees of Columbia University in the City of New York. The earlier version assumed that the event would be a single ascii character, and did not support the "%events" directive. 5 -- David Collier-Brown. {mnetor yunexus utgpu}!geac!daveb Geac Computers Ltd., | "His Majesty made you a major 350 Steelcase Road, | because he believed you would Markham, Ontario. | know when not to obey his orders"
jbush@ficc.UUCP (james bush) (06/22/88)
In article <5444@pucc.Princeton.EDU>, EGNILGES@pucc.Princeton.EDU (Ed Nilges) writes: > ... [discussion on finite state machines] > 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? I once maintained and used a couple of finite state machines acting as real-time user-input processing systems. The technique resulted in very flexable and easy-to-add-to code. -- James Bush, Ferranti, Houston Praise the Lord Internal address: jbush extension 5230, mail stop A/3204, room A/3602 External address: ..!uunet!nuchat!sugar!ficc!jbush