nfa_to_dfa.py

# -*- coding: utf-8 -*-
"""NFA_To_DFA.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1z2lr8--9hYPoLuGCOUfTwex9yeWVnDOd
"""

EPSION= 'ESP'

from graphviz import Digraph
def vizualize_NFA(NFA):

  #gra = Digraph(graph_attr={'landscape':'True'})
  gra = Digraph(graph_attr={'rankdir':'LR'})


  #construct nodes first
  for stat in NFA:

     if "startingState" in stat:
        continue
     for key, value in NFA[stat].items():
        if key == 'isTerminatingState':
          if value==True:
            gra.node(stat, _attributes={'peripheries' : '2'})
          else:
            gra.node(stat)

  #for each node, construct edges
  for stat in NFA:
      if "startingState" in stat:

        continue
      for edg,values in NFA[stat].items():
          if(edg !="isTerminatingState"):
            if(isinstance(values,list)):
              for value in values:
                gra.edge(stat, value, edg)
            else:
                gra.edge(stat, values, edg)
  gra.node('', shape='none')
  gra.edge('',NFA['startingState'], label='Start')
  gra.format = 'png'
  gra.render('NFA', view = True)
  return

from typing import List, Tuple
from enum import Enum
class RegexErrors(Enum):
    SUCCESS = 0
    UNALLOWED_CHAR = 1
    INVALID_DASH = 2
    INVALID_BRACKETS = 3
    INVALID_OR = 4
    INVALID_INITIAL = 5
    EMPTY_BRACKET = 6


def is_valid_dash(s:str,i:int) -> bool:
    if (s[i - 1].isalnum() and s[i + 1].isalnum()):
        return True
    return False

def is_valid_bar(s:str,i:int) -> bool:
    if (s[i - 1].isalnum() or s[i-1] == ')'or s[i+1] == ']') and (s[i + 1].isalnum() or s[i+1] == '(' or s[i+1] == '[' ):
        return True
    return False

def is_allowed_char (ch: str, allowed_non_alnum: Tuple[str, ...]) -> bool:
    if ch not in allowed_non_alnum and not (ch.isalnum()):
        return False
    return True

def is_empty_bracket(s:str,i) -> bool:
    if (s[i] == '[' and s[i+1] == ']' or s[i] == '(' and s[i+1] == ')' ):
        return True
    return False


def is_valid_first_char(s:str) -> bool:
    if (not (is_allowed_char(s[0],allowed_non_alnum))):
        return RegexErrors.UNALLOWED_CHAR
    # if (not (s[0].isalnum() or s[0] =='(' )):


def is_valid_regex(s: str, allowed_non_alnum: Tuple[str, ...]) -> RegexErrors:
    stack: List[str] = []
    stack_square_brackets: List[str] = []
    brackets_map: dict[str, str] = {')': '(',}
    square_brackets_map: dict[str, str] = {']': '['}
    last_index = len(s) - 1
    #hardcoding 1st iteration due to index error from dashing
    if not is_allowed_char(s[0], allowed_non_alnum):
        return RegexErrors.UNALLOWED_CHAR
    elif not (s[0].isalnum() or s[0] =='(' or s[0] == '['):
        return RegexErrors.INVALID_INITIAL
    if s[0] in brackets_map.values():
        if is_empty_bracket(s,0):
            return RegexErrors.EMPTY_BRACKET
        stack.append(s[0])
    elif s[0] in square_brackets_map.values():
        if is_empty_bracket(s,0):
            return RegexErrors.EMPTY_BRACKET
        stack_square_brackets.append(s[0])
    #Looping through the rest of the string
    for i, char in enumerate(s[1:last_index], start=1):
        if not (is_allowed_char(char,allowed_non_alnum)):
            return RegexErrors.UNALLOWED_CHAR
        if char == '-' and (not is_valid_dash(s,i) or not stack_square_brackets):
            return RegexErrors.INVALID_DASH
        elif char == '|' and not is_valid_bar(s,i):
            return RegexErrors.INVALID_OR
        elif char in brackets_map.values():
            if stack_square_brackets:
                return RegexErrors.INVALID_BRACKETS
            if is_empty_bracket(s,i):
                return RegexErrors.EMPTY_BRACKET
            stack.append(char)
        elif char in square_brackets_map.values():
            if is_empty_bracket(s,i):
                return RegexErrors.EMPTY_BRACKET
            stack_square_brackets.append(char)
        elif char in brackets_map.keys():
            if not stack or brackets_map[char] != stack.pop():
                return RegexErrors.INVALID_BRACKETS
        elif char in square_brackets_map.keys():
            if not stack_square_brackets or square_brackets_map[char] != stack_square_brackets.pop():
                return RegexErrors.INVALID_BRACKETS
    #hardcoding last iteration due to index error from dashing
    if s[-1] == '|':
        return RegexErrors.INVALID_OR
    if s[-1] not in allowed_non_alnum and not (s[-1].isalnum()):
            return RegexErrors.UNALLOWED_CHAR
    if s[-1] in brackets_map.values():
        return RegexErrors.INVALID_BRACKETS
    elif s[-1] in brackets_map.keys():
        if not stack or brackets_map[s[-1]] != stack.pop():
            return RegexErrors.INVALID_BRACKETS
    if (stack or stack_square_brackets):
      return RegexErrors.INVALID_BRACKETS
    return RegexErrors.SUCCESS
    # return RegexErrors.SUCCESS if not (stack or stack_square_brackets)  else RegexErrors.INVALID_BRACKETS

from typing import Dict, Union
import json

class Node:
    state_id_counter: int = 1  # Static data member to calculate state_id

    def __init__(self, is_start: bool = False, is_end: bool = False):
        self.is_start: bool = is_start
        self.is_end: bool = is_end
        self.state_id: str = f"S{Node.state_id_counter}"  # State ID for the node
        Node.state_id_counter += 1
        self.connections: Dict[str, Union[int, list]] = {}  # Dictionary to store connections to other nodes

    def add_connection(self, to_node, action_value: str) -> None:
        if action_value in self.connections:
            # If action already exists, append the new destination node to the existing one
            existing_destination = self.connections[action_value]
            if isinstance(existing_destination, list):
                existing_destination.append(to_node.state_id)
            else:
                self.connections[action_value] = [existing_destination, to_node.state_id]
        else:
            self.connections[action_value] = to_node.state_id

    def to_dict(self) -> dict:
        connections_dict = {}
        for action, destination in self.connections.items():
            connections_dict[str(action)] = destination
        state_dict = {
                "isTerminatingState": self.is_end,
        }
        state_dict.update(connections_dict)
        return state_dict


    def remove_connection(self, action_value: str) -> None:
        if action_value in self.connections:
            del self.connections[action_value]
        else:
            print("Connection with action value {} does not exist.".format(action_value))

class Graph:
    def __init__(self):
        self.nodes: List[Node] = []

    def add_node(self, node: Node) -> None:
        self.nodes.append(node)
    def to_dict(self):
        return {
            node.state_id: node.to_dict() for node in self.nodes
        }

global_graph: Graph = Graph()

class Token:
    def __init__(self, start_node: Node = None, end_node: Node = None):
        self.start_node: Node = start_node
        self.end_node: Node = end_node
    def to_dict(self):
        return {
            'startingState': self.start_node.state_id
        }

def construct_literal(token: Token, action: str) -> Token:
    new_node: Node = Node(is_end=True)
    global_graph.add_node(new_node)
    token.end_node.add_connection(new_node, action_value=action)
    token.end_node.is_end = False
    token.end_node = new_node
    return token

def construct_literal_optional(token: Token) -> Token:
    new_start: Node = Node(is_start=True)
    global_graph.add_node(new_start)
    new_start.add_connection(token.start_node, 'ESP')
    token.start_node.is_start = False
    token.start_node = new_start
    new_end_node: Node = Node(is_end=True)
    global_graph.add_node(new_end_node)
    token.end_node.add_connection(new_end_node, 'ESP')
    token.end_node.is_end = False
    token.end_node = new_end_node
    token.start_node.add_connection(token.end_node, 'ESP')
    return token

def construct_literal_kleene_star(token: Token) -> Token:
    new_start: Node = Node(is_start=True)
    global_graph.add_node(new_start)
    new_start.add_connection(token.start_node, 'ESP')
    token.start_node.is_start = False
    token.start_node = new_start #line 1-5/part 1, highlighted in red
    token.end_node.add_connection(new_start, 'ESP') #line 6/part 2, highlighted in green
    new_end_node: Node = Node(is_end=True)
    global_graph.add_node(new_end_node)
    token.end_node.add_connection(new_end_node, 'ESP')
    token.end_node.is_end = False
    token.end_node = new_end_node
    token.start_node.add_connection(token.end_node, 'ESP')
    return token

