#!/usr/bin/env python3 """ fns2dfa.py 0.2 Usage: nfa2dfa.py Read an NFA (in graphviz format) and convert it to a DFA. Note that this is a hack - it depends on specific conventions in graphviz! Options: -h --help Print this help. -d --dot Print a description of the automaton in the Graphviz language suitable for processing with dot to get a graphical representation of the automaton. -p --print Print back the automaton in tabular form. Copyright 2014-2024 Stephan Schulz, schulz@eprover.org This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program ; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA The original copyright holder can be contacted as Stephan Schulz DHBW Stuttgart Informatik Postfach 10 05 63 D-70004 Stuttgart Germany or via email (address above). """ import sys import re import getopt from pylib_dfa import DFA start_re = re.compile("dummy_x23z *-> *([A-Za-z0-9]+)") trans_re = re.compile(r"([A-Za-z0-9]+) *-> *([A-Za-z0-9]+) *\[label *= *([^]]*)\]") accept_re = re.compile(r"node \[shape = doublecircle\];") naccept_re = re.compile("node") state_re = re.compile(r"([A-Za-z0-9]+) *(\[label *= *[^]]*\]);") class NFA(object): """ Object representing a (non-deterministic) finite automaton. """ def __init__(self): self.states = set() self.sigma = [] self.delta = set() self.start = None self.accept = set() def add_state(self, state): self.states.add(state) def set_accepting(self, state): self.states.add(state) self.accept.add(state) def set_start(self, state): # Will overwrite previous start state, if any self.states.add(state) self.start = state def add_trans(self, fr, char, to): self.states.add(fr) self.states.add(to) if not char in self.sigma: self.sigma.append(char) self.delta.add((fr, char, to)) def delta_rel(self, state, char): return [t[2] for t in self.delta if (t[0]==state and t[1]==char)] def delta_star(self, state, char): res = set() for s in self.delta_rel(state, char): res.update(self.epsilon_closure(s)) return res def Delta(self, states, char): res = set() for s in states: res.update(self.delta_star(s, char)) return res def delta_rel_str(self, state, char): return "{"+",".join(self.delta_rel(state, char))+"}" def comp_epsilon_closure(self, state, closure): if state in closure: return closure closure.add(state) for s in self.delta_rel(state, ""): self.comp_epsilon_closure(s, closure) return closure def epsilon_closure(self, state): return self.comp_epsilon_closure(state, set()) def __str__(self): res = list() sigma = sorted(self.sigma) l1 = " | "+" ".join(["%15s"%(i,) for i in sigma]) res.append(l1) l2 = "-"*(len(l1)+1) res.append(l2) for i in sorted(self.states): if i == self.start: start = "->" else: start = " " if i in self.accept: accept = "*" else: accept = " " xstate = "%2s %1s %3s | " %(start, accept, i) d = " ".join(["%15s"%(self.delta_rel_str(i, c),) for c in sigma]) l = xstate + d res.append(l) return "\n".join(res) def parse_gv(self, str): lines = str.split("\n") accepting = False for line in lines: mo = accept_re.search(line) if mo: # print "Accept" accepting = True else: mo = naccept_re.search(line) if mo: # print "Non-Accept" accepting = False mo = state_re.search(line) if mo: # print "Found state", mo.groups()[0] if accepting: self.set_accepting(mo.groups()[0]) mo = start_re.search(line) if mo: # print "Start state is", mo.groups()[0] self.set_start(mo.groups()[0]) else: #3 print "Scanning line", line mo = trans_re.search(line) if mo: # print "Found" fr = mo.groups()[0] to = mo.groups()[1] transstr = mo.groups()[2].strip("\"") chars = transstr.split(",") for c in chars: c=c.strip() char = "" # print c if c != "<ε>" and c != 'ε': char = c # print "Transition %s -- %s -> %s"% (fr, char, to) self.add_trans(fr, char, to) def make_det(self): dfa = DFA() states = {} sigma = [l for l in self.sigma if l != ""] S0 = frozenset(self.epsilon_closure(self.start)) states[S0] = "S0" dfa.set_start("S0") print("# S0 =", S0) worklist =[ ("S0", S0) ] state_counter = 1 while worklist: item = worklist.pop(0) name, state = item for l in sigma: newstate = frozenset(self.Delta(state, l)) print("# Delta(%s, %s) = "%(name,l), newstate) if not newstate in states: newname = "S%d"% (state_counter,) state_counter += 1 states[newstate] = newname worklist.append((newname, newstate)) print("#", newname, " = ", newstate) if newstate.intersection(self.accept): dfa.set_accepting(newname) else: print("# State is equal to ", states[newstate]) newname = states[newstate] dfa.add_trans(name, l, newname) return dfa dot = False prt = False if __name__ == '__main__': opts, args = getopt.gnu_getopt(sys.argv[1:], "hdp", ["help", "dot", "print"]) for option, optarg in opts: if option in ["-h", "--help"]: print(__doc__) sys.exit() elif option in ["-d", "--dot"]: dot = True elif option in ["-p", "--print"]: prt = True else: sys.exit("Unknown option "+ option) if len(args)<1: print(__doc__) sys.exit() file = open(args[0], "r") str = file.read() file.close() na = NFA() na.parse_gv(str) # print na dfa = na.make_det() if prt: print(dfa) if dot: print(dfa.dotify())