def bigUnion(M):
    return frozenset({ x for A in M for x in A })

bigUnion({ frozenset({1,2,3}), frozenset({2,3,4}), frozenset({3,4,5}) })

"""
Explanation: Converting a Non-Deterministic <span style="font-variant:small-caps;">Fsm</span> into a Deterministic <span style="font-variant:small-caps;">Fsm</span>
In this notebook we show how a non-deterministic <span style="font-variant:small-caps;">Fsm</span>
$$ F = \langle Q, \Sigma, \delta, q_0, A \rangle $$
can be transformed into a deterministic <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$ such that both <span style="font-variant:small-caps;">Fsm</span>s accept the
same language, that is we have
$$ L(F) = L\bigl(\texttt{det}(F)\bigr). $$
The idea behind this transformation is that the <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$ has to 
compute the set of all states that the <span style="font-variant:small-caps;">Fsm</span> $F$ could be in. 
Hence the states of the deterministic <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$ are 
sets of states of the non-deterministic <span style="font-variant:small-caps;">Fsm</span> $F$.  A set of these states contains all those states that the non-deterministic <span style="font-variant:small-caps;">Fsm</span> 
$F$ could have reached.  Furthermore, a set $M$ of states of the <span style="font-variant:small-caps;">Fsm</span> $F$ is an accepting state of the <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$ if the set $M$ contains an accepting state of the <span style="font-variant:small-caps;">Fsm</span> $F$.
<hr style="height:5px;background-color:blue">

In order to present the construction of $\texttt{det}(F)$ we first have to define three auxiliary functions.
We start with the function bigUnion.  Given a set M that contains frozensets, the epression bigUnion(M)
returns the union of all sets in M, i.e. we have
$$ \texttt{bigUnion}(M) = \bigcup M = \bigl{ x \bigm| \exists A \in M: x \in A \bigr}. $$
The resulting set is returned as a frozenset.
End of explanation
"""


def epsClosure(s, delta):
    Result = frozenset({ s })
    while True:
        NewStates = bigUnion({ frozenset(delta.get((q, ''), set())) for q in Result })
        if NewStates <= Result:
            return Result
        Result |= NewStates

"""
Explanation: The function epsClosure takes two arguments:
- s is a state, 
- delta is the transition function of the non-deterministic <span style="font-variant:small-caps;">Fsm</span> $F$.
The function computes the set of all those states that can be reached from the state
s via $\varepsilon$-transitions.
Formally, the set $\texttt{epsClosure}(q)$ is defined inductively:
- $s \in \texttt{epsClosure}(s)$.
- $p \in \texttt{epsClosure}(s) \wedge r \in \delta(p, \varepsilon) \;\rightarrow\; r \in \texttt{epsClosure}(s)$.
If the state $p$ is an element of the $\varepsilon$-closure of the state $s$ 
  and there is an $\varepsilon$-transition from $p$ to some state $r$, then $r$ 
  is also an element of the $\varepsilon$-transition of $s$.
The implementationof epsClosure uses a fixed-point algorithm.
End of explanation
"""


def deltaHat(s, c, delta):
    return bigUnion({ epsClosure(q, delta) for q in delta.get((s, c), set()) })

"""
Explanation: In order to transform a non-deterministic <span style="font-variant:small-caps;">Fsm</span> $F$ into a deterministic 
<span style="font-variant:small-caps;">Fsm</span>
$\texttt{det}(F)$ we have to extend the function $\delta:Q \times \Sigma \rightarrow 2^Q$ into the function
$$\widehat{\delta}: Q \times \Sigma \rightarrow 2^Q. $$
The idea is that given a state $q$ and a character $c$,  the value of $\widehat{\delta}(q,c)$ is the set of all states that the
<span style="font-variant:small-caps;">Fsm</span> $F$ could reach when it reads the character $c$ in state $q$ and then performs an arbitrary number of $\varepsilon$-transitions.  Formally, the definition of $\widehat{\delta}$ is as follows:
$$ \widehat{\delta}(q_1, c) := \bigcup \bigl{ \texttt{epsClosure}(q_2) \bigm| q_2 \in \delta(q_1, c) \bigr }. $$
This formula is to be read as follows:
- For every state $q_2 \in Q$ that can be reached from the state $q_1$ by reading the character $c$ we
  compute $\texttt{epsClosure}(q_2)$.
- Then we take the union of all these sets $\texttt{epsClosure}(q_2)$.
The function $\widehat{\delta}$ is implemented as the function deltaHat, which takes three arguments:
- s is a state,
- c is a character,
- 𝛿 is the transition function of a deterministic 
  <span style="font-variant:small-caps;">Fsm</span>.
This function computes the set of all those states that can be reached 
from s when we first have a transition from state s to some state p 
on reading the character c followed by any number of $\varepsilon$-transitions
starting in p.
End of explanation
"""