def construct_literal_kleene_plus(token: Token) -> Token:
    new_start: Node = Node(is_start=True)
    global_graph.add_node(new_start)
    new_start.add_connection(token.start_node, 'ESP')
    token.start_node.is_start = False
    token.start_node = new_start
    token.end_node.add_connection(new_start, 'ESP')
    return token

def construct_base(base: str) -> Token:
    start_node: Node = Node(is_start=True)
    global_graph.add_node(start_node)
    end_node: Node = Node(is_end=True)
    global_graph.add_node(end_node)
    token: Token = Token(start_node=start_node, end_node=end_node)
    start_node.add_connection(end_node, base)
    return token

def add_quantifier(token: Token, ch: str) -> Tuple[Token,bool]:
    has_quantifier = True
    if(ch == '?'):
       token = construct_literal_optional(token=token)
    elif(ch == '*'):
       token = construct_literal_kleene_star(token=token)
    elif(ch == '+'):
        token = construct_literal_kleene_plus(token=token)
    else:
        has_quantifier = False
    return token,has_quantifier
def and_tokens(token1: Token, token2: Token) -> Token:
    token1.end_node.add_connection(token2.start_node,'ESP')
    token1.end_node = token2.end_node
    token2.start_node.is_start = False
    token1.end_node.is_end = False
    token2.end_node.is_end = True
    return token1

def or_tokens(token1: Token, token2: Token) -> Token:
    new_start_node: Node = Node(is_start=True)
    global_graph.add_node(new_start_node)
    new_start_node.add_connection(token1.start_node, 'ESP')
    new_start_node.add_connection(token2.start_node, 'ESP')
    token1.start_node.is_start = False
    token2.start_node.is_start = False
    token1.start_node = new_start_node
    new_end_node: Node = Node(is_end=True)
    global_graph.add_node(new_end_node)
    token1.end_node.add_connection(new_end_node, 'ESP')
    token2.end_node.add_connection(new_end_node, 'ESP')
    token1.end_node.is_end = False
    token2.end_node.is_end = False
    token1.end_node = new_end_node
    return token1

def construct_token(s: str) -> Token:
    start_node = Node(is_start=True)
    global_graph.add_node(start_node)
    end_node = start_node
    token = Token(start_node=start_node,end_node=end_node)
    index = 0  # Initialize index variable
    nesting = False
    while index < len(s):
        if s[index] == '(':
            nesting = True
            count = 1
            base = ""
            for index2, char2 in enumerate(s[index + 1:], start=index + 1):
              if char2 == '(':
                count += 1
              if char2 == ')':
                  count -= 1
                  if count == 0:
                      index = index2 + 1
                      break
              base += char2
        elif s[index] == '[':
            base = "["
            for index2, char2 in enumerate(s[index + 1:], start=index + 1):
                if char2 == ']':
                    index = index2 + 1  # Move index to the next character after ']'
                    base+= char2
                    break
                base += char2
        else:
            base = s[index]
            index += 1  # Move index to the next character
        #Now we have the base, we need to check if there is a quantifier
        #if nesting is false then I'm sure the string inside base doesnt need any nesting and can be passed to construct_quantified_base
        if (nesting):
            #if there is nesting then I need to essentially construct a new token with the string inside the brackets
            new_token = construct_token(base)
            if (index !=  len(s) ):
                #there might be a quantifier after the closing bracket
                has_quantifer = False
                if (index != len(s) ):
                    new_token, has_quantifer = add_quantifier(new_token,s[index])
                #if there is a quantifier then I need to increment index
                if (has_quantifer): index += 1
        else:
            #I pass s[index] because it is the char right after the char/range of chars that determine whether the base needs a quantifier or not
            new_token = construct_base(base)
            has_quantifer = False
            if(index != len(s)):
                new_token, has_quantifer = add_quantifier(new_token,s[index])
            if (has_quantifer): index += 1
            #Since the base has a quantifier, I need to check index+1 to see if there is a '|' or not
        while index != len(s) and s[index] == '|':
            #If there is a '|' then I need to find operand 2 before I can join operand 1 and operand 2
            new_token_right = Token()
            index += 1
            #Well I got 3 cases for the right token/operand. It could be a single character, a range of characters or a nested token
            #So I need to check if the next character is a bracket or not
            #If it is a bracket then I need to find the closing bracket and pass the string inside the brackets to construct_token
            nesting2 = False
            if s[index] == '(':
                nesting2 = True
                count2 = 1
                base = ""
                for index2, char2 in enumerate(s[index + 1:], start=index + 1):
                    if char2 == '(':
                      count2 += 1
                    if char2 == ')':
                        count2 -= 1
                        if count2 == 0:
                          index = index2 + 1  # Move index to the next character after ')'
                          break
                    base += char2
            elif s[index] == '[':
                base = "["
                for index2, char2 in enumerate(s[index + 1:], start=index + 1):
                    if char2 == ']':
                        index = index2 + 1  # Move index to the next character after ']'
                        base+= char2
                        break
                    base += char2
            else:
                base = s[index]
                index += 1
            if (nesting2):
                new_token_right = construct_token(base)
                if (index !=  len(s) ):
                    new_token_right, has_quantifer = add_quantifier(new_token_right,s[index])
                    if (has_quantifer): index += 1
            else:
                new_token_right = construct_base(base)
                has_quantifer = False
                if(index != len(s) ):
                    new_token_right, has_quantifer = add_quantifier(new_token_right,s[index])
                if (has_quantifer): index += 1
            new_token = or_tokens(new_token,new_token_right)
        token = and_tokens(token,new_token)
    return token

