progs/dfa.scala
author cu
Thu, 28 Sep 2017 11:04:11 +0100
changeset 510 25580bf89ac0
parent 487 a697421eaa04
child 576 550186034b6e
permissions -rw-r--r--
typos
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
485
bd6d999ab7b6 updated
Christian Urban <urbanc@in.tum.de>
parents: 483
diff changeset
     1
// DFAs in Scala  using partial functions
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     2
import scala.util.Try
479
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     3
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     4
// type abbreviation for partial functions
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     5
type :=>[A, B] = PartialFunction[A, B]
479
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     6
483
6f508bcdaa30 updated
Christian Urban <urbanc@in.tum.de>
parents: 481
diff changeset
     7
case class DFA[A, C](start: A,               // starting state
6f508bcdaa30 updated
Christian Urban <urbanc@in.tum.de>
parents: 481
diff changeset
     8
                     delta: (A, C) :=> A,    // transition (partial fun)
6f508bcdaa30 updated
Christian Urban <urbanc@in.tum.de>
parents: 481
diff changeset
     9
                     fins:  A => Boolean) {  // final states
479
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    10
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    11
  def deltas(q: A, s: List[C]) : A = s match {
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    12
    case Nil => q
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    13
    case c::cs => deltas(delta(q, c), cs)
145
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    14
  }
479
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    15
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    16
  def accepts(s: List[C]) : Boolean = 
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    17
    Try(fins(deltas(start, s))) getOrElse false
479
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    18
}
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    19
487
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    20
// the example shown in the handout 
145
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    21
abstract class State
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    22
case object Q0 extends State
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    23
case object Q1 extends State
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    24
case object Q2 extends State
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    25
case object Q3 extends State
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    26
case object Q4 extends State
145
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    27
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    28
val delta : (State, Char) :=> State = 
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    29
  { case (Q0, 'a') => Q1
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    30
    case (Q0, 'b') => Q2
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    31
    case (Q1, 'a') => Q4
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    32
    case (Q1, 'b') => Q2
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    33
    case (Q2, 'a') => Q3
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    34
    case (Q2, 'b') => Q2
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    35
    case (Q3, 'a') => Q4
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    36
    case (Q3, 'b') => Q0
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    37
    case (Q4, 'a') => Q4
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    38
    case (Q4, 'b') => Q4 }
145
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    39
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    40
val dfa = DFA(Q0, delta, Set[State](Q4))
145
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    41
480
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    42
dfa.accepts("bbabaab".toList)   // true
9e42ccbbd1e6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    43
dfa.accepts("baba".toList)      // false
487
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    44
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    45
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    46
// another DFA test with a Sink state
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    47
abstract class S
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    48
case object S0 extends S
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    49
case object S1 extends S
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    50
case object S2 extends S
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    51
case object Sink extends S
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    52
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    53
// transition function with a sink state
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    54
val sigma : (S, Char) :=> S = 
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    55
  { case (S0, 'a') => S1
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    56
    case (S1, 'a') => S2
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    57
    case _ => Sink
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    58
  }
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    59
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    60
val dfa1a = DFA(S0, sigma, Set[S](S2))
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    61
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    62
dfa1a.accepts("aa".toList)        // true
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    63
dfa1a.accepts("".toList)          // false
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    64
dfa1a.accepts("ab".toList)        // false
a697421eaa04 updated
Christian Urban <urbanc@in.tum.de>
parents: 485
diff changeset
    65