• API
• FAQ
• Tools
• Archive
daily pastebin goal
8%
SHARE
TWEET

# Untitled

a guest Jun 5th, 2018 111 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.

Top