diff -r 14a348d050b3 -r 084e2843f478 progs/display/thompson2.scala --- a/progs/display/thompson2.scala Tue Jul 21 00:12:34 2020 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,43 +0,0 @@ -// Thompson Construction (Part 2) - -// some more type abbreviations -type NFAtrans = (TState, Char) :=> Set[TState] -type eNFAtrans = (TState, Option[Char]) :=> Set[TState] - - -// for composing an eNFA transition with a NFA transition -implicit class RichPF(val f: eNFAtrans) extends AnyVal { - def +++(g: NFAtrans) : eNFAtrans = - { case (q, None) => applyOrElse(f, (q, None)) - case (q, Some(c)) => - applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c)) } -} - -// sequence of two NFAs -def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = { - val new_delta : eNFAtrans = - { case (q, None) if enfa1.fins(q) => enfa2.starts } - - eNFA(enfa1.starts, new_delta +++ enfa1.delta +++ enfa2.delta, - enfa2.fins) -} - -// alternative of two NFAs -def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = { - val new_delta : NFAtrans = { - case (q, c) => applyOrElse(enfa1.delta, (q, c)) | - applyOrElse(enfa2.delta, (q, c)) } - val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q) - - NFA(enfa1.starts | enfa2.starts, new_delta, new_fins) -} - -// star of a NFA -def NFA_STAR(enfa: NFAt) : NFAt = { - val Q = TState() - val new_delta : eNFAtrans = - { case (Q, None) => enfa.starts - case (q, None) if enfa.fins(q) => Set(Q) } - - eNFA(Set(Q), new_delta +++ enfa.delta, Set(Q)) -}