Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 6th, 2018 70 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. package As1
  2.  
  3. import scala.io._
  4. import scala.collection.mutable.{MStack => Stack}
  5.  
  6. object NFA {
  7.   import FiniteAutomata._
  8.   type TransitionFunction = (State, Symbol) => Set[State]
  9.  
  10.   //"five-tuple" definition for an NFA.
  11.   case class Definition(states: Set[State],
  12.                         inputSymbols: Set[Symbol],
  13.                         startState: State,
  14.                         transitions: Set[(State, Symbol, Set[State])],
  15.                         acceptingStates: Set[State])
  16.   /**
  17.     First line - input symbols
  18.     Second line - states in the NFA
  19.     Third line - start state
  20.     Fourth line - accepting states
  21.     Subsequent lines - transitions
  22.  
  23.     I have made the assumption that input symbols will be single characters
  24.   */
  25.   def fromFile(filename: String): Definition = {
  26.     type Transition = (State, Symbol, Set[State])
  27.  
  28.     def toTransition(tokens: Seq[Symbol]): Transition = {
  29.       (State(tokens(0)),
  30.        if (tokens(1) == 'epsilon) 'ε else tokens(1),
  31.        tokens.drop(2).map(State).toSet)
  32.     }
  33.    
  34.     var inputSymbols:Set[Symbol]   = null
  35.     var states:Set[State]          = null  
  36.     var startState:State           = null
  37.     var acceptingStates:Set[State] = null
  38.     var transitions:Set[(State, Symbol, Set[State])] = Set.empty
  39.    
  40.     Source.fromFile(filename).getLines.withFilter(!_.isEmpty).zipWithIndex.foreach((e) => {
  41.       e match {
  42.         case (line, 0) => inputSymbols = tokenize(line).toSet
  43.         case (line, 1) => states = tokenize(line).map(State).toSet
  44.         //If there is more than one start, this simply selects the first
  45.         case (line, 2) => startState = State(tokenize(line)(0))
  46.         case (line, 3) => acceptingStates = tokenize(line).map(State).toSet
  47.         case (line, _) => {
  48.           val newTransitions = Set(toTransition(tokenize(line)))
  49.           transitions = transitions union newTransitions
  50.         }
  51.       }
  52.     })
  53.  
  54.     Definition(states, inputSymbols, startState, transitions, acceptingStates)
  55.   }
  56.  
  57.   //TODO: test, write in a functional style
  58.   def epsilonClosure(ss: Set[State], trans: TransitionFunction):Set[State] = {
  59.     val stack = MStack(ss.toSeq:_*)
  60.     var result = ss
  61.  
  62.     while (!stack.isEmpty) {      
  63.       var currentState = stack.pop
  64.  
  65.       trans(currentState, 'ε).foreach((u) => {
  66.         if (!epsilonClosure(ss, trans).contains(u)) {
  67.           result = result + u
  68.           stack.push(u)
  69.         }
  70.       })
  71.     }
  72.                  
  73.     return result
  74.   }  
  75.  
  76.   private def tokenize(str: String): Seq[Symbol] = {
  77.     str.replace(",", "").split(" ").map(Symbol(_))
  78.   }
  79. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top