ZAUT2017/Zadania z automatów

Zadania z automatów znajdują się z katalogu automata/.

Termin rozwiązania tych zadań to 29 stycznia 2016 r.

Które zadania należy zrobić?

Uwaga! Spośród zadań 205-219 student rozwiązuje JEDNO zadanie — takie którego reszta z dzielenia przez 15 jest taka sama jak reszta z dzielenia numeru indeksu przez 15.

Spośród zadań 201-204 można zrobić dowolne zadania.

Podpowiedzi

W rozwiązaniach należy korzystać z dostępnego w katalogu pliku deterministic_automaton — zdefiniowano tam klasę DeterministicAutomaton reprezentującą automat deterministyczny. Trzeba więc skorzystać w pewnym stopniu z programowania obiektowego. Nie powinno to być jednak trudne jako że:

  • nie definiujemy nowej klasy, tylko korzystamy z gotowych,
  • metodę wywołujemy na rzecz danego obiektu wywołujemy przy użyciu notacji obiekt.methoda(...) (podobnie jak w Javie).

Na przykład rozwiązanie zadania 201 może wyglądać tak:

#!/usr/bin/python2
# -*- coding: utf-8 -*-

"""
Rozwiązanie zadania 201.
"""

def is_initial_state_a_final_one(automaton):
    """
    Sprawdza, czy stan początkowy jest końcowym.
    """
    return automaton.is_final_state(...)

(Co powinno być wpisane w miejsce wielokropka, żeby uzyskać pełne rozwiązanie?)

Jeśli chodzi o zadania 205-219, to rozwiązanie powinno wyglądać mniej więcej tak:

#!/usr/bin/python2
# -*- coding: utf-8 -*-

"""
Rozwiązanie zadania 2..
"""

from deterministic_automaton import DeterministicAutomaton

def ab_automaton():
    """
    Sprawdza, czy napis to "ab".
    """

    automaton = DeterministicAutomaton()

    state_a = automaton.add_state()
    state_b = automaton.add_state()
    state_c = automaton.add_state()

    automaton.mark_as_initial(state_a)
    automaton.mark_as_final(state_c)

    automaton.add_transition(state_a, 'a', state_b)
    automaton.add_transition(state_b, 'b', state_c)

    return automaton