DEMO : "FST" a Hypercard stack implementing a Türing Machine

Q: What is a transducer, anyway?

Answer: A type of FSA which is able to record what it is doing (i.e. is able to record the states it passes through).

A dictionary definition (WWW Webster):

trans.duc.er \tran(t)s-'d(y)u:-s*r, tranz-\ n [L transducere to lead across, fr. trans- + ducere to lead m more at TOW : a device that is actuated by power from one system and supplies power in any other form to a second system (as a telephone receiver that is actuated by electric power and supplies acoustic power to the surrounding air)

In computer science:

A "six-tuple" (V,X,l,d,S,F) where:

V

the set of states

X

the alphabet

l

the "labelling relation"

d

the "transition relation"

S

the set of start states

F

the set of end states

DEMO : Regular Expressions in PERL

• Preamble about programming...
  • Relax: we are just looking right now!
  • Distinguish Vodoo vs. Stuff you need to know
  • Try to understand the causal link between the statements in the program and the behavior of the program.
  • Understand that there are many ways to do the same thing, and that the computer is the final arbitrator of what is "right" (with caveats!)

• Basic structure of most programs:

  Get ready to do something: "Initialization", "Prologue"
  Do something: "Main process"
  Cleanup and get out: "Termination"  "EOF processing"
  

• Basic structure of the program we're using today:

  PROLOGUE:
           Specify some things about the PERL environment
           Open a file of text to process
           Get an expression to look for from user
  
  PROCESS:  
           read each line
           check for pattern
           print line and part of line which matches pattern
  
  TERMINATION: 
           Finish up (stop the program)
  

Two-level Phonology

"...phonological alternations are treated as direct correspondences between the underlying (or lexical) representation of words and their realization on the surface level." Example from English orthography spies = spy + -s (plural allomorph)

    Lexical Representation:   ` s p y + 0 s
    Surface Representation:   0 s p i 0 e s

(i.e. there are two tapes...one for each representation. As the transducer moves along one tape, it creates the other...

Rules must be written to account for the special correspondences `:0, y:i, +:0, and 0:e. For example, the two-level rule for the y:i correspondence looks like this (somewhat simplified):

          y:i => @:C___+:0

1. a rules file, which specifies the alphabet and the phonological (or spelling) rules, and

2. a lexicon file, which lists lexical items (words and morphemes) and their glosses, and encodes morphotactic constraints.

Main components of PC-KIMMO

           +-----------+        +-----------+
           |  RULES    |        |  LEXICON  |
           +----+------+        +------+----+
                |-------+      +-------|
                        |      |
                        v      v
    Surface Form:  +------------------+      Lexical Form:
     spies ------->|    Recognizer    |----> `spy+s
                   +----+-------------+      [N(spy)+PLURAL]
                        |
                        v
                   +------------------+
     spies <-------|    Generator     |<----- `spy+s
                   +------------------+

          |@ y + @
          |C i 0 @
        --+-------
        1:|2 0 1 1
        2:|2 3 2 1
        3.|0 0 1 0

DEMO: Morphological Parsing of English Words using PC-KIMMO

DEMO: Part of Speech tagging using KTagger