Some of our key algorithms for NDFAs
Building machines for $\{x\}$, where $x\in\Sigma$,
$\{\lambda\}$, and $\{\ \}$.
| a ∈ Σ Machine |
λ Machine |
∅ Machine |
Input: a ∈ Σ
Output: M = ({q0,q1},Σ,{(q0,a,q1)},q0,{q1})
|
Input: nothing
Output: M = ({q0},Σ,{ },q0,{q0})
|
Input: nothing
Output: M = ({q0},Σ,{ },q0,{ })
|
 |
 |
 |
Building new machines from old machines: union, concatenation,
Kleene Star.
- Algorithm: Union
-
Input: Machines M1 = (Q1,Σ1,Δ1,s1,W1)
and M2 = (Q2,Σ2,Δ2,s2,W2), where
Q1 ∩ Q2 = ∅
Output:
M = (Q1 ∪ Q2 ∪ {s}, Σ1 ∪ Σ2,
Δ1 ∪ Δ2 ∪ {(s,λ,s1),(s,λ,s2)},
s, W1 ∪ W2), where s ∉ Q1 and
s ∉ Q2
(i.e. s is a new state)
- Algorithm: Concatenation
-
Input:
Machines M1 = (Q1,Σ1,Δ1,s1,W1) and
M2 = (Q2,Σ2,Δ2,s2,W2), where
Q1 ∩ Q2 = ∅
Output: Machine
M = (Q1 ∪ Q2, Σ1 ∪ Σ2, Δ,
s1,W2),
where Δ = Δ1 ∪ Δ2 ∪
{(q,λ,s2) | q ∈ W1}
- Algorithm: KleeneStar
-
Input: Machine M = (Q, Σ, Δ, s,
W)
Output: $M' = (Q \cup \{\$\}, \Sigma,
\Delta \cup \{(\$,\lambda,s)\} \cup \{(q,\lambda,\$)\ |\ q \in W\}, \$, \{\$\})$,
where $\$ \notin Q$, i.e. $\$$ is a new state
Convert NDFA to Regular Expression
Algorithm: FA2RE
Input: NDFA $M = (Q,\Sigma,\Delta,s,W)$ such that:
- $Q = \{q_0, ..., q_{n-1}\}$,
- For each $(q_a, x, q_b) \in \Delta$, $q_a \neq q_{n-1}$ and $q_b
\neq q_0$,
- $s = q_0$,
- $W = \{q_{n-1}\}$.
Output:
A regular expression for $L(M)$.
Step 1: For any pair of states $q_j$ and $q_k$ (including when $j = k$), if
there are $m$ arrows with labels $E_{j,k}^1, E_{j,k}^2, ..., E_{j,k}^m$,
then replace them with a single arrow labeled with
$E_{j, k} = (E_{j,k}^1 | E_{j,k}^2 | ... | E_{j,k}^m)$.
Step 2:
for $i = 1, 2, ..., n-2$
do
for every pair of states $q_j$ and $q_k$ (including when $j = k$)
such that there is an arrow from $q_j$ to $q_i$ and an arrow from
$q_i$ to $q_k$:
- if there is no arrow from $q_i$ to $q_i$,
then add an
arrow from $q_j$ to $q_k$ labeled by $E_{j,i} E_{i,k}$.
else (i.e. there is an arrow from $q_i$ to $q_i$), add an
arrow from $q_j$ to $q_k$ labeled by $E_{j,i} (E_{i,i})^*
E_{i,k}$.
- If there are arrows from $q_j$ to $q_k$ with labels
$E_{j,k}^1, E_{j,k}^2, ..., E_{j,k}^m$, replace them by a single
arrow with label $(E_{j,k}^1 | E_{j,k}^2 | ... | E_{j,k}^m)$.
- Remove node $q_i$ and all the arrows going in and out of
it.
Return the only remaining label, namely, $E_{0, n-1}$.
Problem 1
In your groups at the board, try to read through and understand
the above algorithm and apply it to the machine
below.
Note: a big idea behind this algorithm is to
label transitions with regular expressions!
