Deterministic finite state machines¶

This Jupyter notebook provides an example of using the Python package gravis. The .ipynb file can be found here.

It provides a simple implementation of a finite state machine and visualizes its formal structure as network plot: States are represented as nodes, state transitions as edges, and symbols (read from the input string during a transition) as edge labels.

References¶

Wikipedia: Deterministic finite automaton

[1]:

import gravis as gv

Defining a DFA class¶

[2]:

class DeterministicFiniteAutomaton:
    """A simple data structure for a deterministic finite automaton (DFA)"""

    def __init__(self, states, alphabet, transitions, start_state, accepting_states):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.accepting_states = accepting_states

    def accepts(self, string):
        current_state = self.start_state
        for symbol in string:
            if symbol not in self.alphabet:
                raise ValueError('String contains invalid symbol: '.format(symbol))
            current_state = self.transitions[current_state][symbol]
        if current_state in self.accepting_states:
            return True
        return False

    def plot_structure(self):
        # States as nodes
        nodes = {}
        hidden_start_node = {'label': '', 'metadata': {'size': '0'}}
        nodes['__start'] = hidden_start_node
        for state in self.states:
            if state in self.accepting_states:
                nodes[state] = {'label': state, 'metadata': {'border_size': 2, 'border_color': 'black'}}
            else:
                nodes[state] = {'label': state}
        # State transitions as edges
        hidden_start_edge = {'source': '__start', 'target': self.start_state, 'label': ''}
        edges = [hidden_start_edge]
        for source, values in self.transitions.items():
            for label, target in values.items():
                edges.append({'source': source, 'target': target, 'label': label})
        # Graph definition in gJGF format
        data_gjgf = {
            'graph': {
                'directed': True,
                'metadata': {
                    'node_size': 20,
                    'node_color': 'green',
                    'node_label_color': 'green',
                    'edge_label_size': 10,
                    'edge_label_color': 'blue'},
                'nodes': nodes,
                'edges': edges,
            }
        }
        # Plotting
        fig = gv.d3(
            data_gjgf, node_label_data_source='label', edge_label_data_source='label',
            show_edge_label=True, edge_curvature=0.2, zoom_factor=1.8, links_force_distance=90)
        return fig

Creating a DFA instance¶

[3]:

m1 = DeterministicFiniteAutomaton(
    states={'q0', 'q1', 'q2', 'q3'},
    alphabet={'0', '1'},
    transitions={
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q0', '1': 'q2'},
        'q2': {'0': 'q0', '1': 'q3'},
        'q3': {'0': 'q0', '1': 'q3'}
    },
    start_state='q0',
    accepting_states={'q3'}
)

Recognizing strings¶

Use the DFA to test whether certain strings are accepted, i.e. whether they are part of the formal language defined by the DFA.

[4]:

strings = [
    '111',
    '010111',
    '101',
    '101110',
]

for s in strings:
    if m1.accepts(s):
        print('"{}" was recognized.'.format(s))
    else:
        print('"{}" was NOT recognized.'.format(s))

"111" was recognized.
"010111" was recognized.
"101" was NOT recognized.
"101110" was NOT recognized.

Plotting its structure¶

[5]:

m1.plot_structure()

[5]:

Details for selected element