FSM Generator

July 11, 2014

A few weeks ago we had an exercise that solved the problem of removing singleton occurrences of a given character from a string while leaving multiple occurrences of the given character intact. Our solution used a finite state machine that iterated over the input string writing output as it went.

The finite state machine used in that solution was hand-crafted to solve the given problem. But it is possible to write a program that takes a definition of a finite state machine and creates a function that takes an input string and applies the finite state machine to it. Such a program isn’t hard to create and provides a useful utility for small parsing problems.

Your task is to write a program that generates a finite state machine from a simple description; the format and capabilities of the machine are up to you, but it should be at least powerful enough to solve the “remove singleton” problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

4 Responses to “FSM Generator”

  1. Paul said

    As there is already a very good FSM for Python written by Noah Spurrier, I did not try to make another one. I give here how the FSM can be used for the remove singleton problem.

    """
    FSM is from Noah Spurrier
    (http://opensource.apple.com/source/lldb/lldb-159/test/pexpect-2.4/FSM.py)
    Also supports FSM memory
    """
    from __future__ import print_function
    
    from prpr.FSM import FSM
    
    def emit(fsm):
        print(fsm.input_symbol, end="")
    
    def secondX(fsm):
        emit(fsm); emit(fsm)
        
    def single(txt, x):
        f = FSM(0)
        f.add_transition     (x,      0,  None    ,       1)
        f.add_transition     (x,      1,  secondX ,       2)
        f.add_transition     (x,      2,  emit    ,       2)
        f.set_default_transition         (emit,           0)
        f.process_list(txt)
    
    single("abcccabcabccabcc", "c")
    # -> abcccababccabcc
    
  2. Mirko said

    In the common-lisp code above, the “output” variable is defined in the inner “let”, but left unused (courtesy of my CLISP). It can be safely commented out.

  3. Mike said

    I don’t think the two-state Mealy machine in the proposed solution will correctly handle 3 or more ‘X’s in a row.
    For example, an input of “XbbXXXbX” yields and output of “bbXXXXb”. I think a third state is needed:
    [pre]
    State 0:
    X -> 1,
    * -> 0,*
    State 1:
    X -> 2,XX
    * -> 0,*
    State 2:
    X -> 2,X
    * -> 0,*
    [/pre]

  4. matthew said

    Mirko: good catch, thanks, I think the program should say “output” instead of the later occurrence of “(cddr actionspec)”

    Mike: also well spotted (and particularly stupid on my part as I seem to have got it right in my solution to the original problem).

    This should be the right thing:

    (defun singleton1 (s)
      (mealy s
             ((0 
               (#\X 1) 
               (nil 0 nil))
              (1 
               (#\X 2 #\X #\X)
               (nil 0 nil))
              (2
               (#\X 2 #\X)
               (nil 0 nil)))))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: