Transform NFA to DFA with context

nfa2dfa.py

import json
import csv

# Input JSON from Finite State Machine Designer's localStorage['fsm']

name = 'A'
names = [ { 'states': ['Φ'], 'name': 'Z' }]
def get_dfa_name(states):
  global name
  global names
  for item in names:
    if item["states"] == states:
      return item["name"]
  tmp = {"states": states, "name": name}
  names.append(tmp)
  name = chr(ord(name) + 1)
  return tmp['name']

    

def is_final_dfa(state_list):
  for x in state_list:
    for y in ['Y', 'Z']:
      if (x == y):
        return True
  return False

def calc_e_closure(state, state_trans_table):
  closure = dict()
  closure[state] = 0
  closure_stack = [state]
  while(len(closure_stack) > 0):
    cur = closure_stack.pop(0)
    for x in state_trans_table[cur]['\epsilon']:
      if x not in closure.keys():
        closure[x] = 0
        closure_stack.append(x)
    closure[cur] = 1
  return closure.keys()

with open('./fsm_designer.json', 'r', encoding='utf-8') as f:
  data = json.load(f)
  
  #initialize table
  nodes = []
  conditions = set()
  state_trans_table = {}

  for link in data['links']:
    conditions.add(link['text'])
  for node in data['nodes']:
    nodes.append(node['text'])
    state_trans_table[node['text']] = {}
    for c in conditions:
      state_trans_table[node['text']][c] = []

  print("nodes=", nodes)
  print("conditions=", conditions)
  
  for link in data['links']:
    if link['type'] == 'Link':
      state_trans_table[nodes[link['nodeA']]][link['text']].append(nodes[link['nodeB']])
    elif link['type'] == 'SelfLink':
      state_trans_table[nodes[link['node']]][link['text']].append(nodes[link['node']])
  
  #print("state_trans_table=", state_trans_table)
  print(json.dumps(state_trans_table))

  
  fields = [ 'node' ]
  for c in conditions:
    fields.append(c)
  print("fields=", fields)
  
  with open('state_trans_table.csv', 'w', encoding='utf-8') as fcsv:
    w = csv.DictWriter( fcsv, fields )
    w.writeheader()
    for key, val in sorted(state_trans_table.items()):
      row = { 'node': key }
      row.update(val)
      w.writerow(row)

  #求出ε-closure(s)，ε-closure(s)表示由状态s经由条件ε可以到达的 所有状态的集合 
  epsilon_closure = dict()
  for x in nodes:
    epsilon_closure[x] = list(calc_e_closure(x, state_trans_table))
  print("e-closure=", epsilon_closure)
  print("====================================")
  for key, val in sorted(epsilon_closure.items()):
    print("ε-closure(", key, ") = ", val)
  
  #首先将初始态X的转换闭包ε-closure(X)设为状态A
  dfa_stack = list()
  dfa_stack.append(epsilon_closure['X'])
  dfa_states = list()
  dfa_states.append(epsilon_closure['X'])
  edges = []
  print("====================================================")
  print(f"ε-closure(X) = {epsilon_closure['X']} = {get_dfa_name(epsilon_closure['X'])}")
  while (len(dfa_stack) > 0):
    cur_state = dfa_stack.pop(0)
    #print("cur_state:", cur_state)
    for al in conditions:
      if al == '\\epsilon':
        continue
      from_closure = set()
      for x in cur_state:
        from_closure.update(set(state_trans_table[x][al]))
        #print("al:", al, "x:", x, "from_closure:", from_closure)
      if len(from_closure) > 0:
        to_state = set()
        for x in list(from_closure):
          to_state.update(set(epsilon_closure[x]))
        #print("to_state:", to_state)
        if list(to_state) not in dfa_states:
          print(f"ε-closure(move({get_dfa_name(list(cur_state))}, {al})) = {list(to_state)} = {get_dfa_name(list(to_state))}")
          dfa_stack.append(list(to_state))
          dfa_states.append(list(to_state))
        edges.append({ "from": get_dfa_name(list(cur_state)), "to": get_dfa_name(list(to_state)), "label": al, "final": is_final_dfa(list(to_state)) })
      else:
        if (-1) not in dfa_states:
          dfa_states.append(-1)
          for al in conditions:
            if al == '\\epsilon':
              continue
            #edges.append({ "from": get_dfa_name(['Φ']), "to": get_dfa_name(['Φ']), "label": al, "final": False })
        #edges.append({ "from": get_dfa_name(list(cur_state)), "to": get_dfa_name(['Φ']), "label": al, "final": False })

  print("edges:", edges, "\n")
  with open('edges.json', 'w', encoding='utf-8') as edge_f:
    json.dump(edges, edge_f, indent=2)
  print("dfa_names:", names, "\n")