THLR/thlr_5_code.py at main · byhlel/THLR · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
from thlr_automata import *


#[Q2]

def is_complete(nfa):
  inc= nfa.all_states
  for i in inc:
    for j in nfa.alphabet:
      if len(nfa.get_successors(i,j))==0:
        return False
  return True

#[\Q2]

#[Q3]

def is_deterministic(nfa):
  inc = nfa.all_states
  for i in inc:
    for j in nfa.alphabet:
      if len(nfa.get_successors(i,j))>1:
        return False
  return True

#[\Q3]

#[Q4]

def get_reachable_states(nfa,origins,letter):
  l=[]
  for i in origins:
    liste = nfa.get_successors(i,letter)
    for j in liste:
      l.append(j)
  return set(l)

#[\Q4]

#[Q5]

def accepts_from(nfa,current_states,word):
  if word=="":
    for i in current_states:
      if i in nfa.final_states:
        return True
    return False
  else:
    l=get_reachable_states(nfa,current_states,word[0])
    return accepts_from(nfa,l,word[1:])

#[\Q5]

#[Q6]

def accepts(nfa,word):
  return accepts_from(nfa,nfa.initial_states,word)

#[\Q6]

#[Q7]

def determinize(nfa):
  vis = []
  tal=[]
  tis=[]
  tfl= []
  te=[]
  tis.append(set(nfa.initial_states))
  tas.append(set(nfa.initial_states))
  inc = tis
  poubelle = nfa.add_state()
  nfa.remove_state(poubelle)
  lpoub =[]
  lpoub.append(poubelle)
  spoub= set(lpoub)
  tas.append(spoub)
  for i in nfa.alphabet:
    te.append((spoub, i, spoub))
  while len(inc)!=0:
    posi = inc[0]
    for lettre in nfa.alphabet:
      ifs= False
      liste = get_reachable_states(nfa,posi,lettre)
      for j in nfa.final_states:
        if j in liste:
          ifs= True
      if len(liste)==0:
        thisedges.append((posi,lettre,spoub))
      else:
        n= set(liste)
        if n not in tas:
          tas.append(n)
          if ifs:
            tfs.append(node)
        te.append((posi,lettre,n))
        if n not in inc:
          if n not in vis:
            incoming.append(n)
    vis.append(posi)
    inc.pop(0)
  l= symbolic_nfa_builder(tas,tis,tfs,nfa.alphabet,te)
  return l

#[\Q7]