progs/dfa.scala
author Christian Urban <urbanc@in.tum.de>
Fri, 17 Mar 2017 12:15:58 +0000
changeset 479 52aa298211f6
parent 145 920f675b4ed1
child 481 acd8780bfc8b
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
479
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     1
// convert normal string to hex bytes string
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     2
def string2hex(str: String): String = {
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     3
  str.toList.map(_.toInt.toHexString).mkString
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     4
}
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     5
    
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     6
// convert hex bytes string to normal string
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     7
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     8
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
     9
val byteArray: Array[Byte] = List.range(1, 255).map(_.toByte).toArray
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    10
val bos = new BufferedOutputStream(new FileOutputStream("test.txt"))
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    11
bos.write(byteArray)
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    12
bos.close() 
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    13
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    14
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    15
def string2int(hex: String) = {
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    16
  hex.sliding(2, 2).map(Integer.parseInt(_, 16)).toArray
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    17
}
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
def test(l: List[Int]) = {
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    20
  l.map(_.toChar).mkString
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    21
}
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    22
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    23
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    24
import java.io._
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    25
val writer = new PrintWriter(new File("test.txt" ))
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    26
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    27
//writer.write(string2int("cafebabe"))
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    28
writer.write(test(List.range(1, 255)))
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    29
writer.close()
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    30
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    31
import scalax.io._
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    32
import scalax.io.Resource
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    33
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    34
FileOutputStream fos = new FileOutputStream("test");
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    35
fos.write(bytesArray);
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    36
fos.close();
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    37
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    38
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    39
string2int("cafebabe")
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    40
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    41
202.toHexString
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    42
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    43
"cafebabe".sliding(1, 1).toList.map(Integer.parseInt(_, 16)).map(_.toByte).map(_.toChar)
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    44
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    45
hex2string("ca")
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    46
string2hex("ca")
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    47
hex2string("cafebabe")
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    48
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    49
    
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    50
val appkey = "9GLV//lv/kYFW2o3/bihxwnMcmo="
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    51
        
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    52
        // string to hex
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    53
        val appkey_hex = string2hex(appkey)
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    54
        // 39474c562f2f6c762f6b594657326f332f62696878776e4d636d6f3d
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    55
        println(appkey_hex)
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    56
        
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    57
        // hex to string
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    58
        val appkey_string_again = hex2string(appkey_hex)
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    59
        // 9GLV//lv/kYFW2o3/bihxwnMcmo=
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    60
        println(appkey_string_again)
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    61
    }
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    62
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    63
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    64
List("ca", "fe", "ba", "be").map(_.toByte)
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    65
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    66
"ca".toByte
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    67
52aa298211f6 updated
Christian Urban <urbanc@in.tum.de>
parents: 145
diff changeset
    68
145
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    69
// DFAs
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    70
import scala.util._
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    71
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    72
abstract class State
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    73
type States = Set[State]
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    74
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    75
case class IntState(i: Int) extends State
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    76
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    77
object NewState {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    78
  var counter = 0
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    79
  
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    80
  def apply() : IntState = {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    81
    counter += 1;
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    82
    new IntState(counter - 1)
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    83
  }
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    84
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    85
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    86
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    87
// DFA class
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    88
case class DFA(states: States, 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    89
               start: State, 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    90
               delta: (State, Char) => State, 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    91
               fins: States) {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    92
  
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    93
  def deltas(q: State, s: List[Char]) : State = s match {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    94
    case Nil => q
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    95
    case c::cs => deltas(delta(q, c), cs) 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    96
  }
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    97
  
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    98
  // wether a string is accepted by the automaton or not
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    99
  def accepts(s: String) : Boolean = 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   100
    Try(fins contains 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   101
      (deltas(start, s.toList))) getOrElse false
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   102
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   103
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   104
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   105
// example DFA from the lectures
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   106
val Q0 = NewState()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   107
val Q1 = NewState()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   108
val Q2 = NewState()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   109
val Q3 = NewState()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   110
val Q4 = NewState()
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   111
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   112
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   113
val delta : (State, Char) => State = {
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   114
  case (Q0, 'a') => Q1
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   115
  case (Q0, 'b') => Q2
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   116
  case (Q1, 'a') => Q4
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   117
  case (Q1, 'b') => Q2
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   118
  case (Q2, 'a') => Q3
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   119
  case (Q2, 'b') => Q2
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   120
  case (Q3, 'a') => Q4
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   121
  case (Q3, 'b') => Q0
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   122
  case (Q4, 'a') => Q4
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   123
  case (Q4, 'b') => Q4
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   124
}
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   125
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   126
val DFA1 = DFA(Set(Q0, Q1, Q2, Q3, Q4), Q0, delta, Set(Q4))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   128
println(DFA1.accepts("aaa"))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   129
println(DFA1.accepts("bb"))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   130
println(DFA1.accepts("aaac"))
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   131
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   132