Deterministic Finite Automata

Write a program that accepts a description with lines of the form:  state symbol next_state, which defines the DFA's transition rules, and an input string. 

The first word in the description shall correspond to the starting state.  All transition states shall start with a lowercase letter and all accepting states shall start with an uppercase letter.  The program will print `1' if the input string ends on an accepting state and print `0' if otherwise.  If a symbol in the input string is not included in the description (i.e. not in it's ``alphabet''), then the program will print `0'.

Begin!


import sys

class DFA:
        def __init__(self, file):
                description = self.__listify__(file)

                self.sigma = set([j for (i,j,k) in description])
                self.alpha = [((i,j),k) for (i,j,k) in description]
                self.final = set([i for (i,j,k) in description if i[0].isupper()])
                self.state = description[0][0]

                self.accept = 1

        def __listify__(self, file):
                return [tuple(line.strip('\n').split()) for line in file]

        def __transition__(self, symbol):
                for (oldstate,newstate) in self.alpha:
                        if (self.state,symbol) == oldstate:
                                self.state = newstate
                                break

        def tapewalk(self, tape):
                for symbol in tape:
                        if not (symbol in self.sigma):
                                self.accept = 0
                                break
                        self.__transition__(symbol)

                self.accept = 1 if self.accept and self.state in self.final else 0
                print self.accept

def main():

        if len(sys.argv) != 3:
                sys.stderr.write('usage: DFA_sim DFA_desc_file string')
                sys.exit(0)

        descfile   = open(sys.argv[1])
        input      = sys.argv[2]
        automation = DFA(descfile)

        automation.tapewalk(input)

if __name__ == "__main__":
        main()

ONE WORD THE FORCED INDENTATION OF CODE THREAD OVER

>>1
Dude, __foo__ is only for magic methods, your private methods are supposed to be __foo

>>3
Thank you.  I'll be aware of that from now on.  I hope this doesn't anger Guido.

Deterministic
BO-RING

{-# LANGUAGE PostfixOperators #-}
import Data.Char (isUpper)

type State = String
type Symbol = String
data DFA = Automaton {
           state :: State,
           states :: [(State, Symbol, State)] }
         | Invalid
          deriving (Show, Eq)

buildAutomaton input = Automaton initial dict
  where dict = map (mkTuple . words) $ lines input
        initial = (\(x,y,z) -> x) $ head dict
        mkTuple [x, y, z] = (x, y, z)
        mkTuple _ = error "Invalid description."

(?) Invalid = False
(?) (Automaton s _) = isUpper $ head s

Invalid << _ = Invalid
(Automaton c states) << (s:ss) = invoke rule << ss
  where rule = filter f states
        f = (\(x,y,z) -> and [x == c, y == s])
        invoke [(_, _, new)] = Automaton new states
        invoke _ = Invalid

evaluate automaton input = (automaton << input ?)

Not as ELEGANT AS FUCK as I wanted it to be, though.
Also, OP, you should always post some test input too.

>>6
Apologies.  Here's how mine worked:

$ cat description
q0 0 q3
q0 1 q1
q1 0 q0
q1 1 Q2
Q2 0 Q2
Q2 1 Q2
q3 0 Q4
q3 1 q0
Q4 0 Q4
Q4 1 Q4

$ python DFA_sim.py description 00001
1

$ python DFA_sim.py description 01010
0

$ python DFA_sim.py description 01001010haxmyanus
0

9 Name: Anonymous 2011-02-03 0:43

Don't change these.

Name:		Email:
Entire Thread Thread List

All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -