logo

DFA örnekleri

Örnek 1:

∑ = {0, 1} ile bir FA tasarlayın, 1 ile başlayan ve 0 ile biten dizeleri kabul edin.

Çözüm:

FA, yalnızca girişi 1 olan kenarın bir sonraki duruma geçeceği q0 başlangıç ​​durumuna sahip olacaktır.

Deterministik sonlu otomata örnekleri

q1 durumunda 1 okursak q1 durumunda olacağız, q1 durumunda 0 okursak ise son durum olan q2 durumuna ulaşacağız. q2 durumunda 0 veya 1 okursak sırasıyla q2 durumuna veya q1 durumuna geçeceğiz. Girişin 0 ile bitmesi durumunda son durumda olacağını unutmayın.

Örnek 2:

∑ = {0, 1} olan bir FA tasarlayın, tek giriş 101'i kabul eder.

Çözüm:

Deterministik sonlu otomata örnekleri

Verilen çözümde sadece 101 girişinin kabul edileceğini görüyoruz. Dolayısıyla, giriş 101 için diğer giriş için gösterilen başka bir yol yoktur.

Örnek 3:

∑ = {0, 1} olan FA tasarımı çift sayıda 0'ı ve çift sayıda 1'i kabul eder.

Çözüm:

Bu FA, giriş 0 ve giriş 1 için dört farklı aşamayı dikkate alacaktır. Aşamalar şunlar olabilir:

Deterministik sonlu otomata örnekleri

Burada q0 bir başlangıç ​​durumu ve aynı zamanda son durumdur. 0'lar ve 1'lerin simetrisinin korunduğuna dikkat edin. Anlamları her duruma şu şekilde bağlayabiliriz:

q0: çift sayıda 0'ların ve çift sayıda 1'lerin durumu.
q1: tek sayıdaki 0'ların ve çift sayıdaki 1'lerin durumu.
q2: tek sayıdaki 0'ların ve tek sayıdaki 1'lerin durumu.
q3: çift sayıdaki 0'ların ve tek sayıdaki 1'lerin durumu.

Örnek 4:

∑ = {0, 1} olan FA Tasarımı, ardışık üç 0'lı tüm dizilerin kümesini kabul eder.

Çözüm:

Bu belirli diller için oluşturulacak dizeler 000, 0001, 1000, 10001, .... şeklindedir; burada 0 her zaman 3 kümesinde görünür. Geçiş grafiği aşağıdaki gibidir:

Deterministik sonlu otomata örnekleri

Son duruma ulaşmak için üçlü sıfır dizisinin korunduğunu unutmayın.

Örnek 5:

Bir DFA tasarlayın L(M) = {w | w ε {0, 1}*} ve W ardışık 1'ler içermeyen bir dizedir.

Çözüm:

Art arda üç 1 oluştuğunda DFA şöyle olacaktır:

Deterministik sonlu otomata örnekleri

Burada ardışık iki 1 veya tek 1 kabul edilebilir, dolayısıyla

Deterministik sonlu otomata örnekleri

q0, q1, q2 aşamaları son durumlardır. DFA, 10, 110, 101,..... vb. gibi ardışık 1'ler içermeyen dizeleri üretecektir.

Örnek 6:

∑ = {0, 1} ile bir FA tasarlayın, çift sayıda 0 ve ardından tek 1 gelen dizeleri kabul eder.

Çözüm:

DFA bir geçiş diyagramı ile şu şekilde gösterilebilir:

Deterministik sonlu otomata örnekleri