NFA to DFA

nfa_to_dfa.py

import deque

def _e_closure(node: Node, result: Set[Node]) -> None:
  if isinstance(Node, (CharNode, EOFNode)):  # si es matcheable
    result.add(node)
    return
  # node deberia ser *, +, |, (, )
  for n in node.out:
    _e_closure(n, result)

def e_closure(node: Node) -> List[Node]:
  ## devuelve el epsilon_closure, los siguientes
  ## nodos que se pueden matchear
  result = set()
  for n in node.out:
    _e_closure(node, result)
  return frozenset(result)

# Ascii
ALPHABET = [chr(c) for c in range(128)]

def n0(nfa: Node) -> Set[Node]:
  return frozenset(e_closure(nfa))

def delta(closure: Set[Node], c: string) -> Set[Node]:
  ## Devuelve el closure con todos los nodos que matchean c
  result = set()
  for n in closure:
    if c == n.char or n is EOF:
      result.add(n)
  return frozenset(result)

def powerset_construction(nfa: Node):
  q0 = n0(nfa)  # closure con los primeros nodos matcheables
  qw = deque()  # queue de closures
  qw.appendleft(q0)
  qs = set()
  qs.add(q0)
  T = {}
  while qw:
    q = qw.pop()
    for c in ALPHABET:
      t = delta(q, c)  # closure que matchea c
      if not t:
        continue
      T[q, c] = t
      if t not in qs:
        qw.appendleft(t)
        qs.add(t)
  return T, q0

def match(text, dfa):
  T, q = dfa
  for c in text:
    if (q, c) not in T:
      return False
    q = T[q, c]
  if EOF not in q:
    return False
  return True