def correct_token(token: Token) -> Token:
    for node in global_graph.nodes:
            node.is_end = False
    token.end_node.is_end = True
    graph_dict = global_graph.to_dict()
    token_dict = token.to_dict() #this returns a dictionary containing only the start state
    token_dict.update(graph_dict)
    return token_dict

def part1_assignment(s:str, allowed_non_alnum: Tuple[str, ...]) -> dict:
    valid = is_valid_regex(s, allowed_non_alnum)
    if valid == RegexErrors.SUCCESS:
        print("Valid")
    else:
        raise ValueError(f"Invalid regex due to {valid}")
    token: Token = construct_token(s)
    token_dict: dict = correct_token(token)
    with open("NFA.json", "w") as json_file:
        json.dump(token_dict, json_file)

    return token_dict
# Example usage:
# global_graph = Graph()
# s:str = input()
# allowed_non_alnum: Tuple[str, ...] = ('[', ']', '(', ')', '.', '|', '?', '*', '+','-')
# token_dict = part1_assignment(s, allowed_non_alnum)

"""flow of code
    1-convert json into data structure
    2-helper function to closure of node
    3-transantions table
todo list
    1-coverting json => Done
    2-Get Closure    => Done
    3-Define DFA     => Done
    4-algorithm   


Check List in json    
"""

from tokenize import String
import json

def getClosure(startState, states):
    closure = []
    closure.append(startState)
   #print(startState)
   #print(states)
    isAddedToClosure=True
    while isAddedToClosure:
        isAddedToClosure=False
        for item in closure:


            for key , value in states[item].items():
                if key== EPSION:
                    if(isinstance(value,list)):
                        for valuetemp in value:
                          if valuetemp not in closure:
                             closure.append(valuetemp)
                             isAddedToClosure=True;
                    else:
                      if value not in closure:
                        closure.append(value)
                        isAddedToClosure=True;


    return closure

def applyingFilter(json_data):
    for key, value in list(json_data.items()):  # Create a copy of the dictionary for iteration
        if key == 'startingState':
            continue
        for key2, value2 in list(value.items()):  # Create a copy of the dictionary for iteration
            if key2[0] == '[':
                for i in range(len(key2)):
                    if key2[i] == '-':
                        for j in range(ord(key2[i-1]), ord(key2[i+1])+1):

                            if chr(j) in value and value[chr(j)]==value2  :

                                value.pop(chr(j))


    return json_data

class DFA:
    def __init__(self):
        self.startState = None
        self.acceptStates = []
        self.States = []
        self.transitions = {}

class Min_DFA:
    def __init__(self):
        self.startState = None
        self.acceptStates = []
        self.States = []
        self.transitions = {}

