progs/thompson.scala
author Christian Urban <urbanc@in.tum.de>
Tue, 25 Apr 2017 12:33:16 +0100
changeset 486 8178fcf377dc
child 487 a697421eaa04
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
486
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     1
// eNFA that does not accept any string
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     2
def eNFA_ZERO(): NFA[TState, Char] = {
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
  val Q = TState()
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     4
  NFA(Set(Q), { case _ => Set() }, Set())
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     5
}
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     7
// eNFA that accepts the empty string
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     8
def eNFA_ONE() : NFA[TState, Char] = {
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
  val Q = TState()
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    10
  NFA(Set(Q), { case _ => Set() }, Set(Q))
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    11
}
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    12
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    13
// eNFA that accepts the string "c"
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    14
def eNFA_CHAR(c: Char) : NFA[TState, Char] = {
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    15
  val Q1 = TState()
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    16
  val Q2 = TState()
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    17
  NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2))
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    18
}
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    19
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    20
// alternative of two eNFAs
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    21
def eNFA_ALT(enfa1: NFA[TState, Char], enfa2: NFA[TState, Char]) : NFA[TState, Char] = {
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    22
  val Q = TState()
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    23
  val new_delta : eNFAtrans = 
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    24
    { case (Q, None) => enfa1.starts | enfa2.starts }
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    26
  val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q)
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    27
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    28
  eNFA(Set(Q), 
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    29
       new_delta andAlso enfa1.delta andAlso enfa2.delta, 
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    30
       new_fins)
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    31
}
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    32
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    33
// sequence of two eNFAs
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    34
def eNFA_SEQ(enfa1: NFA[TState, Char], enfa2: NFA[TState, Char]) : NFA[TState, Char] = {
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    35
  val new_delta : eNFAtrans = 
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    36
    { case (q, None) if enfa1.fins(q) => enfa2.starts }
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    37
  
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    38
  eNFA(enfa1.starts, 
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    39
       new_delta andAlso enfa1.delta andAlso enfa2.delta, 
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    40
       enfa2.fins)
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    41
}
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    42
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    43
// star of an eNFA
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    44
def eNFA_STAR(enfa: NFA[TState, Char]) : NFA[TState, Char] = {
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    45
  val Q = TState()
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    46
  val new_delta : eNFAtrans = 
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    47
    { case (Q, None) => enfa.starts
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    48
      case (q, None) if enfa.fins(q) => Set(Q) }
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    49
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    50
  eNFA(Set(Q), new_delta andAlso enfa.delta, Set(Q))
8178fcf377dc updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    51
}