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

Материјали

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

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

Алат за рад са аутоматима

За цртање и испробавање коначних аутомата уз ово поглавље постоји интерактивни алат. У њему можете:

цртати аутомате: стања, прелазе, петље, почетно и завршна стања, са ознакама као што су \(q_0\) или \(\alpha\);
радити са више аутомата истовремено у табовима и копирати стања из једног таба у други;
симулирати рад аутомата: унети реч и корак по корак пратити кроз која стања аутомат пролази и да ли реч прихвата, или тестирати више речи одједном;
примењивати операције: детерминизацију (конструкција подскупова), минимизацију, комплемент, унију, пресек и надовезивање — резултат се отвара у новом табу;
видети таблицу прелаза \(\delta\) текућег аутомата и сачувати аутомат као датотеку или слику.

Алат се може користити овде или отворити у новом прозору, где има више простора. Упутство се добија дугметом „?“ у алату.

Најважније пречице: двоклик на празно платно додаје стање; Shift + превлачење од стања до стања прави прелаз (на исто стање — петљу); двоклик на стање га чини завршним, а десни клик почетним; изабрани елемент мења се куцањем или у панелу десно; Delete брише, Ctrl+C / Ctrl+V копира и лепи (и између табова), Ctrl+Z поништава.

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

Имплементираћемо коначни аутомат приказан на слици 8.1. Почетно стање је 0 (на њега показује стрелица), а оно је уједно и завршно стање (двострука кружница).

Слика 8.1: Коначни аутомат са стањима 0, 1 и 2 над азбуком \(\{a, b\}\)


# Дефинишемо скуп стања
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("Аутомат не прихвата реч")