53 case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c)) } |
53 case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c)) } |
54 } |
54 } |
55 |
55 |
56 |
56 |
57 // sequence of two NFAs |
57 // sequence of two NFAs |
58 def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = { |
58 def NFA_SEQ(nfa1: NFAt, nfa2: NFAt) : NFAt = { |
59 val new_delta : eNFAtrans = |
59 val new_delta : eNFAtrans = |
60 { case (q, None) if enfa1.fins(q) => enfa2.starts } |
60 { case (q, None) if nfa1.fins(q) => nfa2.starts } |
61 |
61 |
62 eNFA(enfa1.starts, |
62 eNFA(nfa1.starts, |
63 new_delta +++ enfa1.delta +++ enfa2.delta, |
63 new_delta +++ nfa1.delta +++ nfa2.delta, |
64 enfa2.fins) |
64 nfa2.fins) |
65 } |
65 } |
66 |
66 |
67 // alternative of two NFAs |
67 // alternative of two NFAs |
68 def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = { |
68 def NFA_ALT(nfa1: NFAt, nfa2: NFAt) : NFAt = { |
69 val new_delta : NFAtrans = { |
69 val new_delta : NFAtrans = { |
70 case (q, c) => applyOrElse(enfa1.delta, (q, c)) | |
70 case (q, c) => applyOrElse(nfa1.delta, (q, c)) | |
71 applyOrElse(enfa2.delta, (q, c)) } |
71 applyOrElse(nfa2.delta, (q, c)) } |
72 val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q) |
72 val new_fins = (q: TState) => nfa1.fins(q) || nfa2.fins(q) |
73 |
73 |
74 NFA(enfa1.starts | enfa2.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(enfa: NFAt) : NFAt = { |
78 def NFA_STAR(nfa: NFAt) : NFAt = { |
79 val Q = TState() |
79 val Q = TState() |
80 val new_delta : eNFAtrans = |
80 val new_delta : eNFAtrans = |
81 { case (Q, None) => enfa.starts |
81 { case (Q, None) => nfa.starts |
82 case (q, None) if enfa.fins(q) => Set(Q) } |
82 case (q, None) if nfa.fins(q) => Set(Q) } |
83 |
83 |
84 eNFA(Set(Q), new_delta +++ enfa.delta, Set(Q)) |
84 eNFA(Set(Q), new_delta +++ nfa.delta, Set(Q)) |
85 } |
85 } |
86 |
86 |
87 |
87 |
88 // We are now ready to translate regular expressions |
88 // We are now ready to translate regular expressions |
89 // into DFAs (via eNFAs and NFAs, and the subset construction) |
89 // into DFAs (via eNFAs and NFAs, and the subset construction) |