daily pastebin goal
11%
SHARE
TWEET

Untitled

a guest Jun 5th, 2018 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package nfa
  2.  
  3.  
  4.  
  5.  
  6. // A nondeterministic Finite Automaton (NFA) consists of states,
  7. // symbols in an alphabet, and a transition function.
  8.  
  9. // A state in the NFA is represented as an unsigned integer.
  10. type state uint
  11.  
  12. // An symbol in the NFA is a single rune, i.e. a character.
  13. type symbol rune
  14.  
  15. // Given the current state and a symbol, the transition function
  16. // of an NFA returns the set of next states the NFA can transition to
  17. // on reading the given symbol.
  18. // This set of next states could be empty.
  19. type TransitionFunction func(st state, sym symbol) []state
  20.  
  21. // Reachable returns true if there exists a sequence of transitions
  22. // from transitions such that if the NFA starts at the start state
  23. // start it would reach the final state final after reading the
  24. // entire sequence of symbols input; Reachable returns false otherwise.
  25. var transitionsLength = 0
  26. var explored []bool
  27.  
  28. func Reachable(transitions TransitionFunction, start, final state, input []symbol) bool {
  29.     nextState := transitions(start, 99)
  30.     n := len(input)
  31.  
  32.  
  33.     if n == 0 { //base case
  34.  
  35.         if start == final{
  36.             return true
  37.         } else{
  38.             return false
  39.         }
  40.     }
  41.  
  42.  
  43.    
  44.     if n != 0{
  45.         nextState = transitions(start, input[0]) //check len.  check if empty.
  46.         transitionsLength = len(nextState)
  47.  
  48.        
  49.     }
  50.    
  51.  
  52.     if transitionsLength == 0{
  53.         return false
  54.     }
  55.     if transitionsLength >=1{ //only explore the transitions if they can be explored.
  56.        
  57.         if n != 0{
  58.             deleteThisIndex := 0
  59.             new_input := append(input[:deleteThisIndex], input[deleteThisIndex+1:]...) //update symbols
  60.             for i := 0; i < len(nextState); i++{
  61.                 //update explored
  62.                 explored = append(explored, Reachable(transitions, nextState[i], final, new_input))
  63.        
  64.             }
  65.            
  66.    
  67.  
  68.         }
  69.  
  70.     }
  71.  
  72.  
  73.     for i := 0; i < len(explored); i++{
  74.         if explored[i]{
  75.             explored = explored[:0]
  76.             return true
  77.         }
  78.     }
  79.  
  80.     return false
  81. }
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