Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ######## compile word to dfa
- alphabet = 'abcdefghijklmnopqrstuvwxyz'
- def bitstoint(bs):
- n = 0
- for b in reversed(bs):
- n = 2*n + b
- return n
- def compile_word_to_dfa_that_matches_it_as_substring(word):
- """
- The state of the automaton must tell, for each i, whether the
- input so far ends in word[:i].
- If the input so far ends in word[:i], and the next character is
- indeed word[i], then the input so far ends in word[:i+1];
- otherwise it doesn't.
- As an exception to this rule, if the input so far ends in word,
- then this will forever be the state of the automaton.
- """
- assert set(word) <= set(alphabet)
- N = 2**(len(word) + 1) # all states are 0 <= s < N; (s & (1 << i)) is valid for 0 <= i <= len(word)
- def transition(s, c):
- if s == N-1:
- return N-1 # accepting state
- if s & (1 << (len(word)-1)) and word[-1] == c:
- return N-1
- return 1 + 2*bitstoint([
- int(s & (1 << i) and word[i] == c)
- for i in range(len(word))
- ])
- transition_matrices = {
- c: [[int(transition(i, c) == j) for j in range(N)] for i in range(N)]
- for c in alphabet
- }
- initial_state = 1
- final_state = N-1
- return (transition_matrices, initial_state, final_state)
- ######## (optional: optimize the dfa)
- ######## probability calculation
- import numpy as np
- def calculate_acceptance_probability(dfa, q, t):
- transition_matrices, initial_state, final_state = dfa
- Aq = sum([np.array(transition_matrices[c])*q[c] for c in alphabet]).transpose()
- N = Aq.shape[0]
- v = np.array([int(i == initial_state) for i in range(N)])
- for _ in range(t):
- v = np.dot(Aq, v)
- return v[final_state]
- ######## demo
- word = 'joel' # the 4 letter word
- t = 8 # the total number of letters
- dfa = compile_word_to_dfa_that_matches_it_as_substring(word)
- q = {c: 1/len(alphabet) for c in alphabet}
- answer = calculate_acceptance_probability(dfa, q, t)
- print(f"The accepted stackexchange answer: {5/26**4}")
- print(f"The exact answer with automaton: {answer}")
- """ demo output
- box% python -i main.py
- The accepted stackexchange answer: 1.094149364518049e-05
- The exact answer with automaton: 1.094148885652915e-05
- >>>
- """
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement