Implementieren Sie einen deterministischen endlichen Automaten in Python, um Vielfache von 3 zu bestimmen

Die automata-lib-Bibliothek erleichtert die Implementierung von Automutons in Python.

Was ist in diesem Artikel zu tun?

Verwenden Sie den deterministischen endlichen Automaten in Python, um festzustellen, ob eine Binärzahl durch 3 teilbar ist. Es ist ein Beispiel, das oft in Lehrbüchern zu finden ist. Wenn die Eingabe ein Vielfaches von 3 ist, wird sie akzeptiert, andernfalls wird sie abgelehnt. Im Zustandsübergangsdiagramm sieht es so aus.

Wenn es sich um eine Hausaufgabe an einer Universität handelt, sollten Sie sie selbst implementieren. Hier werden wir sie jedoch mit der automata-lib-Bibliothek implementieren.

Umgebung

OS

• Pengwin 1.4.1 on WSL

Python-Version

Python 3.8.1

Bibliothek zu verwenden

automata-lib automata-lib funktioniert mit Python 3.4 und höher.

Umwelt schaffen

Die Umgebung wurde mit pipenv gebaut.

$ pipenv --python 3.8
$ pipenv install automata-lib
$ pipenv shell

Ausführungsbeispiel

Der eingegebene numerische Wert (Dezimalzahl) wird als erstes Argument angegeben. Wenn es durch 3 teilbar ist, wird es als "Ergebnis: Akzeptiert" ausgegeben, und wenn es nicht durch 3 teilbar ist, wird es als "Ergebnis: Abgelehnt" ausgegeben. Danach wird auch der Übergang ausgegeben. Es ist bequem.

Akzeptiertes Beispiel

$ ./modulo_three.py 12
12
Result: Accepted
Transitions
q0
q1
q0
q0
q0

Beispiele für Ablehnung

$ ./modulo_three.py 11
11
Result: Rejected
Transitions
q0
q1
q2
q2
q2
Traceback (most recent call last):
  File "./modulo_three.py", line 40, in <module>
    for i in modulo.read_input_stepwise(entry):
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
105, in read_input_stepwise
    self._check_for_input_rejection(current_state)
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
87, in _check_for_input_rejection
    raise exceptions.RejectionException(
automata.base.exceptions.RejectionException: the DFA stopped on a non-final state (q2)

Erläuterung

Definition des Automaten

Die Implementierung des deterministischen endlichen Automaten verwendet die DFA-Klasse.

modulo_three.py

modulo = DFA(
    states = {'q0', 'q1', 'q2'},
    input_symbols = {'0', '1'},
    transitions = {
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q2', '1': 'q0'},
        'q2': {'0': 'q1', '1': 'q2'}
    },
    initial_state='q0',
    final_states={'q0'}
)

--state definiert den Zustand dieses Automaten.

• Definieren Sie Eingabesymbole mit input_symbols.
• Definieren Sie eine Regel, die mit "Übergängen" von einem Zustand in einen anderen übergeht. Wenn Sie beispielsweise "q0" als Beispiel nehmen und die Eingabe 0 ist, wechselt sie zu "q0", und wenn die Eingabe 1 ist, wechselt sie zu "q1".
• Geben Sie den Startstatus mit "initial_state" an.
• Geben Sie den Akzeptanzstatus mit "final_state" an.

Führen Sie automuton aus

Wenn Sie einfach feststellen möchten, ob es akzeptiert wird, verwenden Sie die Methode "accept_input". Wenn es akzeptiert wird, gibt es "True" zurück, und wenn es abgelehnt wird, gibt es "False" zurück. Beachten Sie, dass das Argument der Methode "accept_input" eine binäre Zeichenfolge ist.

>>> modulo.accepts_input('10')
False
>>> modulo.accepts_input('110')
True

Wenn Sie sehen möchten, wie es übergeht, verwenden Sie die Methode "read_input_stepwise". Diese Methode gibt den Übergang im Generator zurück. Wenn es abgelehnt wird, wird eine "RejectionException" -Ausnahme zurückgegeben.

Akzeptiertes Beispiel

>>> for i in modulo.read_input_stepwise('110'):
...   print(i)
...
q0
q1
q0
q0

Beispiele für Ablehnung

>>> for i in modulo.read_input_stepwise('10'):
...   print(i)
... 
q0
q1
q2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
105, in read_input_stepwise
    self._check_for_input_rejection(current_state)
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
87, in _check_for_input_rejection
    raise exceptions.RejectionException(
automata.base.exceptions.RejectionException: the DFA stopped on a non-final state (q2)

Code

Sie finden es hier. MIT-Lizenz. https://github.com/bateleurX/qiita-modulo_three