equal
deleted
inserted
replaced
22 // some types abbreviations |
22 // some types abbreviations |
23 type NFAt = NFA[TState, Char] |
23 type NFAt = NFA[TState, Char] |
24 type NFAtrans = (TState, Char) :=> Set[TState] |
24 type NFAtrans = (TState, Char) :=> Set[TState] |
25 type eNFAtrans = (TState, Option[Char]) :=> Set[TState] |
25 type eNFAtrans = (TState, Option[Char]) :=> Set[TState] |
26 |
26 |
27 |
|
28 // for composing an eNFA transition with an NFA transition |
|
29 // | is for set union |
|
30 implicit def nfaOps(f: eNFAtrans) = new { |
|
31 def +++(g: NFAtrans) : eNFAtrans = |
|
32 { case (q, None) => applyOrElse(f, (q, None)) |
|
33 case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c)) } |
|
34 } |
|
35 |
|
36 |
27 |
37 // NFA that does not accept any string |
28 // NFA that does not accept any string |
38 def NFA_ZERO(): NFAt = { |
29 def NFA_ZERO(): NFAt = { |
39 val Q = TState() |
30 val Q = TState() |
40 NFA(Set(Q), { case _ => Set() }, Set()) |
31 NFA(Set(Q), { case _ => Set() }, Set()) |
50 def NFA_CHAR(c: Char) : NFAt = { |
41 def NFA_CHAR(c: Char) : NFAt = { |
51 val Q1 = TState() |
42 val Q1 = TState() |
52 val Q2 = TState() |
43 val Q2 = TState() |
53 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)) |
54 } |
45 } |
|
46 |
|
47 |
|
48 // for composing an eNFA transition with an NFA transition |
|
49 // | is for set union |
|
50 implicit def nfaOps(f: eNFAtrans) = new { |
|
51 def +++(g: NFAtrans) : eNFAtrans = |
|
52 { case (q, None) => applyOrElse(f, (q, None)) |
|
53 case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c)) } |
|
54 } |
|
55 |
55 |
56 |
56 // sequence of two NFAs |
57 // sequence of two NFAs |
57 def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = { |
58 def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = { |
58 val new_delta : eNFAtrans = |
59 val new_delta : eNFAtrans = |
59 { case (q, None) if enfa1.fins(q) => enfa2.starts } |
60 { case (q, None) if enfa1.fins(q) => enfa2.starts } |