7 Коначне машине и аутомати

Материјали

Материјали за ову тему се могу преузети овде.

Аутор материјала је проф. др. Богдана Станојевић.

Цртање аутомата

Велика бела површина испод омогућава брзо исцртавање коначних аутомата. Упуство за коришћење:

Додавање стања: двапут кликнути на платно
Додавање стрелице: држати Shift и повући мишем по платну
Померање елемената: превући мишем
Брисање елемената: кликнути на елемент и притиснути тастер Delete (не Backspace)
Означавање прихватљивог стања: двапут кликнути на постојеће стање
Унос броја као индекса: ставити доњу црту пре броја (на пример: S_0)
Унос грчког слова: ставити обрнуту косу црту пре слова (на пример: \beta)

Коначни аутомати у пајтону

Пример коначног аутомата за имплементацију у пајтону


# Дефинишемо скуп стања
stanja = {0, 1, 2}

# Функција прелаза: за сваки пар (стање, симбол) даје следеће стање
funkcija_prelaza = {
    (0, "a"): 1,
    (0, "b"): 0,
    (1, "a"): 2,
    (1, "b"): 1,
    (2, "a"): 0,
    (2, "b"): 2
}

# Почетно стање аутомата
pocetno_stanje = 0

# Скуп завршних (прихватљивих) стања
zavrsna_stanja = {0}

# Бесконачна петља за унос речи
while True:
    # Корисник уноси реч коју жели да провери
    rec_za_proveru = input("Унесите реч за проверу: ")

    # Ако је унето "quit", прекида се петља и програм се завршава
    if rec_za_proveru == "quit":
        break

    # Иницијализујемо текуће стање као почетно
    tekuce_stanje = pocetno_stanje

    # За сваки симбол у унетој речи...
    for simbol in rec_za_proveru:
        # ...применимо функцију прелаза да добијемо ново стање
        tekuce_stanje = funkcija_prelaza[(tekuce_stanje, simbol)]

    # Након читања целе речи, проверава се да ли је тренутно стање завршно
    if tekuce_stanje in zavrsna_stanja:
        print("Аутомат прихвата реч")
    else:
        print("Аутомат не прихвата реч")