from unittest import TestCase
import unittest
from .context import PySimpleAutomata
import copy
from PySimpleAutomata import DFA
from PySimpleAutomata import automata_IO
[docs]class TestDfaWordAcceptance(TestCase):
[docs] def setUp(self):
self.dfa_word_acceptance_test_01 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_word_acceptance_test_01.dot')
self.dfa_word_acceptance_test_02 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_word_acceptance_test_02.dot')
[docs] def test_word_acceptance(self):
""" Tests a correct word """
self.assertTrue(
DFA.dfa_word_acceptance(self.dfa_word_acceptance_test_01,
['5c', '10c', 'gum', '5c', '10c',
'gum']))
[docs] def test_word_acceptance_false(self):
""" Tests a non correct word, with good alphabet"""
self.assertFalse(
DFA.dfa_word_acceptance(self.dfa_word_acceptance_test_01,
['5c', '10c', 'gum', '5c', '10c']))
[docs] def test_word_acceptance_wrong_alphabet(self):
""" Tests a non correct word, with letters not form the
dfa alphabet """
self.assertFalse(
DFA.dfa_word_acceptance(self.dfa_word_acceptance_test_01,
['5c', '10c', 'wrong']))
[docs] def test_word_acceptance_empty_word(self):
""" Tests an empty word"""
self.assertFalse(
DFA.dfa_word_acceptance(self.dfa_word_acceptance_test_02,
[]))
[docs] @unittest.expectedFailure
def test_word_acceptance_wrong_dict(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_word_acceptance({'goofy': 'donald'},
['5c', '10c', 'gum', '5c', '10c'])
[docs]class TestDfaCompletion(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_completion_test_01 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_completion_test_01.dot')
self.dfa_completion_test_02 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_completion_test_02.dot')
self.dfa_completion_test_03 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_completion_test_03.dot')
self.dfa_completion_test_01_completed = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_completion_test_01_completed.dot')
self.dfa_completion_test_02_completed = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_completion_test_02_completed.dot')
self.dfa_completion_test_03_completed = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_completion_test_03_completed.dot')
[docs] def test_dfa_completion(self):
""" Tests a correct completion """
self.assertDictEqual(
DFA.dfa_completion(self.dfa_completion_test_01),
self.dfa_completion_test_01_completed)
[docs] def test_dfa_completion_empty_states(self):
""" Tests a completion of a dfa without states"""
self.assertDictEqual(
DFA.dfa_completion(self.dfa_completion_test_02),
self.dfa_completion_test_02_completed)
[docs] def test_dfa_completion_empty_transitions(self):
""" Tests a completion of a dfa without transitions"""
self.assertDictEqual(
DFA.dfa_completion(self.dfa_completion_test_03),
self.dfa_completion_test_03_completed)
# @unittest.expectedFailure means that the code doesn't
# handle this situation/exception consciously
[docs] @unittest.expectedFailure
def test_dfa_completion_wrong_dict(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_completion({'goofy': 'donald'})
[docs] def test_dfa_completion_side_effects(self):
""" Tests the function correctly makes side effects on
input """
completed = DFA.dfa_completion(self.dfa_completion_test_01)
completed['states'].pop()
self.assertDictEqual(completed, self.dfa_completion_test_01)
[docs] def test_dfa_completion_side_effects_copy(self):
""" Tests the function doesn't make side effects if a
copy is passed as input """
completed = DFA.dfa_completion(
copy.deepcopy(self.dfa_completion_test_01))
self.assertNotEquals(completed, self.dfa_completion_test_01)
[docs]class TestDfaComplementation(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_complementation_test_01 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_complementation_test_01.dot')
self.dfa_complementation_test_01_complemented = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_complementation_test_01_complemented.dot')
self.dfa_complementation_test_02 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_complementation_test_02.dot')
self.dfa_complementation_test_02_complemented = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_complementation_test_02_complemented.dot')
self.dfa_complementation_test_03 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_complementation_test_03.dot')
self.dfa_complementation_test_03_complemented = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_complementation_test_03_complemented.dot')
[docs] def test_dfa_complementation(self):
""" Tests a correct complementation. """
complementation = DFA.dfa_complementation(
self.dfa_complementation_test_01)
self.assertDictEqual(complementation,
self.dfa_complementation_test_01_complemented)
[docs] def test_dfa_complementation_empty_states(self):
""" Tests a complementation on a DFA without states. """
self.assertDictEqual(DFA.dfa_complementation(
self.dfa_complementation_test_02),
self.dfa_complementation_test_02_complemented)
[docs] def test_dfa_complementation_empty_transitions(self):
""" Tests a complementation on a DFA without transitions. """
self.assertDictEqual(DFA.dfa_complementation(
self.dfa_complementation_test_03),
self.dfa_complementation_test_03_complemented)
[docs] @unittest.expectedFailure
def test_dfa_complementation_wrong_dict(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_complementation({'goofy': 'donald'})
[docs] def test_dfa_complementation_side_effects(self):
""" Tests the function doesn't make side effects on input
"""
original = copy.deepcopy(self.dfa_complementation_test_01)
complemented = DFA.dfa_complementation(
self.dfa_complementation_test_01)
self.assertEquals(original, self.dfa_complementation_test_01)
[docs]class TestDfaIntersection(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_intersection_1_test_01 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_intersection_1_test_01.dot')
self.dfa_intersection_2_test_01 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_intersection_2_test_01.dot')
self.dfa_intersection_1_test_02 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_intersection_1_test_02.dot')
self.dfa_intersection_2_test_02 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_intersection_2_test_02.dot')
self.dfa_test_disjoint_full = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s3', 't2'),
('s3', 't3'),
('s0', 't3'),
('s2', 't3'),
('s2', 't0'),
('s1', 't2'),
('s0', 't0'),
('s1', 't4'),
('s0', 't1'),
('s0', 't5'),
('s2', 't1'),
('s2', 't5'),
('s3', 't4'),
('s3', 't0'),
('s0', 't2'),
('s2', 't2'),
('s1', 't0'),
('s1', 't3'),
('s1', 't5'),
('s3', 't1'),
('s0', 't4'),
('s2', 't4'),
('s3', 't5'),
('s1', 't1')
},
'initial_state': ('s0', 't0'),
'accepting_states': {('s0', 't5'), ('s0', 't4')},
'transitions': {
(('s3', 't3'), 'gum'): ('s0', 't1'),
(('s0', 't1'), '10c'): ('s2', 't2'),
(('s3', 't2'), 'gum'): ('s0', 't4'),
(('s0', 't1'), '5c'): ('s1', 't5'),
(('s2', 't1'), '10c'): ('s3', 't2'),
(('s1', 't0'), '5c'): ('s2', 't1'),
(('s1', 't1'), '10c'): ('s3', 't2'),
(('s2', 't0'), '5c'): ('s3', 't1'),
(('s0', 't2'), '5c'): ('s1', 't3'),
(('s1', 't1'), '5c'): ('s2', 't5'),
(('s3', 't5'), 'gum'): ('s0', 't0'),
(('s1', 't2'), '5c'): ('s2', 't3'),
(('s2', 't2'), '5c'): ('s3', 't3'),
(('s2', 't1'), '5c'): ('s3', 't5'),
(('s0', 't0'), '5c'): ('s1', 't1')
}
}
self.dfa_test_disjoint = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s0', 't0'),
('s0', 't4'),
('s1', 't1'),
('s2', 't5'),
('s3', 't2')
},
'initial_state': ('s0', 't0'),
'accepting_states': {('s0', 't4')},
'transitions': {
(('s3', 't2'), 'gum'): ('s0', 't4'),
(('s1', 't1'), '10c'): ('s3', 't2'),
(('s1', 't1'), '5c'): ('s2', 't5'),
(('s0', 't0'), '5c'): ('s1', 't1')
}
}
self.dfa_test_intersecting_full = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s1', 'c2'), ('c3', 't2'), ('c2', 'c3'),
('c1', 'c1'), ('s1', 't2'), ('c1', 't2'), ('c3', 'c2'),
('s1', 't0'), ('c1', 'c2'), ('c2', 't1'),
('s0', 'c2'), ('c3', 't0'), ('s0', 't2'), ('s0', 'c4'),
('c4', 't2'), ('c3', 't1'), ('c4', 'c2'),
('s1', 't1'), ('c1', 'c3'), ('c2', 'c1'), ('s0', 't3'),
('c2', 'c4'), ('c4', 't0'), ('s0', 'c1'),
('s0', 't0'), ('c1', 't3'), ('c4', 't3'), ('c3', 'c1'),
('c4', 'c3'), ('c4', 't1'), ('c3', 'c4'),
('s1', 'c1'), ('s1', 'c4'), ('c1', 'c4'), ('c1', 't0'),
('s0', 't1'), ('s1', 't3'), ('s1', 'c3'),
('c1', 't1'), ('c3', 't3'), ('c2', 'c2'), ('c4', 'c1'),
('c3', 'c3'), ('c2', 't2'), ('c4', 'c4'),
('c2', 't0'), ('s0', 'c3'), ('c2', 't3')
},
'initial_state': ('s0', 't0'),
'accepting_states': {('s1', 'c4'), ('s1', 't3'),
('c4', 't3'), ('c4', 'c4')},
'transitions': {
(('c2', 't2'), 'gum'): ('c4', 't0'),
(('s0', 't0'), '5c'): ('c1', 'c1'),
(('s0', 'c3'), 'gum'): ('s1', 'c1'),
(('s0', 'c2'), '5c'): ('c1', 'c3'),
(('s0', 't1'), '5c'): ('c1', 't2'),
(('c1', 'c1'), '10c'): ('c2', 'c2'),
(('c2', 't1'), '5c'): ('c3', 't2'),
(('c1', 't0'), '10c'): ('c2', 't1'),
(('c3', 't2'), 'gum'): ('c1', 't0'),
(('s0', 't1'), 'gum'): ('s1', 't3'),
(('c2', 'c2'), 'gum'): ('c4', 'c4'),
(('s0', 't2'), 'gum'): ('s1', 't0'),
(('c3', 'c3'), 'gum'): ('c1', 'c1'),
(('c2', 'c3'), 'gum'): ('c4', 'c1'),
(('c2', 'c2'), '5c'): ('c3', 'c3'),
(('s0', 'c2'), 'gum'): ('s1', 'c4'),
(('c3', 't1'), 'gum'): ('c1', 't3'),
(('c2', 't1'), 'gum'): ('c4', 't3'),
(('c3', 'c2'), 'gum'): ('c1', 'c4'),
(('c2', 't0'), '5c'): ('c3', 'c1')
}
}
self.dfa_test_intersecting = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s0', 't0'),
('c1', 'c1'),
('c2', 'c2'),
('c3', 'c3'),
('c4', 'c4')
},
'initial_state': ('s0', 't0'),
'accepting_states': {('c4', 'c4')},
'transitions': {
(('s0', 't0'), '5c'): ('c1', 'c1'),
(('c1', 'c1'), '10c'): ('c2', 'c2'),
(('c2', 'c2'), 'gum'): ('c4', 'c4'),
(('c3', 'c3'), 'gum'): ('c1', 'c1'),
(('c2', 'c2'), '5c'): ('c3', 'c3')
}
}
self.dfa_test_equals_full = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s1', 's0'), ('s0', 's1'), ('s3', 's3'),
('s2', 's2'), ('s0', 's0'), ('s1', 's1'), ('s1', 's3'),
('s0', 's3'), ('s1', 's2'), ('s2', 's3'),
('s0', 's2'), ('s2', 's0'), ('s2', 's1'), ('s3', 's0'),
('s3', 's1'), ('s3', 's2')
},
'initial_state': ('s0', 's0'),
'accepting_states': {('s0', 's0')},
'transitions': {
(('s1', 's0'), '10c'): ('s3', 's2'),
(('s0', 's1'), '10c'): ('s2', 's3'),
(('s1', 's1'), '10c'): ('s3', 's3'),
(('s0', 's2'), '5c'): ('s1', 's3'),
(('s2', 's2'), '5c'): ('s3', 's3'),
(('s2', 's2'), '10c'): ('s3', 's3'),
(('s0', 's0'), '10c'): ('s2', 's2'),
(('s1', 's2'), '5c'): ('s2', 's3'),
(('s2', 's1'), '10c'): ('s3', 's3'),
(('s0', 's2'), '10c'): ('s2', 's3'),
(('s2', 's0'), '5c'): ('s3', 's1'),
(('s2', 's0'), '10c'): ('s3', 's2'),
(('s2', 's1'), '5c'): ('s3', 's2'),
(('s1', 's0'), '5c'): ('s2', 's1'),
(('s0', 's1'), '5c'): ('s1', 's2'),
(('s3', 's3'), 'gum'): ('s0', 's0'),
(('s1', 's1'), '5c'): ('s2', 's2'),
(('s1', 's2'), '10c'): ('s3', 's3'),
(('s0', 's0'), '5c'): ('s1', 's1')
}
}
self.dfa_test_equals = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s3', 's3'),
('s2', 's2'),
('s0', 's0'),
('s1', 's1')
},
'initial_state': ('s0', 's0'),
'accepting_states': {('s0', 's0')},
'transitions': {
(('s1', 's1'), '10c'): ('s3', 's3'),
(('s2', 's2'), '5c'): ('s3', 's3'),
(('s2', 's2'), '10c'): ('s3', 's3'),
(('s0', 's0'), '10c'): ('s2', 's2'),
(('s3', 's3'), 'gum'): ('s0', 's0'),
(('s1', 's1'), '5c'): ('s2', 's2'),
(('s0', 's0'), '5c'): ('s1', 's1')
}
}
self.dfa_test_side_effect_1 = {
'alphabet': {'5c', '10c', 'gum'},
'states': {'s0', 's1', 's2', 's3'},
'initial_state': 's0',
'accepting_states': {'s0'},
'transitions': {('s0', '5c'): 's1',
('s0', '10c'): 's2',
('s1', '5c'): 's2',
('s1', '10c'): 's3',
('s2', '5c'): 's3',
('s2', '10c'): 's3',
('s3', 'gum'): 's0'}
}
self.dfa_test_side_effect_2 = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s3', 't2'),
('s3', 't3'),
('s0', 't3'),
('s2', 't3'),
('s2', 't0'),
('s1', 't2'),
('s0', 't0'),
('s1', 't4'),
('s0', 't1'),
('s0', 't5'),
('s2', 't1'),
('s2', 't5'),
('s3', 't4'),
('s3', 't0'),
('s0', 't2'),
('s2', 't2'),
('s1', 't0'),
('s1', 't3'),
('s1', 't5'),
('s3', 't1'),
('s0', 't4'),
('s2', 't4'),
('s3', 't5'),
('s1', 't1')
},
'initial_state': ('s0', 't0'),
'accepting_states': {('s0', 't5'), ('s0', 't4')},
'transitions': {
(('s3', 't3'), 'gum'): ('s0', 't1'),
(('s0', 't1'), '10c'): ('s2', 't2'),
(('s3', 't2'), 'gum'): ('s0', 't4'),
(('s0', 't1'), '5c'): ('s1', 't5'),
(('s2', 't1'), '10c'): ('s3', 't2'),
(('s1', 't0'), '5c'): ('s2', 't1'),
(('s1', 't1'), '10c'): ('s3', 't2'),
(('s2', 't0'), '5c'): ('s3', 't1'),
(('s0', 't2'), '5c'): ('s1', 't3'),
(('s1', 't1'), '5c'): ('s2', 't5'),
(('s3', 't5'), 'gum'): ('s0', 't0'),
(('s1', 't2'), '5c'): ('s2', 't3'),
(('s2', 't2'), '5c'): ('s3', 't3'),
(('s2', 't1'), '5c'): ('s3', 't5'),
(('s0', 't0'), '5c'): ('s1', 't1')
}
}
[docs] def test_dfa_intersection_disjoint(self):
""" Tests a correct intersection between disjointed DFAs """
intersection = DFA.dfa_intersection(self.dfa_intersection_1_test_01,
self.dfa_intersection_2_test_01)
self.assertTrue(intersection['states'].issubset(
self.dfa_test_disjoint_full['states']))
self.assertTrue(intersection['accepting_states'].issubset(
self.dfa_test_disjoint_full['accepting_states']))
self.assertDictEqual(intersection, self.dfa_test_disjoint)
[docs] def test_dfa_intersection_intersecting(self):
""" Tests a correct intersection between DFAs partially
intersected"""
intersection = DFA.dfa_intersection(self.dfa_intersection_1_test_02,
self.dfa_intersection_2_test_02)
self.assertDictEqual(intersection, self.dfa_test_intersecting)
[docs] def test_dfa_intersection_equals(self):
""" Tests a correct intersection between the same DFA """
intersection = DFA.dfa_intersection(self.dfa_intersection_1_test_01,
self.dfa_intersection_1_test_01)
automata_IO.dfa_to_dot(intersection,
'intersection_same',
'./tests/outputs')
self.assertDictEqual(intersection, self.dfa_test_equals)
[docs] @unittest.expectedFailure
def test_dfa_intersection_wrong_dict_1(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_intersection({'goofy': 'donald'},
self.dfa_intersection_2_test_01)
[docs] @unittest.expectedFailure
def test_dfa_intersection_wrong_dict_2(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_intersection(self.dfa_intersection_1_test_01,
{'goofy': 'donald'})
[docs] def test_dfa_intersection_side_effects_alphabet(self):
""" Tests that the intersection function doesn't make
side effects on input DFAs alphabet"""
intersection = DFA.dfa_intersection(
self.dfa_test_side_effect_1,
self.dfa_test_side_effect_2)
self.dfa_test_side_effect_1['alphabet'].pop()
self.dfa_test_side_effect_2['alphabet'].pop()
self.assertNotEquals(
self.dfa_test_side_effect_1['alphabet'],
intersection['alphabet'])
[docs] def test_dfa_intersection_side_effects_initial_state(self):
""" Tests that the intersection function doesn't make
side effects on input DFAs initial state"""
intersection = DFA.dfa_intersection(
self.dfa_test_side_effect_1,
self.dfa_test_side_effect_2)
self.dfa_test_side_effect_1['initial_state'] = 'pippo'
result = self.dfa_test_side_effect_1['initial_state'] in \
intersection['initial_state']
self.assertFalse(result)
[docs]class TestDfaUnion(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_union_1_test_01 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_union_1_test_01.dot')
self.dfa_union_2_test_01 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_union_2_test_01.dot')
self.dfa_union_1_test_02 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_union_1_test_02.dot')
self.dfa_union_2_test_02 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_union_2_test_02.dot')
self.dfa_test_disjoint_full = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s3', 't4'), ('s2', 't5'), ('s0', 't5'),
('s1', 't0'), ('s0', 't1'), ('sink', 'sink'),
('s2', 't3'), ('s3', 't0'), ('sink', 't4'),
('sink', 't3'), ('s3', 'sink'), ('s1', 't5'),
('s3', 't2'), ('s1', 'sink'), ('s3', 't5'),
('s2', 't0'), ('s0', 't4'), ('s1', 't3'),
('s2', 't4'), ('s0', 't2'), ('sink', 't1'),
('sink', 't5'), ('s2', 't2'), ('s0', 'sink'),
('s2', 'sink'), ('sink', 't2'), ('s2', 't1'),
('s1', 't1'), ('s0', 't0'), ('sink', 't0'),
('s3', 't1'), ('s1', 't2'), ('s3', 't3'),
('s0', 't3'), ('s1', 't4')
},
'initial_state': ('s0', 't0'),
'accepting_states': {
('s2', 't4'), ('s3', 't4'), ('s0', 't2'),
('s0', 't5'), ('s0', 't1'), ('s2', 't5'),
('s0', 'sink'),
('sink', 't5'), ('sink', 't4'), ('s0', 't0'),
('s1', 't5'), ('s3', 't5'), ('s0', 't4'), ('s0', 't3'),
('s1', 't4')
},
'transitions': {
(('s3', 't3'), '10c'): ('sink', 'sink'),
(('s3', 't2'), '5c'): ('sink', 't3'),
(('s1', 't2'), '5c'): ('s2', 't3'),
(('s3', 't5'), '10c'): ('sink', 'sink'),
(('s0', 't0'), '10c'): ('s2', 'sink'),
(('sink', 't0'), '5c'): ('sink', 't1'),
(('sink', 't3'), '10c'): ('sink', 'sink'),
(('sink', 't1'), '5c'): ('sink', 't5'),
(('s2', 't2'), '10c'): ('s3', 'sink'),
(('s1', 't5'), '10c'): ('s3', 'sink'),
(('sink', 't3'), '5c'): ('sink', 'sink'),
(('sink', 't5'), 'gum'): ('sink', 't0'),
(('s0', 't1'), '10c'): ('s2', 't2'),
(('s3', 't1'), '10c'): ('sink', 't2'),
(('sink', 't5'), '5c'): ('sink', 'sink'),
(('s2', 't1'), '10c'): ('s3', 't2'),
(('s2', 't1'), '5c'): ('s3', 't5'),
(('sink', 't1'), 'gum'): ('sink', 'sink'),
(('sink', 't2'), '5c'): ('sink', 't3'),
(('s0', 't4'), '10c'): ('s2', 'sink'),
(('s3', 't0'), '10c'): ('sink', 'sink'),
(('s2', 'sink'), '10c'): ('s3', 'sink'),
(('s0', 't2'), 'gum'): ('sink', 't4'),
(('s3', 't4'), '10c'): ('sink', 'sink'),
(('s0', 't3'), '10c'): ('s2', 'sink'),
(('s0', 't3'), '5c'): ('s1', 'sink'),
(('s3', 't3'), 'gum'): ('s0', 't1'),
(('sink', 't2'), 'gum'): ('sink', 't4'),
(('s3', 't5'), '5c'): ('sink', 'sink'),
(('s1', 'sink'), 'gum'): ('sink', 'sink'),
(('s2', 't4'), '10c'): ('s3', 'sink'),
(('s3', 'sink'), 'gum'): ('s0', 'sink'),
(('s1', 't1'), '5c'): ('s2', 't5'),
(('s1', 't0'), 'gum'): ('sink', 'sink'),
(('s0', 'sink'), '10c'): ('s2', 'sink'),
(('sink', 't5'), '10c'): ('sink', 'sink'),
(('s0', 't1'), '5c'): ('s1', 't5'),
(('s0', 't0'), 'gum'): ('sink', 'sink'),
(('sink', 't4'), '5c'): ('sink', 'sink'),
(('sink', 't3'), 'gum'): ('sink', 't1'),
(('s1', 't4'), '10c'): ('s3', 'sink'),
(('s0', 't5'), 'gum'): ('sink', 't0'),
(('s1', 't2'), 'gum'): ('sink', 't4'),
(('sink', 't0'), 'gum'): ('sink', 'sink'),
(('s3', 't2'), 'gum'): ('s0', 't4'),
(('s1', 't2'), '10c'): ('s3', 'sink'),
(('s2', 't5'), 'gum'): ('sink', 't0'),
(('s2', 't4'), '5c'): ('s3', 'sink'),
(('s0', 't2'), '10c'): ('s2', 'sink'),
(('s2', 't0'), '10c'): ('s3', 'sink'),
(('sink', 'sink'), '5c'): ('sink', 'sink'),
(('s1', 't4'), '5c'): ('s2', 'sink'),
(('s1', 't1'), '10c'): ('s3', 't2'),
(('s2', 't2'), '5c'): ('s3', 't3'),
(('sink', 't1'), '10c'): ('sink', 't2'),
(('s0', 't4'), 'gum'): ('sink', 'sink'),
(('s3', 't0'), 'gum'): ('s0', 'sink'),
(('sink', 't4'), '10c'): ('sink', 'sink'),
(('s2', 'sink'), 'gum'): ('sink', 'sink'),
(('s2', 't3'), '5c'): ('s3', 'sink'),
(('s3', 't4'), 'gum'): ('s0', 'sink'),
(('s1', 't0'), '10c'): ('s3', 'sink'),
(('s0', 'sink'), 'gum'): ('sink', 'sink'),
(('s3', 't1'), '5c'): ('sink', 't5'),
(('s2', 't3'), 'gum'): ('sink', 't1'),
(('sink', 't2'), '10c'): ('sink', 'sink'),
(('s1', 'sink'), '10c'): ('s3', 'sink'),
(('s3', 't5'), 'gum'): ('s0', 't0'),
(('s0', 't3'), 'gum'): ('sink', 't1'),
(('s2', 't2'), 'gum'): ('sink', 't4'),
(('s3', 'sink'), '10c'): ('sink', 'sink'),
(('s1', 't5'), 'gum'): ('sink', 't0'),
(('s2', 't0'), '5c'): ('s3', 't1'),
(('sink', 'sink'), 'gum'): ('sink', 'sink'),
(('s1', 't3'), '10c'): ('s3', 'sink'),
(('s3', 't2'), '10c'): ('sink', 'sink'),
(('s2', 't5'), '10c'): ('s3', 'sink'),
(('s2', 't5'), '5c'): ('s3', 'sink'),
(('s2', 't0'), 'gum'): ('sink', 'sink'),
(('s1', 't5'), '5c'): ('s2', 'sink'),
(('s2', 't1'), 'gum'): ('sink', 'sink'),
(('s0', 't5'), '5c'): ('s1', 'sink'),
(('s0', 't5'), '10c'): ('s2', 'sink'),
(('sink', 't0'), '10c'): ('sink', 'sink'),
(('s1', 't4'), 'gum'): ('sink', 'sink'),
(('sink', 't4'), 'gum'): ('sink', 'sink'),
(('s0', 't0'), '5c'): ('s1', 't1'),
(('s0', 't1'), 'gum'): ('sink', 'sink'),
(('s3', 't1'), 'gum'): ('s0', 'sink'),
(('s0', 'sink'), '5c'): ('s1', 'sink'),
(('s3', 't4'), '5c'): ('sink', 'sink'),
(('s3', 'sink'), '5c'): ('sink', 'sink'),
(('s1', 't0'), '5c'): ('s2', 't1'),
(('s1', 't1'), 'gum'): ('sink', 'sink'),
(('s2', 'sink'), '5c'): ('s3', 'sink'),
(('s2', 't3'), '10c'): ('s3', 'sink'),
(('s1', 't3'), 'gum'): ('sink', 't1'),
(('s0', 't4'), '5c'): ('s1', 'sink'),
(('s1', 'sink'), '5c'): ('s2', 'sink'),
(('s1', 't3'), '5c'): ('s2', 'sink'),
(('s3', 't3'), '5c'): ('sink', 'sink'),
(('s3', 't0'), '5c'): ('sink', 't1'),
(('sink', 'sink'), '10c'): ('sink', 'sink'),
(('s2', 't4'), 'gum'): ('sink', 'sink'),
(('s0', 't2'), '5c'): ('s1', 't3')
}
}
self.dfa_test_disjoint = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s3', 't4'), ('s2', 't5'), ('s0', 't5'),
('s1', 't0'), ('s0', 't1'), ('sink', 'sink'),
('s2', 't3'), ('s3', 't0'), ('sink', 't4'),
('sink', 't3'), ('s3', 'sink'), ('s1', 't5'),
('s3', 't2'), ('s1', 'sink'), ('s3', 't5'),
('s2', 't0'), ('s0', 't4'), ('s1', 't3'),
('s2', 't4'), ('s0', 't2'), ('sink', 't1'),
('sink', 't5'), ('s2', 't2'), ('s0', 'sink'),
('s2', 'sink'), ('sink', 't2'), ('s2', 't1'),
('s1', 't1'), ('s0', 't0'), ('sink', 't0'),
('s3', 't1'), ('s1', 't2'), ('s3', 't3'),
('s0', 't3'), ('s1', 't4')
},
'initial_state': ('s0', 't0'),
'accepting_states': {
('s2', 't4'), ('s3', 't4'), ('s0', 't2'),
('s0', 't5'), ('s0', 't1'), ('s2', 't5'),
('s0', 'sink'),
('sink', 't5'), ('sink', 't4'), ('s0', 't0'),
('s1', 't5'), ('s3', 't5'), ('s0', 't4'), ('s0', 't3'),
('s1', 't4')
},
'transitions': {
(('s3', 't3'), '10c'): ('sink', 'sink'),
(('s3', 't2'), '5c'): ('sink', 't3'),
(('s1', 't2'), '5c'): ('s2', 't3'),
(('s3', 't5'), '10c'): ('sink', 'sink'),
(('s0', 't0'), '10c'): ('s2', 'sink'),
(('sink', 't0'), '5c'): ('sink', 't1'),
(('sink', 't3'), '10c'): ('sink', 'sink'),
(('sink', 't1'), '5c'): ('sink', 't5'),
(('s2', 't2'), '10c'): ('s3', 'sink'),
(('s1', 't5'), '10c'): ('s3', 'sink'),
(('sink', 't3'), '5c'): ('sink', 'sink'),
(('sink', 't5'), 'gum'): ('sink', 't0'),
(('s0', 't1'), '10c'): ('s2', 't2'),
(('s3', 't1'), '10c'): ('sink', 't2'),
(('sink', 't5'), '5c'): ('sink', 'sink'),
(('s2', 't1'), '10c'): ('s3', 't2'),
(('s2', 't1'), '5c'): ('s3', 't5'),
(('sink', 't1'), 'gum'): ('sink', 'sink'),
(('sink', 't2'), '5c'): ('sink', 't3'),
(('s0', 't4'), '10c'): ('s2', 'sink'),
(('s3', 't0'), '10c'): ('sink', 'sink'),
(('s2', 'sink'), '10c'): ('s3', 'sink'),
(('s0', 't2'), 'gum'): ('sink', 't4'),
(('s3', 't4'), '10c'): ('sink', 'sink'),
(('s0', 't3'), '10c'): ('s2', 'sink'),
(('s0', 't3'), '5c'): ('s1', 'sink'),
(('s3', 't3'), 'gum'): ('s0', 't1'),
(('sink', 't2'), 'gum'): ('sink', 't4'),
(('s3', 't5'), '5c'): ('sink', 'sink'),
(('s1', 'sink'), 'gum'): ('sink', 'sink'),
(('s2', 't4'), '10c'): ('s3', 'sink'),
(('s3', 'sink'), 'gum'): ('s0', 'sink'),
(('s1', 't1'), '5c'): ('s2', 't5'),
(('s1', 't0'), 'gum'): ('sink', 'sink'),
(('s0', 'sink'), '10c'): ('s2', 'sink'),
(('sink', 't5'), '10c'): ('sink', 'sink'),
(('s0', 't1'), '5c'): ('s1', 't5'),
(('s0', 't0'), 'gum'): ('sink', 'sink'),
(('sink', 't4'), '5c'): ('sink', 'sink'),
(('sink', 't3'), 'gum'): ('sink', 't1'),
(('s1', 't4'), '10c'): ('s3', 'sink'),
(('s0', 't5'), 'gum'): ('sink', 't0'),
(('s1', 't2'), 'gum'): ('sink', 't4'),
(('sink', 't0'), 'gum'): ('sink', 'sink'),
(('s3', 't2'), 'gum'): ('s0', 't4'),
(('s1', 't2'), '10c'): ('s3', 'sink'),
(('s2', 't5'), 'gum'): ('sink', 't0'),
(('s2', 't4'), '5c'): ('s3', 'sink'),
(('s0', 't2'), '10c'): ('s2', 'sink'),
(('s2', 't0'), '10c'): ('s3', 'sink'),
(('sink', 'sink'), '5c'): ('sink', 'sink'),
(('s1', 't4'), '5c'): ('s2', 'sink'),
(('s1', 't1'), '10c'): ('s3', 't2'),
(('s2', 't2'), '5c'): ('s3', 't3'),
(('sink', 't1'), '10c'): ('sink', 't2'),
(('s0', 't4'), 'gum'): ('sink', 'sink'),
(('s3', 't0'), 'gum'): ('s0', 'sink'),
(('sink', 't4'), '10c'): ('sink', 'sink'),
(('s2', 'sink'), 'gum'): ('sink', 'sink'),
(('s2', 't3'), '5c'): ('s3', 'sink'),
(('s3', 't4'), 'gum'): ('s0', 'sink'),
(('s1', 't0'), '10c'): ('s3', 'sink'),
(('s0', 'sink'), 'gum'): ('sink', 'sink'),
(('s3', 't1'), '5c'): ('sink', 't5'),
(('s2', 't3'), 'gum'): ('sink', 't1'),
(('sink', 't2'), '10c'): ('sink', 'sink'),
(('s1', 'sink'), '10c'): ('s3', 'sink'),
(('s3', 't5'), 'gum'): ('s0', 't0'),
(('s0', 't3'), 'gum'): ('sink', 't1'),
(('s2', 't2'), 'gum'): ('sink', 't4'),
(('s3', 'sink'), '10c'): ('sink', 'sink'),
(('s1', 't5'), 'gum'): ('sink', 't0'),
(('s2', 't0'), '5c'): ('s3', 't1'),
(('sink', 'sink'), 'gum'): ('sink', 'sink'),
(('s1', 't3'), '10c'): ('s3', 'sink'),
(('s3', 't2'), '10c'): ('sink', 'sink'),
(('s2', 't5'), '10c'): ('s3', 'sink'),
(('s2', 't5'), '5c'): ('s3', 'sink'),
(('s2', 't0'), 'gum'): ('sink', 'sink'),
(('s1', 't5'), '5c'): ('s2', 'sink'),
(('s2', 't1'), 'gum'): ('sink', 'sink'),
(('s0', 't5'), '5c'): ('s1', 'sink'),
(('s0', 't5'), '10c'): ('s2', 'sink'),
(('sink', 't0'), '10c'): ('sink', 'sink'),
(('s1', 't4'), 'gum'): ('sink', 'sink'),
(('sink', 't4'), 'gum'): ('sink', 'sink'),
(('s0', 't0'), '5c'): ('s1', 't1'),
(('s0', 't1'), 'gum'): ('sink', 'sink'),
(('s3', 't1'), 'gum'): ('s0', 'sink'),
(('s0', 'sink'), '5c'): ('s1', 'sink'),
(('s3', 't4'), '5c'): ('sink', 'sink'),
(('s3', 'sink'), '5c'): ('sink', 'sink'),
(('s1', 't0'), '5c'): ('s2', 't1'),
(('s1', 't1'), 'gum'): ('sink', 'sink'),
(('s2', 'sink'), '5c'): ('s3', 'sink'),
(('s2', 't3'), '10c'): ('s3', 'sink'),
(('s1', 't3'), 'gum'): ('sink', 't1'),
(('s0', 't4'), '5c'): ('s1', 'sink'),
(('s1', 'sink'), '5c'): ('s2', 'sink'),
(('s1', 't3'), '5c'): ('s2', 'sink'),
(('s3', 't3'), '5c'): ('sink', 'sink'),
(('s3', 't0'), '5c'): ('sink', 't1'),
(('sink', 'sink'), '10c'): ('sink', 'sink'),
(('s2', 't4'), 'gum'): ('sink', 'sink'),
(('s0', 't2'), '5c'): ('s1', 't3')
}
}
self.dfa_test_intersecting = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('c4', 'c2'), ('sink', 't0'), ('s0', 'c3'),
('s0', 't1'), ('sink', 'sink'), ('c2', 'c2'),
('c3', 'sink'), ('c1', 't2'), ('s0', 'c4'),
('c3', 't2'), ('s0', 't2'), ('s0', 't0'),
('s1', 't2'), ('s1', 'c4'), ('sink', 't3'),
('s1', 't0'), ('c3', 't1'), ('c2', 't1'),
('c1', 'c4'), ('c3', 'c1'), ('c3', 't0'),
('sink', 'c3'), ('c4', 't2'), ('c1', 't0'),
('c2', 'c1'), ('sink', 'c4'), ('c2', 't2'),
('c2', 't0'), ('c2', 'sink'), ('c3', 'c2'),
('c4', 't0'), ('sink', 'c2'), ('s1', 'c2'),
('c4', 't1'), ('c4', 'c4'), ('c4', 't3'),
('s0', 'c1'), ('c1', 'c2'), ('c1', 'sink'),
('c2', 't3'), ('c4', 'c3'), ('s1', 't3'),
('s0', 'sink'), ('sink', 't1'), ('s1', 'sink'),
('c2', 'c3'), ('c4', 'sink'), ('c1', 'c1'),
('c3', 'c3'), ('s0', 'c2'), ('c1', 't3'),
('s1', 'c3'), ('c1', 't1'), ('c2', 'c4'), ('c3', 't3'),
('c3', 'c4'), ('s1', 'c1'), ('c4', 'c1'),
('sink', 'c1'), ('s0', 't3'), ('c1', 'c3'),
('s1', 't1'), ('sink', 't2')
},
'initial_state': ('s0', 't0'),
'accepting_states': {
('c4', 'c2'), ('c4', 't0'), ('s1', 'c2'),
('c4', 't1'), ('c4', 'c4'), ('c4', 't3'),
('s0', 'c4'), ('c2', 't3'), ('c4', 'c3'),
('s1', 't2'), ('s1', 'c4'), ('sink', 't3'),
('s1', 'sink'), ('s1', 't0'), ('c4', 'sink'),
('c1', 'c4'), ('c4', 't2'), ('s1', 'c3'),
('c1', 't3'), ('c2', 'c4'), ('s1', 'c1'),
('c3', 't3'), ('c3', 'c4'), ('c4', 'c1'),
('sink', 'c4'), ('s0', 't3'), ('s1', 't3'),
('s1', 't1')
},
'transitions': {
(('s1', 'c2'), 'gum'): ('sink', 'c4'),
(('sink', 't3'), '5c'): ('sink', 'sink'),
(('s1', 'sink'), 'gum'): ('sink', 'sink'),
(('s0', 'sink'), 'gum'): ('s1', 'sink'),
(('c4', 't2'), 'gum'): ('sink', 't0'),
(('s1', 'c3'), '10c'): ('sink', 'sink'),
(('c2', 't0'), '5c'): ('c3', 'c1'),
(('s1', 't3'), '5c'): ('sink', 'sink'),
(('s1', 't2'), 'gum'): ('sink', 't0'),
(('c3', 't0'), '5c'): ('sink', 'c1'),
(('c2', 't0'), '10c'): ('sink', 't1'),
(('c2', 'c2'), '5c'): ('c3', 'c3'),
(('s0', 'c2'), '5c'): ('c1', 'c3'),
(('sink', 't3'), 'gum'): ('sink', 'sink'),
(('sink', 't1'), 'gum'): ('sink', 't3'),
(('c3', 'c4'), '5c'): ('sink', 'sink'),
(('c4', 't0'), '10c'): ('sink', 't1'),
(('c4', 'c1'), '10c'): ('sink', 'c2'),
(('s1', 'c1'), '10c'): ('sink', 'c2'),
(('s1', 'c3'), 'gum'): ('sink', 'c1'),
(('c1', 'c1'), '10c'): ('c2', 'c2'),
(('c3', 't2'), 'gum'): ('c1', 't0'),
(('c4', 'c1'), '5c'): ('sink', 'sink'),
(('s1', 'c1'), '5c'): ('sink', 'sink'),
(('c2', 't3'), 'gum'): ('c4', 'sink'),
(('c4', 't3'), '10c'): ('sink', 'sink'),
(('sink', 'sink'), '5c'): ('sink', 'sink'),
(('c3', 't3'), 'gum'): ('c1', 'sink'),
(('c1', 't3'), '10c'): ('c2', 'sink'),
(('sink', 'c2'), '5c'): ('sink', 'c3'),
(('s1', 'c2'), '10c'): ('sink', 'sink'),
(('c4', 't3'), '5c'): ('sink', 'sink'),
(('s0', 'c2'), '10c'): ('sink', 'sink'),
(('s1', 't0'), '5c'): ('sink', 'c1'),
(('c4', 't3'), 'gum'): ('sink', 'sink'),
(('c3', 't2'), '5c'): ('sink', 'sink'),
(('c3', 't0'), 'gum'): ('c1', 'sink'),
(('s0', 't0'), '5c'): ('c1', 'c1'),
(('s0', 't2'), '10c'): ('sink', 'sink'),
(('sink', 'c4'), '10c'): ('sink', 'sink'),
(('s0', 'c3'), '10c'): ('sink', 'sink'),
(('s1', 't0'), '10c'): ('sink', 't1'),
(('sink', 't3'), '10c'): ('sink', 'sink'),
(('c1', 't0'), '5c'): ('sink', 'c1'),
(('c4', 'c1'), 'gum'): ('sink', 'sink'),
(('s0', 't2'), '5c'): ('c1', 'sink'),
(('c2', 'c4'), '5c'): ('c3', 'sink'),
(('s0', 't1'), 'gum'): ('s1', 't3'),
(('c4', 'c2'), 'gum'): ('sink', 'c4'),
(('c2', 'c1'), '10c'): ('sink', 'c2'),
(('sink', 't1'), '5c'): ('sink', 't2'),
(('sink', 'c1'), '5c'): ('sink', 'sink'),
(('c1', 'sink'), 'gum'): ('sink', 'sink'),
(('c2', 'c4'), '10c'): ('sink', 'sink'),
(('c2', 'c2'), 'gum'): ('c4', 'c4'),
(('s1', 'c4'), '5c'): ('sink', 'sink'),
(('c1', 't2'), 'gum'): ('sink', 't0'),
(('c1', 'c4'), '10c'): ('c2', 'sink'),
(('c2', 'sink'), 'gum'): ('c4', 'sink'),
(('s0', 'c4'), '5c'): ('c1', 'sink'),
(('s0', 'c3'), 'gum'): ('s1', 'c1'),
(('s1', 't0'), 'gum'): ('sink', 'sink'),
(('c4', 'c3'), '5c'): ('sink', 'sink'),
(('c3', 'c3'), '5c'): ('sink', 'sink'),
(('c4', 'sink'), 'gum'): ('sink', 'sink'),
(('s1', 't2'), '5c'): ('sink', 'sink'),
(('c3', 't3'), '10c'): ('sink', 'sink'),
(('c1', 'c4'), '5c'): ('sink', 'sink'),
(('s0', 'sink'), '10c'): ('sink', 'sink'),
(('s1', 'sink'), '5c'): ('sink', 'sink'),
(('sink', 't0'), '10c'): ('sink', 't1'),
(('c3', 'sink'), '5c'): ('sink', 'sink'),
(('c3', 'c1'), '10c'): ('sink', 'c2'),
(('c4', 't2'), '5c'): ('sink', 'sink'),
(('c3', 'c3'), '10c'): ('sink', 'sink'),
(('c1', 't1'), '10c'): ('c2', 'sink'),
(('c3', 't3'), '5c'): ('sink', 'sink'),
(('sink', 't2'), 'gum'): ('sink', 't0'),
(('sink', 't0'), '5c'): ('sink', 'c1'),
(('c2', 't2'), '10c'): ('sink', 'sink'),
(('s1', 'c1'), 'gum'): ('sink', 'sink'),
(('s1', 'c4'), 'gum'): ('sink', 'sink'),
(('c2', 'sink'), '10c'): ('sink', 'sink'),
(('s0', 'c4'), 'gum'): ('s1', 'sink'),
(('c4', 'sink'), '10c'): ('sink', 'sink'),
(('s0', 't1'), '10c'): ('sink', 'sink'),
(('c4', 't0'), 'gum'): ('sink', 'sink'),
(('c2', 'sink'), '5c'): ('c3', 'sink'),
(('c2', 't1'), '5c'): ('c3', 't2'),
(('sink', 'c1'), '10c'): ('sink', 'c2'),
(('c1', 'c2'), '5c'): ('sink', 'c3'),
(('c1', 't3'), '5c'): ('sink', 'sink'),
(('sink', 'c3'), 'gum'): ('sink', 'c1'),
(('c2', 'c4'), 'gum'): ('c4', 'sink'),
(('c2', 'c3'), '5c'): ('c3', 'sink'),
(('c2', 't1'), '10c'): ('sink', 'sink'),
(('c1', 'c2'), '10c'): ('c2', 'sink'),
(('sink', 't2'), '5c'): ('sink', 'sink'),
(('c3', 'c4'), '10c'): ('sink', 'sink'),
(('c3', 't1'), 'gum'): ('c1', 't3'),
(('s1', 't3'), 'gum'): ('sink', 'sink'),
(('s0', 't2'), 'gum'): ('s1', 't0'),
(('sink', 'c4'), 'gum'): ('sink', 'sink'),
(('s0', 't3'), '10c'): ('sink', 'sink'),
(('c1', 'c3'), '5c'): ('sink', 'sink'),
(('c2', 'c3'), '10c'): ('sink', 'sink'),
(('sink', 't2'), '10c'): ('sink', 'sink'),
(('c1', 'c3'), '10c'): ('c2', 'sink'),
(('c4', 'c4'), 'gum'): ('sink', 'sink'),
(('sink', 'sink'), '10c'): ('sink', 'sink'),
(('c3', 'c3'), 'gum'): ('c1', 'c1'),
(('c4', 'c4'), '5c'): ('sink', 'sink'),
(('c3', 'c2'), '10c'): ('sink', 'sink'),
(('c3', 'sink'), '10c'): ('sink', 'sink'),
(('c1', 'c1'), '5c'): ('sink', 'sink'),
(('c2', 't3'), '10c'): ('sink', 'sink'),
(('s1', 'c2'), '5c'): ('sink', 'c3'),
(('c4', 'c3'), 'gum'): ('sink', 'c1'),
(('c3', 'c4'), 'gum'): ('c1', 'sink'),
(('c4', 'c4'), '10c'): ('sink', 'sink'),
(('c1', 't3'), 'gum'): ('sink', 'sink'),
(('c1', 'c4'), 'gum'): ('sink', 'sink'),
(('c3', 't1'), '5c'): ('sink', 't2'),
(('s0', 't0'), '10c'): ('sink', 't1'),
(('c4', 't1'), 'gum'): ('sink', 't3'),
(('c2', 't3'), '5c'): ('c3', 'sink'),
(('sink', 'c4'), '5c'): ('sink', 'sink'),
(('c2', 'c3'), 'gum'): ('c4', 'c1'),
(('c2', 'c2'), '10c'): ('sink', 'sink'),
(('s1', 't1'), 'gum'): ('sink', 't3'),
(('sink', 'c2'), '10c'): ('sink', 'sink'),
(('c3', 't1'), '10c'): ('sink', 'sink'),
(('s1', 't1'), '5c'): ('sink', 't2'),
(('c2', 'c1'), '5c'): ('c3', 'sink'),
(('c4', 't0'), '5c'): ('sink', 'c1'),
(('s0', 'c1'), '10c'): ('sink', 'c2'),
(('s1', 't1'), '10c'): ('sink', 'sink'),
(('s1', 'c4'), '10c'): ('sink', 'sink'),
(('s0', 't0'), 'gum'): ('s1', 'sink'),
(('sink', 'c1'), 'gum'): ('sink', 'sink'),
(('c1', 't0'), 'gum'): ('sink', 'sink'),
(('s0', 'c4'), '10c'): ('sink', 'sink'),
(('s0', 'c1'), '5c'): ('c1', 'sink'),
(('c2', 't1'), 'gum'): ('c4', 't3'),
(('c3', 't0'), '10c'): ('sink', 't1'),
(('c4', 'c3'), '10c'): ('sink', 'sink'),
(('sink', 'sink'), 'gum'): ('sink', 'sink'),
(('sink', 't0'), 'gum'): ('sink', 'sink'),
(('c3', 'c1'), 'gum'): ('c1', 'sink'),
(('s0', 'sink'), '5c'): ('c1', 'sink'),
(('s1', 't3'), '10c'): ('sink', 'sink'),
(('c3', 'c1'), '5c'): ('sink', 'sink'),
(('c1', 't1'), 'gum'): ('sink', 't3'),
(('c1', 't2'), '5c'): ('sink', 'sink'),
(('c3', 'sink'), 'gum'): ('c1', 'sink'),
(('c1', 't1'), '5c'): ('sink', 't2'),
(('c1', 'sink'), '5c'): ('sink', 'sink'),
(('s0', 'c3'), '5c'): ('c1', 'sink'),
(('c3', 'c2'), '5c'): ('sink', 'c3'),
(('c3', 'c2'), 'gum'): ('c1', 'c4'),
(('c1', 'c1'), 'gum'): ('sink', 'sink'),
(('c3', 't2'), '10c'): ('sink', 'sink'),
(('c1', 't0'), '10c'): ('c2', 't1'),
(('s0', 't3'), 'gum'): ('s1', 'sink'),
(('sink', 'c3'), '10c'): ('sink', 'sink'),
(('c1', 'sink'), '10c'): ('c2', 'sink'),
(('s0', 'c1'), 'gum'): ('s1', 'sink'),
(('sink', 't1'), '10c'): ('sink', 'sink'),
(('c4', 'sink'), '5c'): ('sink', 'sink'),
(('s0', 'c2'), 'gum'): ('s1', 'c4'),
(('c4', 'c2'), '10c'): ('sink', 'sink'),
(('sink', 'c3'), '5c'): ('sink', 'sink'),
(('c1', 'c3'), 'gum'): ('sink', 'c1'),
(('c4', 't1'), '5c'): ('sink', 't2'),
(('s1', 't2'), '10c'): ('sink', 'sink'),
(('c4', 'c2'), '5c'): ('sink', 'c3'),
(('c2', 'c1'), 'gum'): ('c4', 'sink'),
(('c2', 't0'), 'gum'): ('c4', 'sink'),
(('c1', 't2'), '10c'): ('c2', 'sink'),
(('c4', 't1'), '10c'): ('sink', 'sink'),
(('s0', 't3'), '5c'): ('c1', 'sink'),
(('s1', 'sink'), '10c'): ('sink', 'sink'),
(('sink', 'c2'), 'gum'): ('sink', 'c4'),
(('c2', 't2'), 'gum'): ('c4', 't0'),
(('c4', 't2'), '10c'): ('sink', 'sink'),
(('s0', 't1'), '5c'): ('c1', 't2'),
(('c2', 't2'), '5c'): ('c3', 'sink'),
(('c1', 'c2'), 'gum'): ('sink', 'c4'),
(('s1', 'c3'), '5c'): ('sink', 'sink')
}
}
self.dfa_test_equals = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s1', 's3'), ('s0', 'sink'), ('s0', 's3'),
('sink', 's0'), ('s0', 's1'), ('s2', 's0'),
('s2', 'sink'),
('s1', 'sink'), ('sink', 's1'), ('s2', 's3'),
('s0', 's0'), ('sink', 's3'), ('s3', 'sink'),
('s2', 's2'), ('s3', 's0'), ('s0', 's2'),
('s1', 's0'), ('sink', 's2'), ('s3', 's2'),
('s1', 's1'),
('s2', 's1'), ('s1', 's2'), ('s3', 's1'),
('s3', 's3'), ('sink', 'sink')
},
'initial_state': ('s0', 's0'),
'accepting_states': {
('s0', 'sink'), ('s0', 's3'), ('sink', 's0'),
('s0', 's1'), ('s0', 's0'), ('s2', 's0'),
('s3', 's0'), ('s0', 's2'), ('s1', 's0')
},
'transitions': {
(('s3', 'sink'), '5c'): ('sink', 'sink'),
(('s3', 's1'), '5c'): ('sink', 's2'),
(('s1', 's3'), '5c'): ('s2', 'sink'),
(('s0', 's1'), '5c'): ('s1', 's2'),
(('s3', 's3'), '5c'): ('sink', 'sink'),
(('s0', 's1'), '10c'): ('s2', 's3'),
(('s1', 's0'), 'gum'): ('sink', 'sink'),
(('sink', 's0'), 'gum'): ('sink', 'sink'),
(('s1', 's3'), 'gum'): ('sink', 's0'),
(('s1', 'sink'), '10c'): ('s3', 'sink'),
(('s3', 's2'), 'gum'): ('s0', 'sink'),
(('sink', 's2'), '5c'): ('sink', 's3'),
(('s3', 's0'), '10c'): ('sink', 's2'),
(('s2', 's0'), 'gum'): ('sink', 'sink'),
(('s3', 's2'), '10c'): ('sink', 's3'),
(('s2', 's2'), '10c'): ('s3', 's3'),
(('s2', 's1'), '10c'): ('s3', 's3'),
(('s2', 'sink'), '10c'): ('s3', 'sink'),
(('s0', 's2'), 'gum'): ('sink', 'sink'),
(('sink', 's2'), 'gum'): ('sink', 'sink'),
(('sink', 's3'), '5c'): ('sink', 'sink'),
(('sink', 's3'), '10c'): ('sink', 'sink'),
(('s0', 's3'), '10c'): ('s2', 'sink'),
(('s1', 's1'), '10c'): ('s3', 's3'),
(('s3', 's3'), '10c'): ('sink', 'sink'),
(('s0', 's1'), 'gum'): ('sink', 'sink'),
(('sink', 'sink'), 'gum'): ('sink', 'sink'),
(('s1', 'sink'), 'gum'): ('sink', 'sink'),
(('s2', 's2'), '5c'): ('s3', 's3'),
(('s3', 's0'), 'gum'): ('s0', 'sink'),
(('s2', 's3'), 'gum'): ('sink', 's0'),
(('s3', 's0'), '5c'): ('sink', 's1'),
(('s0', 'sink'), '5c'): ('s1', 'sink'),
(('s0', 'sink'), '10c'): ('s2', 'sink'),
(('s1', 'sink'), '5c'): ('s2', 'sink'),
(('s3', 's1'), 'gum'): ('s0', 'sink'),
(('s1', 's1'), '5c'): ('s2', 's2'),
(('sink', 's1'), '10c'): ('sink', 's3'),
(('s3', 'sink'), '10c'): ('sink', 'sink'),
(('s1', 's2'), '10c'): ('s3', 's3'),
(('s1', 's0'), '10c'): ('s3', 's2'),
(('s0', 's0'), '10c'): ('s2', 's2'),
(('s2', 's0'), '5c'): ('s3', 's1'),
(('s2', 'sink'), '5c'): ('s3', 'sink'),
(('s1', 's1'), 'gum'): ('sink', 'sink'),
(('s0', 's3'), 'gum'): ('sink', 's0'),
(('s2', 's1'), 'gum'): ('sink', 'sink'),
(('sink', 's0'), '5c'): ('sink', 's1'),
(('s0', 's3'), '5c'): ('s1', 'sink'),
(('sink', 's2'), '10c'): ('sink', 's3'),
(('s2', 'sink'), 'gum'): ('sink', 'sink'),
(('s2', 's1'), '5c'): ('s3', 's2'),
(('sink', 's3'), 'gum'): ('sink', 's0'),
(('s1', 's0'), '5c'): ('s2', 's1'),
(('s3', 's1'), '10c'): ('sink', 's3'),
(('s0', 's2'), '5c'): ('s1', 's3'),
(('s0', 's2'), '10c'): ('s2', 's3'),
(('s1', 's3'), '10c'): ('s3', 'sink'),
(('s2', 's0'), '10c'): ('s3', 's2'),
(('sink', 's1'), 'gum'): ('sink', 'sink'),
(('s2', 's2'), 'gum'): ('sink', 'sink'),
(('s0', 's0'), '5c'): ('s1', 's1'),
(('sink', 's0'), '10c'): ('sink', 's2'),
(('s1', 's2'), '5c'): ('s2', 's3'),
(('sink', 'sink'), '10c'): ('sink', 'sink'),
(('s3', 's3'), 'gum'): ('s0', 's0'),
(('s1', 's2'), 'gum'): ('sink', 'sink'),
(('s0', 's0'), 'gum'): ('sink', 'sink'),
(('s0', 'sink'), 'gum'): ('sink', 'sink'),
(('sink', 's1'), '5c'): ('sink', 's2'),
(('s3', 'sink'), 'gum'): ('s0', 'sink'),
(('s2', 's3'), '5c'): ('s3', 'sink'),
(('s2', 's3'), '10c'): ('s3', 'sink'),
(('sink', 'sink'), '5c'): ('sink', 'sink'),
(('s3', 's2'), '5c'): ('sink', 's3')
}
}
self.dfa_test_side_effect_1 = {
'alphabet': {'5c', '10c', 'gum'},
'states': {'s0', 's1', 's2', 's3'},
'initial_state': 's0',
'accepting_states': {'s0'},
'transitions': {('s0', '5c'): 's1',
('s0', '10c'): 's2',
('s1', '5c'): 's2',
('s1', '10c'): 's3',
('s2', '5c'): 's3',
('s2', '10c'): 's3',
('s3', 'gum'): 's0'}
}
self.dfa_test_side_effect_2 = {
'alphabet': {'5c', '10c', 'gum'},
'states': {
('s3', 't2'),
('s3', 't3'),
('s0', 't3'),
('s2', 't3'),
('s2', 't0'),
('s1', 't2'),
('s0', 't0'),
('s1', 't4'),
('s0', 't1'),
('s0', 't5'),
('s2', 't1'),
('s2', 't5'),
('s3', 't4'),
('s3', 't0'),
('s0', 't2'),
('s2', 't2'),
('s1', 't0'),
('s1', 't3'),
('s1', 't5'),
('s3', 't1'),
('s0', 't4'),
('s2', 't4'),
('s3', 't5'),
('s1', 't1')
},
'initial_state': ('s0', 't0'),
'accepting_states': {('s0', 't5'), ('s0', 't4')},
'transitions': {
(('s3', 't3'), 'gum'): ('s0', 't1'),
(('s0', 't1'), '10c'): ('s2', 't2'),
(('s3', 't2'), 'gum'): ('s0', 't4'),
(('s0', 't1'), '5c'): ('s1', 't5'),
(('s2', 't1'), '10c'): ('s3', 't2'),
(('s1', 't0'), '5c'): ('s2', 't1'),
(('s1', 't1'), '10c'): ('s3', 't2'),
(('s2', 't0'), '5c'): ('s3', 't1'),
(('s0', 't2'), '5c'): ('s1', 't3'),
(('s1', 't1'), '5c'): ('s2', 't5'),
(('s3', 't5'), 'gum'): ('s0', 't0'),
(('s1', 't2'), '5c'): ('s2', 't3'),
(('s2', 't2'), '5c'): ('s3', 't3'),
(('s2', 't1'), '5c'): ('s3', 't5'),
(('s0', 't0'), '5c'): ('s1', 't1')
}
}
[docs] def test_dfa_union_disjoint(self):
""" Tests a correct union between disjointed DFAs"""
union = DFA.dfa_union(self.dfa_union_1_test_01,
self.dfa_union_2_test_01)
# automata_IO.dfa_to_dot(union, 'union_new', 'tests/outputs')
self.assertTrue(
union['states'].issubset(self.dfa_test_disjoint_full['states']))
self.assertTrue(union['accepting_states'].issubset(
self.dfa_test_disjoint_full['accepting_states']))
[docs] def test_dfa_union_intersecting(self):
""" Tests a correct union between DFAs partially
intersected"""
union = DFA.dfa_union(self.dfa_union_1_test_02,
self.dfa_union_2_test_02)
# automata_IO.dfa_to_dot(union, 'union_intersecting', 'tests/outputs')
self.assertTrue(
union['states'].issubset(self.dfa_test_intersecting['states']))
self.assertTrue(union['accepting_states'].issubset(
self.dfa_test_intersecting['accepting_states']))
[docs] def test_dfa_union_equals(self):
""" Tests a correct union between the same DFA """
union = DFA.dfa_union(self.dfa_union_1_test_01,
self.dfa_union_1_test_01)
automata_IO.dfa_to_dot(union, 'union_equals', 'tests/outputs')
self.assertTrue(
union['states'].issubset(self.dfa_test_equals['states']))
self.assertTrue(union['accepting_states'].issubset(
self.dfa_test_equals['accepting_states']))
[docs] @unittest.expectedFailure
def test_dfa_union_wrong_dict_1(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_union({'goofy': 'donald'}, self.dfa_union_2_test_01)
[docs] @unittest.expectedFailure
def test_dfa_union_wrong_dict_2(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_union(self.dfa_union_1_test_01, {'goofy': 'donald'})
[docs] def test_dfa_union_side_effects(self):
""" Tests that the union function doesn't make side
effects on input DFAs"""
dfa1_before = copy.deepcopy(self.dfa_test_side_effect_1)
DFA.dfa_union(self.dfa_test_side_effect_1,
self.dfa_test_side_effect_2)
self.assertDictEqual(dfa1_before,
self.dfa_test_side_effect_1)
[docs]class TestDfaMinimization(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_minimization_test_01 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_minimization_test_01.dot')
self.dfa_minimization_test_01_minimized = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_minimization_test_01.dot')
self.dfa_minimization_test_02 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_minimization_test_02.dot')
self.dfa_minimization_test_02_minimized_s2 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_minimization_test_01.dot')
self.dfa_minimization_test_02_minimized_s4 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_minimization_test_01_s4.dot')
self.dfa_minimization_test_03 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_minimization_test_03.dot')
self.dfa_minimization_test_04 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_minimization_test_04.dot')
[docs] def test_dfa_minimization_already_minimized(self):
""" Tests the minimization of a DFA already minimal"""
self.assertDictEqual(
DFA.dfa_minimization(self.dfa_minimization_test_01),
DFA.dfa_completion(
self.dfa_minimization_test_01_minimized))
[docs] def test_dfa_minimization(self):
""" Tests correct DFA minimization """
minimal = DFA.dfa_minimization(
self.dfa_minimization_test_02)
# the two solution are semantically equivalent as 's2'
# and 's4' are equivalent
if 's4' in minimal['states']:
self.assertDictEqual(minimal, DFA.dfa_completion(
self.dfa_minimization_test_02_minimized_s4))
else:
self.assertDictEqual(minimal, DFA.dfa_completion(
self.dfa_minimization_test_02_minimized_s2))
[docs] def test_dfa_minimization_empty_states(self):
""" Tests a minimization with a dfa without states"""
minimal = DFA.dfa_minimization(
copy.deepcopy(self.dfa_minimization_test_03))
self.dfa_minimization_test_03['states'].add('sink')
self.assertDictEqual(minimal, self.dfa_minimization_test_03)
[docs] def test_dfa_minimization_empty_transitions(self):
""" Tests a minimization with a dfa without transitions"""
test = {
'alphabet': set(),
'states': {'s0'},
'initial_state': 's0',
'accepting_states': {'s0'},
'transitions': dict()
}
minimal = DFA.dfa_minimization(
copy.deepcopy(self.dfa_minimization_test_04))
if 's1' in minimal['states']:
test['states'].add('s1')
self.assertEqual(minimal, test)
elif 's2' in minimal['states']:
test['states'].add('s2')
self.assertEqual(minimal, test)
elif 's3' in minimal['states']:
test['states'].add('s3')
self.assertEqual(minimal, test)
[docs] @unittest.expectedFailure
def test_dfa_minimization_wrong_dict(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_minimization({'goofy': 'donald'})
[docs] def test_dfa_minimization_side_effects(self):
""" Tests the function doesn't make side effects on input
"""
input_before = copy.deepcopy(self.dfa_minimization_test_02)
DFA.dfa_minimization(self.dfa_minimization_test_02)
self.assertDictEqual(input_before,
self.dfa_minimization_test_02)
[docs]class TestDfaReachable(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_reachable_test_01 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_reachable_test_01.dot')
self.dfa_reachable_test_02 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_reachable_test_02.dot')
self.dfa_reachable_test_02_reachable = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_reachable_test_02_reachable.dot')
self.dfa_reachable_test_03 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_reachable_test_03.dot')
self.dfa_reachable_test_04 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_reachable_test_04.dot')
self.dfa_reachable_test_05 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_reachable_test_05.dot')
self.dfa_reachable_test_intersected = \
automata_IO.dfa_dot_importer(
'./tests/dot/automata_io'
'/automata_io_dfa_imported_intersection.dot')
[docs] def test_dfa_reachable_already_reachable(self):
""" Tests making reachable a DFA even if its already
completely reachable """
test = copy.deepcopy(self.dfa_reachable_test_01)
self.assertEqual(
DFA.dfa_reachable(self.dfa_reachable_test_01), test)
[docs] def test_dfa_reachable(self):
""" Tests making correctly reachable a DFA """
self.assertEqual(
DFA.dfa_reachable(self.dfa_reachable_test_intersected),
self.dfa_reachable_test_02_reachable)
[docs] def test_dfa_reachable_empty_states(self):
""" Tests making reachable a DFA without states"""
test = copy.deepcopy(self.dfa_reachable_test_03)
test['states'].add(None)
reach = DFA.dfa_reachable(self.dfa_reachable_test_03)
self.assertEqual(reach, test)
[docs] def test_dfa_reachable_empty_transitions(self):
""" Tests making reachable a DFA without transitions"""
test = {
'alphabet': set(),
'states': {'s0'},
'initial_state': 's0',
'accepting_states': {'s0'},
'transitions': dict()
}
self.assertEqual(
DFA.dfa_reachable(self.dfa_reachable_test_04), test)
[docs] @unittest.expectedFailure
def test_dfa_reachable_wrong_dict(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_reachable({'goofy': 'donald'})
[docs] def test_dfa_reachable_side_effects(self):
""" Tests the function makes side effects on input """
input_before = copy.deepcopy(
self.dfa_reachable_test_intersected)
DFA.dfa_reachable(self.dfa_reachable_test_intersected)
self.assertNotEquals(input_before,
self.dfa_reachable_test_intersected)
[docs] def test_dfa_reachable_side_effects_copy(self):
""" Tests the function doesn't make side effects if a
copy is passed as input """
input_before = copy.deepcopy(
self.dfa_reachable_test_intersected)
DFA.dfa_reachable(
copy.deepcopy(self.dfa_reachable_test_intersected))
self.assertEquals(input_before,
self.dfa_reachable_test_intersected)
[docs] def test_dfa_reachable_no_accepting_state_reachable(self):
""" Tests making reachable a DFA where no accepting state
is reached by the initial state"""
self.assertEqual(
DFA.dfa_reachable(self.dfa_reachable_test_05)[
'accepting_states'], set())
[docs]class TestDfaCoReachable(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_co_reachable_test_01 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_co_reachable_test_01.dot')
self.dfa_co_reachable_test_02 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_co_reachable_test_02.dot')
self.dfa_co_reachable_test_02_co_reachable = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_co_reachable_test_02_co_reachable.dot')
self.dfa_co_reachable_test_03 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_co_reachable_test_03.dot')
self.dfa_co_reachable_test_04 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_co_reachable_test_04.dot')
self.dfa_co_reachable_test_05 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_co_reachable_test_05.dot')
self.dfa_co_reachable_test_06 = \
automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_co_reachable_test_06.dot')
[docs] def test_dfa_co_reachable_already_co_reachable(self):
""" Tests making co_reachable a DFA even if its already
completely co_reachable """
test = copy.deepcopy(self.dfa_co_reachable_test_01)
self.assertEqual(
DFA.dfa_co_reachable(self.dfa_co_reachable_test_01),
test)
[docs] def test_dfa_co_reachable(self):
""" Tests making correctly co_reachable a DFA """
self.assertEqual(
DFA.dfa_co_reachable(self.dfa_co_reachable_test_02),
self.dfa_co_reachable_test_02_co_reachable)
[docs] def test_dfa_co_reachable_empty_states(self):
""" Tests making co_reachable a DFA without states"""
test = copy.deepcopy(self.dfa_co_reachable_test_03)
co_reach = DFA.dfa_co_reachable(
self.dfa_co_reachable_test_03)
self.assertEqual(co_reach, test)
[docs] def test_dfa_co_reachable_empty_transitions(self):
""" Tests making co_reachable a DFA without transitions"""
test = {
'alphabet': set(),
'states': {'s0'},
'initial_state': 's0',
'accepting_states': {'s0'},
'transitions': dict()
}
self.assertEqual(
DFA.dfa_co_reachable(self.dfa_co_reachable_test_04),
test)
[docs] @unittest.expectedFailure
def test_dfa_co_reachable_wrong_dict(self):
""" Tests a dict() in input different from a well
formatted dict() representing a DFA. [EXPECTED FAILURE]"""
DFA.dfa_co_reachable({'goofy': 'donald'})
[docs] def test_dfa_co_reachable_side_effects(self):
""" Tests the function makes side effects on input """
input_before = copy.deepcopy(self.dfa_co_reachable_test_06)
DFA.dfa_co_reachable(self.dfa_co_reachable_test_06)
self.assertNotEquals(input_before,
self.dfa_co_reachable_test_06)
[docs] def test_dfa_co_reachable_side_effects_copy(self):
""" Tests the function doesn't make side effects if a
copy is passed as input """
input_before = copy.deepcopy(self.dfa_co_reachable_test_06)
DFA.dfa_co_reachable(
copy.deepcopy(self.dfa_co_reachable_test_06))
self.assertEquals(input_before,
self.dfa_co_reachable_test_06)
[docs] def test_dfa_co_reachable_no_accepting_state_co_reachable(self):
""" Tests making co_reachable a DFA where the initial
state doesn't reach any accepting state """
test = {
'alphabet': set(),
'states': set(),
'initial_state': None,
'accepting_states': set(),
'transitions': dict()
}
self.assertEqual(
DFA.dfa_co_reachable(self.dfa_co_reachable_test_05),
test)
[docs]class TestDfaTrimming(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_trimming_test_01 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_trimming_test_01.dot')
self.dfa_trimming_test_02 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_trimming_test_02.dot')
self.dfa_trimming_test_03 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_trimming_test_03.dot')
self.dfa_trimming_test_04 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_trimming_test_04.dot')
[docs] def test_dfa_trimming(self):
""" Tests a correct trimming of a dfa"""
automata_IO.dfa_to_dot(
DFA.dfa_trimming(self.dfa_trimming_test_01),
'graphviz_dfa_trimming', 'tests/outputs')
[docs] def test_dfa_trimming_side_effects(self):
""" Tests the function makes side effects on input """
input_before = copy.deepcopy(self.dfa_trimming_test_01)
DFA.dfa_trimming(self.dfa_trimming_test_01)
self.assertNotEquals(input_before,
self.dfa_trimming_test_01)
[docs] def test_dfa_trimming_side_effects_copy(self):
""" Tests the function doesn't make side effects if a
copy is passed as input """
input_before = copy.deepcopy(self.dfa_trimming_test_01)
DFA.dfa_trimming(copy.deepcopy(self.dfa_trimming_test_01))
self.assertEquals(input_before, self.dfa_trimming_test_01)
[docs] def test_dfa_trimming_empty_states(self):
""" Tests trimming a DFA without states"""
test = copy.deepcopy(self.dfa_trimming_test_02)
trimmed = DFA.dfa_trimming(self.dfa_trimming_test_02)
self.assertEqual(trimmed, test)
[docs] def test_dfa_trimming_empty_transitions(self):
""" Tests trimming a DFA without transitions"""
test = {
'alphabet': set(),
'states': {'s0'},
'initial_state': 's0',
'accepting_states': {'s0'},
'transitions': dict()
}
self.assertEqual(
DFA.dfa_trimming(self.dfa_trimming_test_03), test)
[docs] def test_dfa_trimming_non_reachable_non_co_reachable(self):
""" Tests trimming a DFA without transitions"""
test = {
'alphabet': set(),
'states': set(),
'initial_state': None,
'accepting_states': set(),
'transitions': dict()
}
self.assertEqual(
DFA.dfa_trimming(self.dfa_trimming_test_04), test)
[docs]class TestDfaProjection(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_projection_test_01 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_projection_test_01.dot')
self.dfa_projection_test_02 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_projection_test_02.dot')
self.dfa_projection_test_01_solution = {
'alphabet': {'10c', 'gum'},
'states': {'s0', 's1', 's2', 's3'},
'initial_states': {'s0', 's1', 's2', 's3'},
'accepting_states': {'s0'},
'transitions': {
('s0', '10c'): {'s2', 's3'},
('s0', 'gum'): {'s0', 's1', 's2', 's3'},
('s1', '10c'): {'s3'},
('s1', 'gum'): {'s0', 's1', 's2', 's3'},
('s2', '10c'): {'s3'},
('s2', 'gum'): {'s0', 's1', 's2', 's3'},
('s3', 'gum'): {'s0', 's1', 's2', 's3'}
}
}
self.dfa_projection_test_02_solution = {
'alphabet': set(),
'states': {'s0', 's1', 's2', 's3', 's4'},
'initial_states': {'s0', 's1', 's2', 's3', 's4'},
'accepting_states': {'s0'},
'transitions': dict()
}
[docs] def test_dfa_projection(self):
""" Tests a correct dfa projection"""
projection = DFA.dfa_projection(self.dfa_projection_test_01,
{"5c"})
self.assertDictEqual(projection,
self.dfa_projection_test_01_solution)
[docs] def test_dfa_projection_full_alphabet_projection(self):
""" Tests a dfa projection where all the symbols of the alphabets
got projected out """
projection = DFA.dfa_projection(self.dfa_projection_test_02,
{'5c', '10c', 'gum'})
self.assertDictEqual(projection,
self.dfa_projection_test_02_solution)
[docs] def test_dfa_projection_words_not_in_alphabet(self):
""" Tests a dfa projection with word not present in the dfa alphabet
"""
projection = DFA.dfa_projection(self.dfa_projection_test_01,
{"pippo"})
solution = self.dfa_projection_test_01
solution['initial_states'] = set()
solution['initial_states'].add(solution['initial_state'])
solution.pop('initial_state')
for transition in solution['transitions']:
app = solution['transitions'][transition]
solution['transitions'][transition] = set()
solution['transitions'][transition].add(app)
self.assertDictEqual(projection, solution)
[docs] def test_dfa_projection_empty_words(self):
""" Tests a dfa projection without word o project out """
projection = DFA.dfa_projection(self.dfa_projection_test_01,
set())
solution = self.dfa_projection_test_01
solution['initial_states'] = set()
solution['initial_states'].add(solution['initial_state'])
solution.pop('initial_state')
for transition in solution['transitions']:
app = solution['transitions'][transition]
solution['transitions'][transition] = set()
solution['transitions'][transition].add(app)
self.assertDictEqual(projection, solution)
[docs] @unittest.expectedFailure
def test_dfa_projection_wrong_dict(self):
""" Tests a dfa projection where the first input is different from a
well formatted dict representing a dfa. [EXPECTED FAILURE] """
DFA.dfa_projection({}, {'5c'})
[docs] def test_dfa_projection_side_effects(self):
""" Tests the function doesn't make side effects on input """
before = copy.deepcopy(self.dfa_projection_test_01)
p = DFA.dfa_projection(self.dfa_projection_test_01, {'5c'})
p['states'].pop()
self.assertDictEqual(before, self.dfa_projection_test_01)
[docs]class TestDfaNonemptinessCheck(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_nonemptiness_check_test_01 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_nonemptiness_check_test_01.dot')
self.dfa_nonemptiness_check_test_02 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_nonemptiness_check_test_02.dot')
self.dfa_nonemptiness_check_test_03 = {
'alphabet': set(),
'states': set(),
'initial_state': None,
'accepting_states': set(),
'transitions': {}
}
self.dfa_nonemptiness_check_test_04 = {
'alphabet': {'5c', 'gum'},
'states': {'s0', 's1', 's2', 's3', 's4'},
'initial_state': 's0',
'accepting_states': {'s0'},
'transitions': {
('s0', '10c'): 's2',
('s0', '5c'): 's1',
('s1', '10c'): 's3',
('s2', '10c'): 's3',
('s3', 'gum'): 's0'
}
}
[docs] def test_dfa_nonemptiness_check(self):
""" Tests correctly the nonemptiness of the input """
self.assertTrue(DFA.dfa_nonemptiness_check(
self.dfa_nonemptiness_check_test_01))
[docs] def test_dfa_nonemptiness_check_false(self):
""" Tests correctly the emptiness of the input """
self.assertFalse(DFA.dfa_nonemptiness_check(
self.dfa_nonemptiness_check_test_02))
[docs] def test_dfa_nonemptiness_check_empty(self):
""" Tests the nonemptines of an empty dfa"""
self.assertFalse(DFA.dfa_nonemptiness_check(
self.dfa_nonemptiness_check_test_03))
[docs] @unittest.expectedFailure
def test_dfa_nonemptiness_check_wrong_dict(self):
""" Tests the nonemptines of an input dict different from a dict
representing a dfa. [EXPECTED FAILURE] """
self.assertFalse(DFA.dfa_nonemptiness_check({}))
[docs] def test_dfa_nonemptiness_check_side_effects(self):
""" Tests that the function doesn't make any side effect on the
input"""
before = copy.deepcopy(self.dfa_nonemptiness_check_test_01)
DFA.dfa_nonemptiness_check(
self.dfa_nonemptiness_check_test_01)
self.assertDictEqual(before,
self.dfa_nonemptiness_check_test_01)
[docs]class TestRenameDfaStates(TestCase):
[docs] def setUp(self):
self.maxDiff = None
self.dfa_1 = automata_IO.dfa_dot_importer(
'./tests/dot/dfa/dfa_renaming_test_01.dot')
[docs] def test_rename_dfa_states(self):
""" Tests a correct DFA states renaming """
automata_IO.dfa_to_dot(DFA.rename_dfa_states(self.dfa_1, 'TOP_'),
'dfa_renamed_1',
'tests/outputs')