progs/nfa.scala
changeset 490 4fee50f38305
parent 489 e28d7a327870
child 491 d5776c6018f0
equal deleted inserted replaced
489:e28d7a327870 490:4fee50f38305
    83 
    83 
    84 
    84 
    85 
    85 
    86 // subset constructions
    86 // subset constructions
    87 
    87 
    88 //def subset(nfa: NFA[A, C]) : DFA[Set[A], C] =
    88 def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {
       
    89   DFA(nfa.starts, 
       
    90       { case (qs, c) => nfa.nexts(qs, c) }, 
       
    91       _.exists(nfa.fins))
       
    92 }
       
    93 
       
    94 subset(nfa1).accepts("aa".toList)             // false
       
    95 subset(nfa1).accepts("aaaaa".toList)          // false
       
    96 subset(nfa1).accepts("aaaaab".toList)         // true
       
    97 subset(nfa1).accepts("aaaaabbb".toList)       // true
       
    98 subset(nfa1).accepts("aaaaabbbaaa".toList)    // false
       
    99 subset(nfa1).accepts("ac".toList)             // false