1 // DFAs and NFAs based on Scala's partial functions

     2 

     3 

     4 // edges of the DFAs and NFAs

     5 type Edge[A, C] = PartialFunction[(A, C), A]

     6 

     7 

     8 

     9 

    10 // some states for test cases 

    11 abstract class State

    12 case object Q0 extends State

    13 case object Q1 extends State

    14 case object Q2 extends State

    15 case object Q3 extends State

    16 case object Q4 extends State

    17 case object Q5 extends State

    18 case object Q6 extends State

    19 

    20 

    21 // class for DFAs

    22 case class DFA[A, C](start: A,               // starting state

    23                      trans: Edge[A, C],      // transition

    24                      fins:  A => Boolean) {  // final states

    25 

    26   // given a state and a character, 

    27   // what is the next state, if there is any?

    28   def next(q: A, c: C) : Option[A] = 

    29     trans.lift.apply((q, c))

    30 

    31   // given a state and a string, what is the next state?

    32   def nexts(q: A, s: List[C]) : Option[A] = s match {

    33     case Nil => Some(q)

    34     case c::cs => next(q, c).flatMap(nexts(_, cs))

    35   }

    36 

    37   // is a string accepted by an DFA?

    38   def accepts(s: List[C]) : Boolean = nexts(start, s) match {

    39     case None => false

    40     case Some(q) => fins(q)

    41   }

    42 

    43 }

    44 

    45 // DFA 1

    46 val dtrans1 : Edge[State, Char] = 

    47   { case (Q0, 'a') => Q0 

    48     case (Q0, 'b') => Q1 

    49   }

    50 

    51 val dfa1 = DFA(Q0, dtrans1, Set[State](Q1))

    52 

    53 dfa1.accepts("aaab".toList)     // true

    54 dfa1.accepts("aacb".toList)     // false

    55 

    56 // another DFA test

    57 abstract class S

    58 case object S0 extends S

    59 case object S1 extends S

    60 case object S2 extends S

    61 case object Sink extends S

    62 

    63 // transition function

    64 // S0 --a--> S1 --a--> S2

    65 val sigma : Edge[S, Char] = 

    66   { case (S0, 'a') => S1

    67     case (S1, 'a') => S2

    68     case _ => Sink

    69   }

    70 

    71 val dfa1a = DFA(S0, sigma, Set[S](S2))

    72 

    73 dfa1a.accepts("aa".toList)               //true

    74 dfa1a.accepts("".toList)                 //false

    75 dfa1a.accepts("ab".toList)               //false

    76 

    77 

    78 // class for NFAs

    79 case class NFA[A, C](starts: Set[A],            // starting states

    80                      trans: Set[Edge[A, C]],    // transition edges

    81                      fins:  A => Boolean) {     // final states 

    82 

    83   // given a state and a character, what is the set of next states?

    84   def next(q: A, c: C) : Set[A] = 

    85     trans.flatMap(_.lift.apply((q, c)))

    86 

    87   // given some states and a character, what is the set of next states?

    88   def nexts(qs: Set[A], c: C) : Set[A] = 

    89     qs.flatMap(next(_, c))

    90 

    91   // given some states and a string, what is the set of next states?

    92   def nextss(qs: Set[A], s: List[C]) : Set[A] = s match {

    93     case Nil => qs

    94     case c::cs => nextss(nexts(qs, c), cs)

    95   }

    96 

    97   // is a string accepted by an NFA?

    98   def accepts(s: List[C]) : Boolean = 

    99     nextss(starts, s.toList).exists(fins)

   100 

   101 }

   102 

   103 

   104 

   105 

   106 // NFA test cases

   107 

   108 // 1 

   109 val trans1 = Set[Edge[State, Char]](

   110   { case (Q0, 'a') => Q1 },

   111   { case (Q0, _)   => Q0 },

   112   { case (Q1, _)   => Q2 },

   113   { case (Q2, _)   => Q3 },

   114   { case (Q3, _)   => Q4 },

   115   { case (Q4, 'b') => Q5 },

   116   { case (Q5, 'c') => Q6 }

   117 )

   118 

   119 val nfa1 = NFA(Set[State](Q0), trans1, Set[State](Q6))

   120 

   121 nfa1.accepts("axaybzbc".toList)     // true

   122 nfa1.accepts("aaaaxaybzbc".toList)  // true

   123 nfa1.accepts("axaybzbd".toList)     // false

   124 

   125 

   126 

   127 // 2

   128 val trans2 = Set[Edge[State, Char]](

   129   { case (Q0, 'a') => Q0 },

   130   { case (Q0, 'a') => Q1 },

   131   { case (Q0, 'b') => Q2 },

   132   { case (Q1, 'a') => Q1 },

   133   { case (Q2, 'b') => Q2 }

   134 )

   135 

   136 val nfa2 = NFA(Set[State](Q0), trans2, Set[State](Q2))

   137 

   138 nfa2.accepts("aa".toList)             // false

   139 nfa2.accepts("aaaaa".toList)          // false

   140 nfa2.accepts("aaaaab".toList)         // true

   141 nfa2.accepts("aaaaabbb".toList)       // true

   142 nfa2.accepts("aaaaabbbaaa".toList)    // false

   143 nfa2.accepts("ac".toList)             // false

   144 

   145 // 3

   146 val trans3 = Set[Edge[State, Char]](

   147   { case (Q0, _)   => Q0 },

   148   { case (Q0, 'a') => Q1 },

   149   { case (Q0, 'b') => Q3 },

   150   { case (Q1, 'b') => Q2 },

   151   { case (Q2, 'c') => Q5 },

   152   { case (Q3, 'c') => Q4 },

   153   { case (Q4, 'd') => Q5 }

   154 )

   155 

   156 val nfa3 = NFA(Set[State](Q0), trans3, Set[State](Q5))

   157 

   158 nfa3.accepts("aaaaabc".toList)      // true

   159 nfa3.accepts("aaaabcd".toList)      // true

   160 nfa3.accepts("aaaaab".toList)       // false

   161 nfa3.accepts("aaaabc".toList)       // true

   162 nfa3.accepts("aaaaabbbaaa".toList)  // false

   163 

   164 

   165 

   166 // subset, or powerset, construction

   167 def powerset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {

   168   DFA(nfa.starts, 

   169       { case (qs, c) => nfa.nexts(qs, c) },

   170       _.exists(nfa.fins))

   171 }

   172 

   173 val dfa2 = powerset(nfa1)

   174 

   175 dfa2.accepts("axaybzbc".toList)     // true

   176 dfa2.accepts("aaaaxaybzbc".toList)  // true

   177 dfa2.accepts("axaybzbd".toList)     // false

   178 

   179 val dfa3 = powerset(nfa2)

   180 

   181 dfa3.accepts("aa".toList)             // false

   182 dfa3.accepts("aaaaa".toList)          // false

   183 dfa3.accepts("aaaaab".toList)         // true

   184 dfa3.accepts("aaaaabbb".toList)       // true

   185 dfa3.accepts("aaaaabbbaaa".toList)    // false

   186 dfa3.accepts("ac".toList)             // false

   187 

   188 

   189 import scala.annotation.tailrec

   190 @tailrec

   191 def fixpT[A](f: A => A, x: A): A = {

   192   val fx = f(x)

   193   if (fx == x) x else fixpT(f, fx) 

   194 }

   195 

   196 

   197 case class eNFA[A, C](starts: Set[A],                    // starting state

   198                       trans: Set[Edge[A, Option[C]]],    // transition edges

   199                       fins:  A => Boolean) {             // final states 

   200 

   201   def enext(q: A) : Set[A] = 

   202     trans.flatMap(_.lift.apply((q, None)))

   203 

   204   def enexts(qs: Set[A]) : Set[A] = 

   205     qs ++ qs.flatMap(enext(_))

   206 

   207   // epsilon closure

   208   def ecl(qs: Set[A]) : Set[A] = 

   209     fixpT(enexts, qs)

   210 

   211   def next(q: A, c: C) : Set[A] = 

   212     trans.flatMap(_.lift.apply((q, Some(c))))

   213 

   214   def nexts(qs: Set[A], c: C) : Set[A] = 

   215     qs.flatMap(next(_, c))

   216 

   217   def nextss(qs: Set[A], s: List[C]) : Set[A] = s match {

   218     case Nil => ecl(qs)

   219     case c::cs => nextss(ecl(nexts(ecl(qs), c)), cs)

   220   }

   221 

   222   def accepts(s: List[C]) : Boolean = 

   223     nextss(starts, s.toList).exists(fins)

   224 

   225 }

   226 

   227 val etrans1 = Set[Edge[State, Option[Char]]](

   228   { case (Q0, Some('a')) => Q1 },

   229   { case (Q1, None) => Q0 }

   230 )

   231 

   232 val enfa = eNFA(Set[State](Q0), etrans1, Set[State](Q1))

   233 

   234 enfa.accepts("a".toList)              // true

   235 enfa.accepts("".toList)               // false

   236 enfa.accepts("aaaaa".toList)          // true

   237 enfa.accepts("aaaaab".toList)         // flase

   238 enfa.accepts("aaaaabbb".toList)       // false

   239 enfa.accepts("aaaaabbbaaa".toList)    // false

   240 enfa.accepts("ac".toList)             // false

   241 

   242 

   243 

   244 abstract class Rexp

   245 case object ZERO extends Rexp

   246 case object ONE extends Rexp

   247 case class CHAR(c: Char) extends Rexp

   248 case object ALL extends Rexp

   249 case class ALT(r1: Rexp, r2: Rexp) extends Rexp 

   250 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 

   251 case class STAR(r: Rexp) extends Rexp 

   252 case class NTIMES(r: Rexp, n: Int) extends Rexp 

   253 case class UPNTIMES(r: Rexp, n: Int) extends Rexp 

   254 

   255 import scala.language.implicitConversions    

   256 import scala.language.reflectiveCalls 

   257 

   258 def charlist2rexp(s: List[Char]): Rexp = s match {

   259   case Nil => ONE

   260   case c::Nil => CHAR(c)

   261   case c::s => SEQ(CHAR(c), charlist2rexp(s))

   262 }

   263 implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)

   264 

   265 implicit def RexpOps (r: Rexp) = new {

   266   def | (s: Rexp) = ALT(r, s)

   267   def % = STAR(r)

   268   def ~ (s: Rexp) = SEQ(r, s)

   269 }

   270 

   271 implicit def stringOps (s: String) = new {

   272   def | (r: Rexp) = ALT(s, r)

   273   def | (r: String) = ALT(s, r)

   274   def % = STAR(s)

   275   def ~ (r: Rexp) = SEQ(s, r)

   276   def ~ (r: String) = SEQ(s, r)

   277 }

   278 

   279 

   280 

   281 // nullable function: tests whether the regular 

   282 // expression can recognise the empty string

   283 def nullable (r: Rexp) : Boolean = r match {

   284   case ZERO => false

   285   case ONE => true

   286   case CHAR(_) => false

   287   case ALL => false

   288   case ALT(r1, r2) => nullable(r1) || nullable(r2)

   289   case SEQ(r1, r2) => nullable(r1) && nullable(r2)

   290   case STAR(_) => true

   291   case NTIMES(r, i) => if (i == 0) true else nullable(r)

   292   case UPNTIMES(r: Rexp, n: Int) => true

   293 }

   294 

   295 // derivative of a regular expression w.r.t. a character

   296 def der (c: Char, r: Rexp) : Rexp = r match {

   297   case ZERO => ZERO

   298   case ONE => ZERO

   299   case CHAR(d) => if (c == d) ONE else ZERO

   300   case ALL => ONE

   301   case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))

   302   case SEQ(r1, r2) => 

   303     if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))

   304     else SEQ(der(c, r1), r2)

   305   case STAR(r1) => SEQ(der(c, r1), STAR(r1))

   306   case NTIMES(r1, i) => 

   307     if (i == 0) ZERO else

   308     if (nullable(r1)) SEQ(der(c, r1), UPNTIMES(r1, i - 1))

   309     else SEQ(der(c, r1), NTIMES(r1, i - 1))

   310   case UPNTIMES(r1, i) => 

   311     if (i == 0) ZERO

   312     else SEQ(der(c, r1), UPNTIMES(r1, i - 1)) 

   313 }

   314 

   315 

   316 // partial derivative of a regular expression w.r.t. a character

   317 def pder (c: Char, r: Rexp) : Set[Rexp] = r match {

   318   case ZERO => Set()

   319   case ONE => Set()

   320   case CHAR(d) => if (c == d) Set(ONE) else Set()

   321   case ALL => Set(ONE)

   322   case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2)

   323   case SEQ(r1, r2) => 

   324     (for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++ 

   325     (if (nullable(r1)) pder(c, r2) else Set())

   326   case STAR(r1) => 

   327     for (pr1 <- pder(c, r1)) yield SEQ(pr1, STAR(r1))

   328   case NTIMES(r1, i) => 

   329     if (i == 0) Set() else

   330     if (nullable(r1)) 

   331       for (pr1 <- pder(c, r1)) yield SEQ(pr1, UPNTIMES(r1, i - 1))

   332     else 

   333       for (pr1 <- pder(c, r1)) yield SEQ(pr1, NTIMES(r1, i - 1))

   334   case UPNTIMES(r1, i) => 

   335     if (i == 0) Set()

   336     else 

   337       for (pr1 <- pder(c, r1)) yield SEQ(pr1, UPNTIMES(r1, i - 1))

   338 }

   339 

   340 val r = STAR(ALL) ~ "a" ~ NTIMES(ALL, 3) ~ "bc"

   341 val pder_nfa = NFA[Set[Rexp], Char](Set(Set(r)), 

   342                                     Set( { case (rs, c) => rs.flatMap(pder(c, _))} ), 

   343                                     _.exists(nullable))

   344 

   345 

   346 

   347 pder_nfa.accepts("axaybzbc".toList)     // true

   348 pder_nfa.accepts("aaaaxaybzbc".toList)  // true

   349 pder_nfa.accepts("axaybzbd".toList)     // false

   350 

   351 

   352 

   353 

   354 ///

   355 type Trans[A, C] = Map[(A, C), A]

   356