def CreatingDFA(DFA):
  st = []
  st.append(DFA.startState)

  while st:
      transMap = {}
      mainState = st.pop()
      mainState.sort()
      if mainState not in DFA.States:
          DFA.States.append(mainState)
      isAccept = False
      for item in mainState:
          for key, value in states[item].items():
              if key == "isTerminatingState" and value == True:
                  isAccept = True
              if key != "isTerminatingState" and key !=EPSION:
                  if key not in transMap:
                      transMap[key] = []
                  #Check here if the value is a list or a single value
                  if isinstance(value,list):
                      for i in value:
                        transMap[key].append(i)
                        value2.extend(getClosure(i, states))
                  else:
                    transMap[key].append(value)
                    value2 = getClosure(value, states)
                  for Closureitem in value2:
                      transMap[key].append(Closureitem)
      if isAccept == True and mainState not in DFA.acceptStates:
          DFA.acceptStates.append(mainState)
      # Remove duplicates from each list in transMap
      for key in transMap:
          transMap[key] = list(set(transMap[key]))
          transMap[key].sort()
          if transMap[key] not in DFA.States:
              DFA.States.append(transMap[key])
              st.append(transMap[key])
          if tuple(mainState) not in DFA.transitions:
                  DFA.transitions[tuple(mainState)] = {}

          DFA.transitions[tuple(mainState)][key] = transMap[key]
  #print("DFA States:", DFA.States)
  #print("DFA Transitions:", DFA.transitions)
  anotherMap = {}
  count = 0
  for item in DFA.States:
      anotherMap[tuple(item)] = 'S' + str(count)
      count += 1
  DFA.startState = anotherMap[tuple(DFA.startState)]
  # Convert DFA.States
  for i in range(len(DFA.States)):
      DFA.States[i] = anotherMap[tuple(DFA.States[i])]

  # Convert DFA.acceptStates
  for i in range(len(DFA.acceptStates)):
      DFA.acceptStates[i] = anotherMap[tuple(DFA.acceptStates[i])]

  # Convert DFA.transitions
  new_transitions = {}
  for key, value in DFA.transitions.items():
      new_key = anotherMap[tuple(key)]
      new_value = {k: anotherMap[tuple(v)] for k, v in value.items()}
      new_transitions[new_key] = new_value
  DFA.transitions = new_transitions

#convert DFA to JSON


# Create a dictionary that represents the DFA
def ConvertDFAtoJSON(DFA):
  dfa_dict = {
      "startingState": DFA.startState,
  }

  # Add states to the dictionary
  for state in DFA.States:
      dfa_dict[state] = {
          "isTerminatingState": state in DFA.acceptStates,
      }
      # Add transitions for each state
      if state in DFA.transitions:
          for symbol, nextState in DFA.transitions[state].items():
              dfa_dict[state][symbol] = nextState

  # Convert the dictionary to a JSON string
  dfa_json = json.dumps(dfa_dict, indent=4)
  # Specify the file path
  file_path = '/content/NFA_To_DFA.json'

  # Open the file in write mode
  with open(file_path, 'w') as f:
      # Write the JSON string to the file
      f.write(dfa_json)
  dat2 = json.load(open('/content/NFA_To_DFA.json'))
  #dat2=applyingFilter(dat2)
  DFAstates = {key: value for key, value in dat2.items() if key != 'startingState'}
  return DFAstates
#print(dfa_json)

def CreatingMinDFA(Min_DFA,DFA,DFAstates):
  dfa_acceptStates = DFA.acceptStates
  dfa_rejectStates=[]
  dfa_state_to_min_dfa_state = {}
  for state in DFA.States:
      if state not in dfa_acceptStates:
        dfa_rejectStates.append(state)
        dfa_state_to_min_dfa_state[state] = dfa_rejectStates
      else:
          dfa_state_to_min_dfa_state[state] = dfa_acceptStates
  #2 bags created
  min_dfa_states = [dfa_acceptStates, dfa_rejectStates]

  flag=True
  while flag:
      flag=False
      for bag in min_dfa_states[:]:  # Create a copy for iteration
          if(len(bag)>1):
              split_map = []
              temp_map = {}
              for state in bag:
                  transsitions_map={}
                  for key, value in DFAstates[state].items():
                      if key != 'isTerminatingState':
                          if value not in transsitions_map:
                              transsitions_map[key] = []
                          transsitions_map[key].append(value)
                  if transsitions_map not in split_map:
                      split_map.append(transsitions_map)
                      temp_map[state] = [split_map.index(transsitions_map)]  # Make it a list
                  else:
                      if state not in temp_map:
                          temp_map[state] = []
                      temp_map[state].append(split_map.index(transsitions_map))  # Use append instead of add
              if len(split_map)>1:
                  flag=True
                  temp_map2 = {}
                  for key,value in temp_map.items():  # Iterate over items, not the dictionary itself
                      if tuple(value) not in temp_map2:
                          temp_map2[tuple(value)] = []
                      temp_map2[tuple(value)].append(key)
                  for value in temp_map2.values():  # Iterate over the values, not the keys
                      min_dfa_states.append(value)
                      for state in value:
                          dfa_state_to_min_dfa_state[state] = value
                  min_dfa_states.remove(bag)
  #print(min_dfa_states)
  #print(dfa_state_to_min_dfa_state)
  Min_DFA.startState = dfa_state_to_min_dfa_state[DFA.startState]




  anotherMap2 = {}
  count2 = 0
  for key,value in dfa_state_to_min_dfa_state.items():
      if tuple(value) not in anotherMap2:
          anotherMap2[tuple(value)] = 'S' + str(count2)
          count2 += 1

  Min_DFA.startState=anotherMap2[tuple(Min_DFA.startState)]
  for state in DFA.acceptStates:
      Min_DFA.acceptStates.append(anotherMap2[tuple(dfa_state_to_min_dfa_state[state])])

  for item in dfa_state_to_min_dfa_state:
      if anotherMap2[tuple(dfa_state_to_min_dfa_state[item])] not in Min_DFA.States:
          Min_DFA.States.append(anotherMap2[tuple(dfa_state_to_min_dfa_state[item])])


  # # Convert DFA.transitions
  new_transitions2 = {}
  for key, value in DFA.transitions.items():
      new_key = anotherMap2[tuple(dfa_state_to_min_dfa_state[key])]
      new_value = {}  # Initialize an empty dictionary
      for k, v in value.items():
          tuple_key = tuple(dfa_state_to_min_dfa_state[v])
          anotherMap2_value = anotherMap2[tuple_key]
          new_value[k] = anotherMap2_value
      new_transitions2[new_key] = new_value
  Min_DFA.transitions = new_transitions2

  #print(new_transitions2)

