25 type eNFAtrans = (TState, Option[Char]) :=> Set[TState] |
25 type eNFAtrans = (TState, Option[Char]) :=> Set[TState] |
26 |
26 |
27 |
27 |
28 // NFA that does not accept any string |
28 // NFA that does not accept any string |
29 def NFA_ZERO(): NFAt = { |
29 def NFA_ZERO(): NFAt = { |
30 val Q = TState() |
30 val Q = TSt.next() |
31 NFA(Set(Q), { case _ => Set() }, Set()) |
31 NFA(Set(Q), { case _ => Set() }, Set()) |
32 } |
32 } |
33 |
33 |
34 // NFA that accepts the empty string |
34 // NFA that accepts the empty string |
35 def NFA_ONE() : NFAt = { |
35 def NFA_ONE() : NFAt = { |
36 val Q = TState() |
36 val Q = TSt.next() |
37 NFA(Set(Q), { case _ => Set() }, Set(Q)) |
37 NFA(Set(Q), { case _ => Set() }, Set(Q)) |
38 } |
38 } |
39 |
39 |
40 // NFA that accepts the string "c" |
40 // NFA that accepts the string "c" |
41 def NFA_CHAR(c: Char) : NFAt = { |
41 def NFA_CHAR(c: Char) : NFAt = { |
42 val Q1 = TState() |
42 val Q1 = TSt.next() |
43 val Q2 = TState() |
43 val Q2 = TSt.next() |
44 NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2)) |
44 NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2)) |
45 } |
45 } |
46 |
46 |
47 |
47 |
48 // for composing an eNFA transition with an NFA transition |
48 // for composing an eNFA transition with an NFA transition |
74 NFA(nfa1.starts | nfa2.starts, new_delta, new_fins) |
74 NFA(nfa1.starts | nfa2.starts, new_delta, new_fins) |
75 } |
75 } |
76 |
76 |
77 // star of a NFA |
77 // star of a NFA |
78 def NFA_STAR(nfa: NFAt) : NFAt = { |
78 def NFA_STAR(nfa: NFAt) : NFAt = { |
79 val Q = TState() |
79 val Q = TSt.next() |
80 val new_delta : eNFAtrans = |
80 val new_delta : eNFAtrans = |
81 { case (Q, None) => nfa.starts |
81 { case (Q, None) => nfa.starts |
82 case (q, None) if nfa.fins(q) => Set(Q) } |
82 case (q, None) if nfa.fins(q) => Set(Q) } |
83 |
83 |
84 eNFA(Set(Q), new_delta +++ nfa.delta, Set(Q)) |
84 eNFA(Set(Q), new_delta +++ nfa.delta, Set(Q)) |