Classical transformations¶

Boolean automata

In [1]:
# We disable autosave for technical reasons.
# Replace 0 by 120 in next line to restore default.
%autosave 0

Autosave disabled
In [2]:
import awalipy # If import fails, check that 
               # Python version used as Jupyter
               # kernel matches the one
               # Awalipy was compiled with.

[Warning] The python module awalipy relies on compilation executed "on-the-fly" depending on the context (type of weights, of labels, etc.). As a result, the very first call to a given function in a given context may take up to one minute.

1. Determinization¶

(a1 is one of the example automaton in the library.)

In [3]:
A1 = awalipy.load("a1")
A1.display()
%3 I2 2 p I2->2 F4 2->2 a, b 3 q 2->3 a 4 r 3->4 b 4->F4 4->4 a, b
In [4]:
A2 = A1.determinize()
A2.display()
%3 I2 2 $0 I2->2 F4 F5 2->2 b 3 $1 2->3 a 3->3 a 4 $2 3->4 b 4->F4 4->4 b 5 $3 4->5 a 5->F5 5->4 b 5->5 a

2. Minimization¶

The minization process is called with the method min_quotient.

In [5]:
A3 = A2.min_quotient()
A3.display()
%3 I2 2 $0 I2->2 F3 2->2 b 4 $1 2->4 a 3 $2 3->F3 3->3 a, b 4->3 b 4->4 a

3. Epsilon removal¶

The epsilon-removal process is called with the method proper().

In [6]:
B = awalipy.Automaton("ab",size=5,allow_eps=True)
s = B.states()
B.set_initial(0)
B.add_transition(s[0],s[1],'a')
B.add_transition(s[1],s[0],'a')
B.add_transition(s[0],s[0],'b')
B.add_transition(s[1],s[1],'b')
B.add_transition(s[2],s[3],'a')
B.add_transition(s[3],s[4],'a')
B.add_transition(s[4],s[2],'a')
B.add_transition(s[2],s[4],'b')
B.add_transition(s[4],s[3],'b')
B.add_transition(s[3],s[2],'b')
B.add_transition(s[0],s[2],"\\e")
B.add_transition(s[2],s[0],"\\e")
B.set_final(2)
B.display()
%3 I2 2 $0 I2->2 F4 2->2 b 3 $1 2->3 a 4 $2 2->4 \e 3->2 a 3->3 b 4->F4 4->2 \e 5 $3 4->5 a 6 $4 4->6 b 5->4 b 5->6 a 6->4 a 6->5 b
In [7]:
B2 = B.proper()
B2.display()
%3 I2 2 $0 I2->2 F2 F4 2->F2 2->2 b 3 $1 2->3 a 5 $3 2->5 a 6 $4 2->6 b 3->2 a 3->3 b 4 $2 4->F4 4->2 b 4->3 a 4->5 a 4->6 b 5->4 b 5->6 a 6->4 a 6->5 b

4. All in one "minimal automaton"¶

The method minimal_automaton() gives the minimal DFA equivalent to its arguments. Determinizing and removing epsilon transition if necessary.

Let us take back the automaton B.

In [8]:
B.display()
%3 I2 2 $0 I2->2 F4 2->2 b 3 $1 2->3 a 4 $2 2->4 \e 3->2 a 3->3 b 4->F4 4->2 \e 5 $3 4->5 a 6 $4 4->6 b 5->4 b 5->6 a 6->4 a 6->5 b

...and call the method minimal_automaton().

In [9]:
B.minimal_automaton().display()
%3 I3 3 $0 I3->3 F3 F4 2 $1 4 $2 2->4 a, b 3->F3 3->2 a 3->4 b 4->F4 4->4 a, b

5. Product (intersection)¶

In [10]:
C1 = awalipy.load("evena")
C2 = awalipy.load("oddb")
C1.display()
C2.display()
%3 I2 2 p I2->2 F2 2->F2 2->2 b 3 q 2->3 a 3->2 a 3->3 b
%3 I2 2 p I2->2 F3 2->2 a 3 q 2->3 b 3->F3 3->2 b 3->3 a

C is the (intersection) product of C1 with C2.

In [11]:
C = awalipy.product(C1,C2)
C.display()
%3 I2 2 $0 I2->2 F4 3 $1 2->3 a 4 $2 2->4 b 3->2 a 5 $3 3->5 b 4->F4 4->2 b 4->5 a 5->3 b 5->4 a

When standard operation is used, the "history" of each state is stored and may be displayed.

In [12]:
C.display(history=True)
%3 I2 2 (p, p) I2->2 F4 3 (q, p) 2->3 a 4 (p, q) 2->4 b 3->2 a 5 (q, q) 3->5 b 4->F4 4->2 b 4->5 a 5->3 b 5->4 a

6. Sum (union)¶

Recalling the operands C1 and C2

In [13]:
C1.display()
C2.display()
%3 I2 2 p I2->2 F2 2->F2 2->2 b 3 q 2->3 a 3->2 a 3->3 b
%3 I2 2 p I2->2 F3 2->2 a 3 q 2->3 b 3->F3 3->2 b 3->3 a

The function union() simply puts the two automata side by side.

In [14]:
D = C1.sum(C2)
D.display()
%3 I2 2 $0 I2->2 I4 4 $2 I4->4 F2 F5 2->F2 2->2 b 3 $1 2->3 a 3->2 a 3->3 b 4->4 a 5 $3 4->5 b 5->F5 5->4 b 5->5 a

Determinizing and minimizing D

In [15]:
D.minimal_automaton().display(history=True)
%3 I3 3 {{$0, $2}} I3->3 F3 F4 F5 2 {{$1, $2}} 2->3 a 5 {{$1, $3}} 2->5 b 3->F3 3->2 a 4 {{$0, $3}} 3->4 b 4->F4 4->3 b 4->5 a 5->F5 5->2 b 5->4 a

7. Concatenation¶

Recalling the operands C1 and C2

In [16]:
C1.display()
C2.display()
%3 I2 2 p I2->2 F2 2->F2 2->2 b 3 q 2->3 a 3->2 a 3->3 b
%3 I2 2 p I2->2 F3 2->2 a 3 q 2->3 b 3->F3 3->2 b 3->3 a

Concatenating by C1 and C2. Result may be non-deterministic.

In [17]:
E = C1.concatenate(C2)
E.display()
%3 I2 2 $0 I2->2 F5 2->2 b 3 $1 2->3 a 4 $2 2->4 a 5 $3 2->5 b 3->2 a 3->3 b 4->4 a 4->5 b 5->F5 5->4 b 5->5 a
In [18]:
F = E.minimal_automaton()
F.display()
%3 I2 2 $0 I2->2 F3 F4 3 $2 2->3 b 5 $1 2->5 a 3->F3 3->3 a, b 4 $6 4->F4 4->3 a 4->5 b 5->2 a 5->4 b

8. Complementation¶

In [19]:
G = F.complement()
G.display()
%3 I2 2 $0 I2->2 F2 F5 2->F2 3 $2 2->3 b 5 $1 2->5 a 3->3 a, b 4 $6 4->3 a 4->5 b 5->F5 5->2 a 5->4 b
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]: