logo

Példák a DFA-ra

1. példa:

Tervezze meg az FA-t ∑ = {0, 1} értékkel, és elfogadja azokat a karakterláncokat, amelyek 1-gyel kezdődnek és 0-val végződnek.

Megoldás:

Az FA-nak lesz egy q0 kezdőállapota, amelyből csak az 1-es bemenettel rendelkező él kerül a következő állapotba.

Példák determinisztikus véges automatákra

A q1 állapotban, ha 1-et olvasunk, q1 állapotban leszünk, de ha 0-t olvasunk a q1 állapotban, akkor elérjük a q2 állapotot, ami a végső állapot. A q2 állapotban, ha 0-t vagy 1-et olvasunk, akkor q2 vagy q1 állapotba megyünk. Vegye figyelembe, hogy ha a bemenet 0-ra végződik, akkor a végső állapotba kerül.

2. példa:

Tervezzen meg egy FA-t ∑ = {0, 1} értékkel, amely elfogadja az egyetlen 101-es bemenetet.

Megoldás:

Példák determinisztikus véges automatákra

Az adott megoldásnál azt láthatjuk, hogy csak a 101-es bemenet kerül elfogadásra. Ennélfogva a 101-es bemenethez nincs más útvonal a másik bemenet számára.

nem determinisztikus véges automaták

3. példa:

Az FA tervezés ∑ = {0, 1} elfogadja a páros számú 0-t és a páros számú 1-et.

Megoldás:

Ez az FA négy különböző szakaszt vesz figyelembe a 0. és az 1. bemenet számára. A szakaszok a következők lehetnek:

Példák determinisztikus véges automatákra

Itt q0 egy kezdő állapot és egy végállapot is. Ügyeljen arra, hogy a 0-k és 1-ek szimmetriája megmarad. Az egyes állapotokhoz jelentéseket rendelhetünk:

q0: páros számú 0 és páros számú 1 állapota.
q1: a páratlan számú 0 és a páros számú 1 állapota.
q2: a páratlan számú 0 és a páratlan számú 1 állapota.
q3: a páros számú 0 és a páratlan számú 1 állapota.

4. példa:

Az FA tervezés ∑ = {0, 1} elfogadja az összes karakterlánc halmazát három egymást követő 0-val.

Megoldás:

Az adott nyelvhez generált karakterláncok a 000, 0001, 1000, 10001, ...., amelyben a 0 mindig egy 3-as csoportban jelenik meg. Az átmeneti gráf a következő:

Példák determinisztikus véges automatákra

Vegye figyelembe, hogy a hármas nullák sorrendje megmarad a végső állapot eléréséhez.

5. példa:

Tervezze meg a DFA-t L(M) = {w | w ε {0, 1}*} és W egy karakterlánc, amely nem tartalmaz egymást követő 1-eket.

Megoldás:

Ha három egymást követő 1 fordul elő, a DFA a következő lesz:

Példák determinisztikus véges automatákra

Itt tehát két egymást követő 1-es vagy egyetlen 1-es is elfogadható

Példák determinisztikus véges automatákra

A q0, q1, q2 szakaszok a végső állapotok. A DFA létrehozza azokat a karakterláncokat, amelyek nem tartalmaznak egymást követő 1-eseket, például 10, 110, 101 stb.

6. példa:

Tervezzünk meg egy FA-t ∑ = {0, 1} értékkel, amely elfogadja a páros számú 0-t, majd egyszeri 1-et.

Megoldás:

A DFA egy átmeneti diagrammal ábrázolható:

Példák determinisztikus véges automatákra