# Create a dictionary that represents the DFA
def MinDFAToJson(Min_DFA):
  dfa_dict2 = {
      "startingState": Min_DFA.startState,
  }

  # Add states to the dictionary
  for state in Min_DFA.States:
      dfa_dict2[state] = {
          "isTerminatingState": state in Min_DFA.acceptStates,
      }
      # Add transitions for each state
      if state in Min_DFA.transitions:
          for symbol, nextState in Min_DFA.transitions[state].items():
              dfa_dict2[state][symbol] = nextState

  # Convert the dictionary to a JSON string
  dfa_json2 = json.dumps(dfa_dict2, indent=4)
  # Specify the file path
  file_path = '/content/DFA.json'

  # Open the file in write mode
  with open(file_path, 'w') as f:
      # Write the JSON string to the file
      f.write(dfa_json2)
  dat22 = json.load(open('/content/DFA.json'))
  #dat22=applyingFilter(dat22);
  MinDFAstates = {key: value for key, value in dat22.items() if key != 'startingState'}


  return MinDFAstates

from graphviz import Digraph

def vizualize_DFA(Min_DFA,MinDFAstates):

  #gra = Digraph(graph_attr={'landscape':'True'})
  gra = Digraph(graph_attr={'rankdir':'LR'})


  #construct nodes first
  for stat in Min_DFA.States:
     for key, value in MinDFAstates[stat].items():
        if key == 'isTerminatingState':
          if value==True:
            gra.node(stat, _attributes={'peripheries' : '2'})
          else:
            gra.node(stat)

  #for each node, construct edges
  for stat in Min_DFA.States:
      for edg,value in MinDFAstates[stat].items():
          if(edg !="isTerminatingState"):
            gra.edge(stat, value, edg)

  gra.node('', shape='none')
  gra.edge('',Min_DFA.startState, label='Start')
  gra.format = 'png'
  gra.render('DFA', view = True)
  return

global_graph = Graph()
s:str = input()
allowed_non_alnum: Tuple[str, ...] = ('[', ']', '(', ')', '.', '|', '?', '*', '+','-')
token_dict = part1_assignment(s, allowed_non_alnum)
vizualize_NFA(token_dict)



with open('/content/NFA.json') as f:
    data = json.load(f)

# Print the data
#print(data['startingState'])
startState = data['startingState'];
states = {key: value for key, value in data.items() if key != 'startingState'}

DFA = DFA()
DFA.startState = getClosure(startState, states)
CreatingDFA(DFA)
DFAstates=ConvertDFAtoJSON(DFA)
Min_DFA = Min_DFA()
CreatingMinDFA(Min_DFA,DFA,DFAstates)
MinDFAstates=MinDFAToJson(Min_DFA)
vizualize_DFA(Min_DFA,MinDFAstates)