def capitalDelta(M, c, delta):
    return bigUnion({ deltaHat(q, c, delta) for q in M })

"""
Explanation: The function  $\widehat{\delta}$ maps a state into a set of states.  Since the <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$ uses sets of states of the <span style="font-variant:small-caps;">Fsm</span> $F$ as its states we need a function that maps sets of states of the <span style="font-variant:small-caps;">Fsm</span> $F$ into sets of states.  Hence we generalize 
the function $\widehat{\delta}$ to the function
$$ \Delta: 2^Q \times \Sigma \rightarrow 2^Q $$
such that for a set $M$ of states and a character $c$ the expression $\Delta(M, c)$
computes the set of all those states that the <span style="font-variant:small-caps;">Fsm</span> $F$ could be in if it is in a state from the set $M$, then
reads the character $c$, and finally makes some $\varepsilon$-transitions.
The formal definition is as follows: 
$$ \Delta(M,c) := \bigcup \bigl{ \widehat{\delta}(q,c) \bigm| q \in M \bigr}. $$
This formula is easy to understand:  For every state  $q \in M$ we compute the set of states that the
<span style="font-variant:small-caps;">Fsm</span> could be in after reading the character $c$ and doing some 
$\varepsilon$-transitions.  Then we take the union of these sets.
End of explanation
"""


def allStates(Q, delta, Sigma):
    Result = { Q }
    while True:
        NewStates = { capitalDelta(M, c, delta) for M in Result 
                                                for c in Sigma 
                    }
        if NewStates <= Result:
            return Result
        Result |= NewStates

"""
Explanation: The function allStates takes three arguments:
- $Q$ is $\texttt{epsClosure}(q_0)$, where $q_0$ is the start state of the deterministic <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$,
- $\delta$ is the transition function of the non-deterministic <span style="font-variant:small-caps;">Fsm</span> $F$, and
- $\Sigma$ is the alphabet of the non-deterministic <span style="font-variant:small-caps;">Fsm</span> $F$.
The function allStates computes the set of all states of the deterministic <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$
that can be reached from the start state.
End of explanation
"""


def nfa2dfa(nfa):
    States, Sigma, delta, q0, Final = nfa
    newStart   = epsClosure(q0, delta)
    NewStates  = allStates(newStart, delta, Sigma)
    newDelta   = { (M, c): capitalDelta(M, c, delta) for M in NewStates
                                                     for c in Sigma
                 }
    NewFinal   = { M for M in NewStates 
                     if  M & Final != set() 
                 }
    return NewStates, Sigma, newDelta, newStart, NewFinal

"""
Explanation: Now we are ready to formally define how the deterministic <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$
is computed from the non-deterministic <span style="font-variant:small-caps;">Fsm</span>
$F = \bigl\langle Q, \Sigma, \delta, q_0, A \bigr\rangle$.
We define: 
$$ \texttt{det}(F) := \bigl\langle \texttt{allStates}(\texttt{epsClosure}(q_0)), \Sigma, \Delta, \texttt{epsClosure}(q_0), \widehat{A} \bigr\rangle $$
where the components of this tuple are given as follows:
- The set of states of $\texttt{det}(F)$ is the set of all states that can be reached from the set $\texttt{epsClosure}(q_0)$.
- The input alphabet $\Sigma$ does not change when going from $F$ to $\texttt{det}(F)$.
  After all, the deterministic <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$ has to recognize the same language as the non-deterministic
  <span style="font-variant:small-caps;">Fsm</span> $F$.
- The function $\Delta$, that has been defined previously, specified how the set of states change when a
  character is read.
- The start state $\texttt{epsClosure}(q_0)$ of the non-deterministic <span style="font-variant:small-caps;">Fsm</span> $\texttt{det}(F)$ is the set of all states
  that can be reached from the start state $q_0$ of the non-deterministic <span style="font-variant:small-caps;">Fsm</span> $F$
  via $\varepsilon$-transitions.
- The set of accepting states $\widehat{A}$ is the set of those subsets of $Q$ that contain an accepting
  state of the <span style="font-variant:small-caps;">Fsm</span> $F$:
  $$\widehat{A} := \bigl{ M \in 2^Q \mid M \cap A \not= {} \bigl}. $$
End of explanation
"""


