Aptallar için sonlu makineler. Sonlu otomatlar: dönüştürücüler ve tanıyıcılar. Otomata ve normal diller

Ders 5

Deterministik sonlu otomatlar

Ayrık deterministik modeller ( F-şema)

Temel oranlar. Otomata teorisinin matematiksel bir aparat olarak kullanılması örneğinde ayrık deterministik yaklaşımın özelliklerini düşünün. Sistem, ayrık bilgileri işleyen ve iç durumlarını yalnızca kabul edilebilir zamanlarda değiştiren, giriş ve çıkış sinyallerine sahip bir cihaz olarak bir otomat olarak temsil edilir. durum makinesi iç durumları, giriş ve çıkış sinyalleri sonlu kümeler olan bir otomat olarak adlandırılır.

Soyut olarak, sonlu bir otomat matematiksel bir şema olarak temsil edilebilir ( F-şema) altı öğeyle karakterize edilir: sonlu bir küme X giriş sinyalleri (giriş alfabesi); Sınırlı set eçıkış sinyalleri (çıkış alfabesi); Sınırlı set Z iç durumlar (iç alfabe veya durumların alfabesi); başlangıç hali z 0 , z 0 Î Z; geçiş fonksiyonu j( z, X); çıkış fonksiyonu y( z, X). Verilen otomat F-şema: F = á Z, X, e, y, j, z 0 ñ, her biri giriş ve çıkış sinyallerinin ve dahili durumların sabit değerlerine karşılık gelen, anları döngü olan ayrık zamanda çalışır. Durumu ve buna karşılık gelen giriş ve çıkış sinyallerini belirtelim. T-th vuruşu T= 0, 1, 2, …, ila z(T), X(T), sen(T). Aynı zamanda duruma göre z(0) = z 0 ve z(T)Î Z, X(T)Î X, sen(T)Î e.

Örnek. Bir aslanın davranışının en basit otomasyonu.

Giriş alfabesi: "antilop", "avcı".

Dahili durumlar: "dolu", "aç".

Çıkış alfabesi: "ye", "uyku", "kaç"

Atlama tablosu:

Soyut durum makinesinin bir giriş ve bir çıkış kanalı vardır. Her an T= 0, 1, 2, ... ayrık zaman F- makine belirli bir durumda z(T) setten Z Otomatın durumları ve zamanın ilk anında T= 0 her zaman başlangıç durumundadır z(0) = z 0. şu anda T, yapabilmek z(T), otomat giriş kanalındaki bir sinyali algılayabilir X(T)Î X ve çıkış kanalına bir sinyal verin sen(T) = sen[ z(T), X(T)], z( durumuna geçerek T+1) = J[ z(T), X(T)], z(T)Î Z, sen(T)Î e. Soyut bir sonlu otomat, giriş alfabesindeki sözcük kümesinin bazı eşlemelerini uygular Xçıktı alfabesindeki bir dizi kelimeye e. Başka bir deyişle, sonlu durum makinesinin girişi başlangıç durumuna ayarlanırsa z 0 , giriş alfabesinin harflerini belirli bir sırayla girin X(0), X(1), X(2), …, yani. giriş sözcüğü, ardından otomatın çıktısı, çıktı alfabesinin harfleri sırayla görünecektir sen(0), sen(1), sen(2), …, çıkış kelimesini oluşturur.

Böylece, sonlu otomatın çalışması aşağıdaki şemaya göre gerçekleşir: her birinde T- durumundaki otomatın girişine giden döngü z(T), bir miktar sinyal verilir X(T), bir geçişle reaksiyona girdiği ( T+1)'inci döngüden yeni bir duruma geçiş z(T+1) ve bazı çıkış sinyallerinin verilmesi. Yukarıdakiler aşağıdaki denklemlerle açıklanabilir: F- birinci türden bir otomat, aynı zamanda denir Mil makinesi,

z(T+1) = j[ z(T), X(T)], T= 0, 1, 2, …; (2.15)

sen(T) = y[ z(T), X(T)], T= 0, 1, 2, …; (2.16)

İçin F- ikinci türden otomasyon

z(T+1) = j[ z(T), X(T)], T= 0, 1, 2, …; (2.17)

sen(T) = y[ z(T), X(T- 1)], T= 1, 2, 3,…. (2.18)

İkinci türden bir otomat, bunun için

sen(T) = y[ z(T)], T= 0, 1, 2, …, (2.19)

onlar. çıkış fonksiyonu giriş değişkenine bağlı değildir X(T), denir Moore makinesi.

Böylece, tamamen tanımlayan (2.15)-(2.19) denklemleri
F-otomat, (2.3) ve (2.4) denklemlerinin özel bir durumudur;
sistem S- deterministik ve tek girişi ayrı bir sinyal alır X.

Durum sayısına göre hafızalı ve hafızasız sonlu otomatlar ayırt edilir. Hafızalı otomatların birden fazla durumu varken hafızasız otomatların (kombinasyon veya mantık devreleri) yalnızca bir durumu vardır. Aynı zamanda (2.16)'ya göre birleşimsel devrenin çalışması, her bir giriş sinyaline atama yapılmasıdır. X(T) tanımlı çıkış sinyali sen(T), yani. formun mantıksal bir işlevini uygular

sen(T) = y[ X(T)], T= 0, 1, 2, … .

Bu fonksiyona, eğer alfabe X Ve e sinyal değerlerine ait olan X Ve sen, iki harften oluşur.

Ayrık zaman sayımının doğasına göre, sonlu otomatlar senkron ve asenkron olarak ikiye ayrılır. Senkron olarak F-otomatlarda, otomatın giriş sinyallerini "okuduğu" zaman noktaları zorunlu senkronizasyon sinyalleri tarafından belirlenir. Bir sonraki senkronizasyon sinyalinden sonra, "okuma" dikkate alınarak ve (2.15) - (2.19) denklemlerine uygun olarak, yeni bir duruma geçiş meydana gelir ve bir çıkış sinyali verilir, ardından otomat bir sonraki değeri algılayabilir. giriş sinyali. Böylece, otomatın giriş sinyalinin her bir değerine tepkisi, süresi bitişik senkronizasyon sinyalleri arasındaki aralık tarafından belirlenen bir döngüde sona erer. Asenkron F- makine giriş sinyalini sürekli olarak okur ve bu nedenle sabit değerde yeterince uzun bir giriş sinyaline tepki verir X(2.15)-(2.19)'da belirtildiği gibi, durumu, verilen giriş sinyali tarafından artık değiştirilemeyecek kararlı bir duruma geçene kadar karşılık gelen sayıda çıkış sinyali vererek birkaç kez değiştirebilir.

Olası uygulamalar F-şema. Finali ayarlamak için F-otomat, setin tüm elemanlarını tanımlamak gerekir F= <Z, X, e, y, j, z 0>, yani giriş, iç ve çıkış alfabelerinin yanı sıra geçiş ve çıkış fonksiyonları ve durumlar kümesi arasından durumu seçmek gerekir z 0 , otomatın durumunda olduğu T= 0. İşi ayarlamanın birkaç yolu vardır F-makineler, ancak en sık kullanılanları tablo, grafik ve matristir.

Tablo yönteminde, satırları otomatın giriş sinyallerine ve sütunları durumlarına karşılık gelen geçiş ve çıkış tabloları belirtilir. Soldaki ilk sütun başlangıç durumuna karşılık gelir z 0. Kavşakta Ben-inci satır ve k geçiş tablosunun inci sütununda karşılık gelen değer j( zk, x ben) geçiş fonksiyonları ve çıktı tablosunda - karşılık gelen değer y( z k ,x ben) çıkış fonksiyonları. İçin F-Moore makinesi, her iki masa birleştirilebilir.

İş tanımı F j geçişlerinin ve y çıkışlarının -mealy otomat tabloları Tablo'da gösterilmektedir. 2.1 ve açıklama F-Moore otomatı - geçiş tablosuna göre (Tablo 2.2).

Tablo 2.1



Geçişler
	J( z 0 , X 1)	J( z 1 , X 1)	J( zk,X 1)
	J( z 0 , X 2)	J( z 1 , X 2)	J( zk,X 2)

	J( z 0 , x ben)	J( z 1 , x ben)	J( zk,x ben)
çıkışlar
	y( z 0 , X 1)	y( z 1 , X 1)	y( zk, X 1)
	y( z 0 , X 2)	y( z 1 , X 2)	y( zk, X 2)

	y( z 0 , x ben)	y( z 1 , x ben)	y( zk, x ben)

Tablo 2.2




J( z 0 , X 1)	J( z 1 , X 1)	J( zk, X 1)
J( z 0 , X 2)	J( z 1 , X 2)	J( zk, X 2)

J( z 0 , x ben)	J( z 1 , x ben)	J( zk, x ben)

Tablo şeklinde ayarlama örnekleri F- Mil makinesi F 1 tabloda verilmiştir. 2.3 ve F-Moore makinesi F 2 - tabloda. 2.4.

Tablo 2.3



Geçişler


çıkışlar

Tablo 2.4

Sonlu bir otomatın grafiksel olarak belirlenmesinde, yönlendirilmiş grafik kavramı kullanılır. Otomat grafiği, otomatın farklı durumlarına karşılık gelen ve otomatın belirli geçişlerine karşılık gelen grafik yaylarının köşelerini birbirine bağlayan bir köşe kümesidir. Giriş sinyali ise xk durum geçişine neden olur z ben bir duruma zj, ardından otomat grafiğinde tepe noktasını birleştiren yay z ben tepe zj, belirtilen xk. Çıkışların fonksiyonunu tanımlamak için grafiğin yayları karşılık gelen çıkış sinyalleriyle işaretlenmelidir. Mealy otomatları için bu etiketleme şu şekilde yapılır: eğer giriş sinyali xk devleti etkiler z ben, sonra çıkan bir yay elde ederiz z ben ve etiketlenmiş xk; bu yay ayrıca bir çıkış sinyaliyle işaretlenir sen= y( z ben, xk). Bir Moore otomatı için grafiğin benzer şekilde etiketlenmesi şu şekildedir: eğer giriş sinyali xk Otomatın bazı durumlarına etki ederek duruma geçişe neden olur zj, ardından yay şuraya yönlendirildi: z ben ve etiketlenmiş xk, ayrıca hafta sonunu kutlayın
sinyal sen= y( zj, xk).

Şek. 2.4. A, B daha önce verilen tablolar F- Mili otomatları F 1 ve Moura F sırasıyla 2.

Pirinç. 2.4. Otomat grafikleri a - Mealy ve b - Moore

Sonlu bir otomatın matris spesifikasyonuyla, otomatın bağlantı matrisi kare şeklindedir İLE=||İleben||, satırlar başlangıç durumlarına, sütunlar ise geçiş durumlarına karşılık gelir. Öğe İleben = xk/evet kavşakta duran
Ben-inci satır ve J Mealy otomatının kullanılması durumunda, inci sütun giriş sinyaline karşılık gelir xk durumdan geçişe neden olan z ben bir duruma zj ve çıkış sinyali evet bu geçişle yayınlandı. Mili makinesi için F Yukarıda tartışılan Şekil 1'e göre bağlantı matrisi şu şekildedir:

X 2 /sen 1 – X 1 /sen 1

C 1 = X 1 /sen 1 – X 2 /sen 2 .

X 1 /sen 2 X 2 /sen 1 –

İçin F-Moore makine elemanı İleben geçişteki giriş sinyalleri kümesine eşittir ( z ben,zj) ve çıktı, çıktıların vektörüyle tanımlanır

= y( zk) ,

Ben-th bileşeni durumu belirten çıkış sinyalidir z ben.

Yukarıdaki için F-Moore makinesi F2 bağlantı matrisleri ve çıkış vektörü şu şekildedir:

– X 1 – X 2 –en 1

– X 2 – – X 1 en 1

C 2 = – X 2 – – X 1 ; = y 3

X 2 – X 1 – –en 2

X 2 – X 1 – –en 3

Deterministik otomatlar için geçiş benzersizliği koşulu karşılanmıştır: belirli bir durumdaki bir otomat, herhangi bir giriş sinyalinin etkisi altında birden fazla duruma gidemez. Grafiksel ayarlama yöntemiyle ilgili olarak F-otomat, bu, bir otomatın grafiğinde aynı giriş sinyaliyle işaretlenen iki veya daha fazla kenarın herhangi bir tepe noktasından çıkamayacağı anlamına gelir. Ve otomatın bağlantı matrisinde İLE her satırda herhangi bir giriş sinyali birden fazla kez oluşmamalıdır.

Bu nedenle, modellerdeki nesne özelliklerinin incelenmesine yönelik ayrık deterministik yaklaşımdaki kavram, otomatik kontrol sistemlerinde gerçek nesnelerin işleyiş süreçlerinin geniş bir sınıfını tanımlamak için uygun olan matematiksel bir soyutlamadır. Kullanarak F- Bir otomatın, ayrık durumların varlığı ve zaman içindeki işin ayrık doğası ile karakterize edilen nesneleri tanımlamak mümkündür - bunlar bir bilgisayarın elemanları ve düğümleri, kontrol, düzenleme ve kontrol cihazları, zamansal ve mekansal sistemlerdir. bilgi alışverişi teknolojisinde geçiş vb.

Sonlu durum makineleriyle simülasyon örneği

Sonlu durum makinesi (işlemci) oluşturmaya bir örnek

gerçek sayıların gösterimini tanımak ve işlemek için

Makinenin girişinde: işaretsiz bir gerçek sayıyı temsil eden bir karakter dizisi.

Makinenin çıkışında: bir çift tam sayı: mantis ve üs veya sayı doğru yazılmadığında bir hata mesajı.

Örnek.

1. 38.71 E - 42 → (3871, -44);

2. .9E 21 → (9, 20);

3. 4.5.6 .9→ Hata;

4. 3. E 4 → (3, 4);

5. 12 → (12, 0);

6. 1.2 → (12, -1).

Bu örnekte, sonlu bir tanıyan otomat ve bir işleme işlemcisi oluşturma probleminin çözümüne yönelik bir örnek göstereceğiz. Bu süreci birkaç aşamaya ayıralım.

1.Bir veya daha fazla örnek yazın karakteristik aşağıdakileri temel alan zincirler:

a) giriş alfabesini belirleyin;

b) otomatın çalışmasını simüle eden durum zincirlerinin sembolleri altında imza;

c) durumların sözlü açıklamalarını yazın.

a) Giriş alfabesiA\u003d (c E. + -); (burada c 0..9 sayısıdır)

b) Örnekler.

Giriş dizesi: 3 8 . 7 1 E – 4 2

Makine durumları: Ø 1 1 2 3 3 4 5 6 6

Giriş dizesi: . 9 E 2 1.

Makine durumları: Ø7 3 4 6 6.

c) Ø başlangıç durumu; bir mantis rakamı veya bir puan bekliyorum.

1 – mantisin ilk kısmının rakamını okuyun; başka bir rakam veya nokta veya E bekleniyor.

2 noktalı okuma; kesirli bir rakam veya karakter bekleniyor E.

3 - mantisin kesirli kısmının rakamını okuyun; başka bir rakam veya karakter bekleniyor E.

4 - E sembolü okundu; +, - veya üslü rakamlar bekleniyor.

5 - emrin işareti okundu; Sipariş hanesini bekliyorum.

6 - sipariş numarasını okuyun; başka bir numara bekliyoruz.

7 – giriş dizesinin 1. karakteri olarak bir nokta okundu; mantisin kesirli kısmının zorunlu bir rakamını beklemek.

eR- hata durumu.

2. Sonlu bir otomat için bir devre ve geçiş tablosu oluşturun.

Oklarla işaretlenmeyen tüm geçişler Er hata durumuna yol açar.

					İzin verilebilirlik








eR

Burada tüm boş hücreler Er hata durumuna geçişe karşılık gelir.

3.Ortaya çıkan otomatı minimum forma getirin.

Sonlu otomatları optimize etmenize, yani otomatın yedek durumlarını bulmanıza olanak tanıyan özel matematiksel yöntemler vardır. Otomatın minimum forma indirilmesi için algoritmalar vardır. Böyle bir algoritmanın uygulanmasının sonuçlarından, 2 ~ 3 durumlarının denkliği ortaya çıkar.

Otomatın geçiş diyagramına bakarak tüm durumların ulaşılabilir olduğunu doğrulamak kolaydır. Bu nedenle, minimum indirgenmiş otomat elde etmek için, durum 2 ve 3'ün birleştirilmesiyle çarpanlara ayırma işlemi yapılmalıdır.

Daha fazla açıklamaya kolaylık sağlamak için durumları şu şekilde yeniden adlandıracağız:

Aşağıda yeni durum makinesi geçiş diyagramı ve tablosu yer almaktadır.

Yeni atlama tablosu:








eR

İşlemci prosedürü çağrı tablosu:

	2 A		7 A
	2 B	4 A	3 A
	3 B	4 B
	6 A			5 A
	6 B
	6 C
	3 C
eR

4. Satır sonu karakterini işleyen bir işlemci oluşturun.

(Tablodaki tüm boş hücreler, giriş dizesini reddeden "HAYIR" prosedürüne yapılan bir çağrıya karşılık gelir). Evet prosedürü, bir girdi zincirini kabul ederek ve işlemenin sonucunu döndürerek otomatı sonlandırır.

5. İşlemci atlamalarını prosedür adlarıyla tamamlayın.

Kolaylık sağlamak için, bu durumda, prosedürün adı, Latin alfabesinin sıralı harfiyle desteklenen, otomatın geçtiği durumun numarasından oluşturulur (ayrıca şekildeki diyagrama bakın).

Not: İşlemcinin bir hata mesajı vermesi gerekiyorsa, her bir hata türünün işlenmesine yönelik prosedürler için tanımlamaların yapılması ve tablonun tüm boş hücrelerinin bunlarla doldurulması gerekir.

6. Makinenin sonucu elde etmesi için gerekli kayıtları - değişkenleri girin.

Sayı – sayının önemli kısmının kaydı (tamsayı).

Emir– sipariş kaydı (tamsayı).

Tezgah– (tam sayıdan) sonraki rakam sayacının kaydı.

İmza- (±1) – sipariş işareti.

7. Tabloya uygun olarak çağrılan ve işlemci kayıtlarının değerlerinin işlendiği prosedürleri açıklayınız.

2a: Sayı:= c

2v: Sayı := 10 * Sayı+ c

3 A: Tezgah := 0

3c: Tezgah := Tezgah + 1

Sayı := 10 * Sayı+ c

3'ler: Sayı:= c; Tezgah =: 1

4a: Tezgah =: 0

5a: İmza:= (a='+' ise +1 veya a='-' ise -1) (burada a giriş karakteridir.)

6a: İmza := +1

Emir:= c

6c: Emir:= c

6'lar: Emir := 10 * Emir+ c

Evet 1: Emir := 0

Evet2: Emir:= -Sayaç

Evet: 3: Emir := İmza * Emir - Tezgah

Burada Æ sembolü herhangi bir eylemin olmadığını, yani boş bir prosedürü belirtir. Bir tamsayı kaydına bir karakter atandığı durumlarda (örneğin: Tezgah\u003d q), bir rakam sembolünün örtülü olarak onun tarafından belirtilen bir sayıya dönüştürülmesini kastediyoruz.

7. Otomatın her geçişinin en az bir kez gerçekleştirilmesi için otomatın (prosedürün) bir veya daha fazla zincir üzerindeki çalışmasını kontrol edin.

Örnek olarak, aşağıdaki üç girdi zincirini işlemek için otomatın çalışmasını düşünün. Parantez içindeki değerler işlemci çıkışındaki Sayı ve Sıra kayıtlarının beklenen değerini belirtir.

a) 67,89E-12┤ (6789, -14)

b) 2E3┤ (2,3)

c) 0,89┤ (3,-1)

giriş karakteri	Duruma değiştir prosedür	Değerleri kaydet
giriş karakteri	Duruma değiştir prosedür	Sayı	Emir	Tezgah	İmza
	1 (başlangıç)
		6
		67
		67		0
		*678*		1
		*6789*		2

					-1


		*6789*	*-14*
	1 (başlangıç)
		2
				0
			3		+1
		2	3
	1 (başlangıç)

		8		1
		89
		89	-2

Otomatın sonucu nihai durumuna göre belirlenir.

Sonlu bir otomat belirlemek için çeşitli seçenekler vardır. Örneğin, bir durum makinesi beş parametreyle belirtilebilir: burada:

Otomat, giriş dizesinin bir karakterini okuyarak q 0 durumunda başlar. Okunan karakter, geçiş fonksiyonuna uygun olarak otomasyonu Q'dan yeni bir duruma aktarır. Giriş sözcüğünü (sembol dizisi) okumayı tamamladıktan sonra otomat kendisini kabul etme durumlarından birinde bulursa, o zaman sözcük otomat tarafından "kabul edilir". Bu durumda verilen otomatın diline ait olduğu söylenir. Aksi takdirde "reddedildi" kelimesi.

Durum makineleri pratikte, örneğin ayrıştırıcılarda, sözcük analizcilerinde ve model tabanlı yazılım testlerinde yaygın olarak kullanılmaktadır.

Açıklamanın diğer yolları

Durum diyagramı ( ya da bazen geçiş grafiği) - durum kümesinin ve geçiş fonksiyonunun grafiksel gösterimi. Köşeleri uzay aracının durumları, kenarları bir durumdan diğerine geçişler ve bu geçişin gerçekleştiği semboller olan yüklü tek yönlü bir grafiktir. Eğer q1 durumundan q2 durumuna geçiş aşağıdaki durumlardan biri ile gerçekleştirilebiliyorsa: birçok semboller varsa hepsi diyagram yayının (grafiğin bir dalı) üzerinde etiketlenmelidir.
Atlama tablosu- δ fonksiyonunun tablo halinde gösterimi. Tipik olarak böyle bir tabloda her satır bir duruma karşılık gelir ve her sütun bir geçerli giriş karakterine karşılık gelir. Satır ve sütunun kesişimindeki hücre, otomatın girişte belirli bir durumda olduğu durumda verilen sembolü alması durumunda gerçekleştirmesi gereken eylemi içerir.

determinizm

Sonlu otomatlar deterministik ve deterministik olmayan olarak ikiye ayrılır.

Deterministik durum makinesi

Deterministik bir sonlu otomat (DFA), her giriş sembolü dizisi için, otomatın mevcut durumdan geçebileceği yalnızca bir durumun bulunduğu bir otomattır.
Deterministik olmayan bir sonlu otomat (NFA), deterministik bir otomatın genelleştirilmesidir. Otomatların determinizmsizliği iki şekilde elde edilir:

Boş bir ε dizesiyle etiketlenmiş geçişler var	Çeşitli geçişler aynı sembolle etiketlenmiş olarak aynı durumdan çıkar

Otomatın şu şekilde verildiği durumu ele alırsak: , burada:

Sonra belirlenimsizliğin üçüncü işareti ortaya çıkıyor - otomat için birkaç başlangıç (başlangıç) durumunun varlığı.

"Deterministik olmayan herhangi bir sonlu otomatın, dilleri çakışacak şekilde deterministik bir otomata dönüştürülebileceğini" belirten bir teorem vardır (bu tür otomatlara eşdeğer denir). Ancak, eşdeğer DFA'daki durum sayısı, en kötü durumda, orijinal NFA'nın durum sayısının artmasıyla birlikte katlanarak arttığından, pratikte böyle bir belirleme her zaman mümkün değildir. Ek olarak, çıktılı sonlu otomatlar genellikle belirsizdir.

Son iki açıklama nedeniyle, deterministik olmayan sonlu otomatların daha karmaşık olmasına rağmen, NFA'lar ağırlıklı olarak metin işlemeyle ilgili görevler için kullanılır.

Otomata ve normal diller

Bir otomat için, Σ alfabesinde bir dil (bir kelime kümesi) tanımlanabilir. dır-dir- bu, otomatın başlangıç durumundan F kümesinin durumlarından birine geçtiği girişte kelimelerin adıdır.

Uzmanlaşmış programlama dilleri

SFC (Sıralı Fonksiyon Tablosu) dili, endüstriyel mantık denetleyicilerini (PLC'ler) programlamak için yaygın olarak kullanılan grafiksel bir programlama dilidir.

SFC'de bir program, geçişlerle birbirine bağlanan adımların şematik bir dizisi olarak tanımlanır.

Durum makineleri kullanılarak modellerin geliştirilmesi

Sonlu otomatlar, paralel işleme sistemlerinin modellerini oluşturmanıza olanak tanır, ancak böyle bir modeldeki paralel süreçlerin sayısını değiştirmek için modelin kendisinde önemli değişiklikler yapmanız gerekir. Ayrıca sonlu bir otomat üzerinde karmaşık bir model geliştirmeye çalışmak, otomatın durum sayısında hızlı bir artışa yol açacak ve bu da sonuçta böyle bir modelin geliştirilmesini son derece sıkıcı hale getirecektir. Yukarıda belirtildiği gibi, son problem deterministik olmayan bir otomat kullanılarak çözülebilir.

Notlar

Ayrıca bakınız

Sıralı mantık (Sıralı mantık)

Bağlantılar

Otomata teorisi / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu.Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorents, A. F. Petrenko, V. P. Chapenko // Olasılık teorisi. Matematik istatistikleri. Teorik sibernetik. - M.: VINITI, 1976. - T. 13. - S. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Otomasyon problemlerini çözmek için sonlu otomatların kullanımı
Django çerçevesi için Python'da bir durum makinesinin örnek uygulaması

Wikimedia Vakfı. 2010.

Keynes, John Maynard
Durum diyagramı (otomata teorisi)

Diğer sözlüklerde "Sonlu Makine" nin ne olduğunu görün:

durum makinesi- KA Sonlu sayıda duruma sahip bir otomatı tanımlayan hesaplamalı bir model. CA'lar programlamada, örneğin derleyicilerin sözcüksel analizörlerinde yaygın olarak kullanılır. durum makinesi Sıra spesifikasyonu… …

durum makinesi- sonlu hafızaya sahip bir cihazın matematiksel modeli. Durum makinesi bir dizi giriş ayrık sinyalini bir dizi çıkış sinyaline dönüştürür. Senkron ve asenkron durum makineleri arasında ayrım yapın. İngilizce: Sonlu durum makinesi Bakınız ... Finansal kelime dağarcığı

durum makinesi- baigtinis automatas statusas T sritis automatika atitikmenys: angl. sonlu otomat; sonlu durum makinesi vok. Endlicher Otomat, m; Finalautomat, m rus. durum makinesi, m pranc. finali otomatikleştir, m; sonunu otomatikleştir, m; terminali otomatikleştir, m;… … Otomatik terminų žodynas

SONLU OTOMATİK- bir dizi duruma ve ayrıca bir dizi giriş ve çıkış sinyaline sahip olan bir otomat sonludur. K. a. teknik bir model olabilir. cihazlar (bilgisayar, röle cihazı) veya biyol. sistemler (idealleştirilmiş hayvan sinir sistemi). önemli… … Büyük ansiklopedik politeknik sözlük

Modüler tasarımda sonlu durum makinesi- — [Ya.N. Luginsky, M.S. Fezi Zhilinskaya, Yu.S. Kabirov. İngilizce Rusça Elektrik Mühendisliği ve Enerji Endüstrisi Sözlüğü, Moskova, 1999] Elektrik mühendisliği konuları, temel kavramlar EN sonlu modüler otomasyon ... Teknik Çevirmen El Kitabı

kullanılabilirlik durumu makinesi- (İTÜ T Y.1711). Telekomünikasyon konuları, temel kavramlar EN kullanılabilirlik durumu machineASM ... Teknik Çevirmen El Kitabı

Hafızalı durum makinesi- Belleğe sahip bir durum makinesi, davranışı hem giriş koşullarına hem de önceki duruma bağlı olan bir cihazın matematiksel modelidir. Belleğe sahip sonlu durum makinesini tanımlamak için operatör şemalarının dilleri kullanılır, düzenli ... ... Wikipedia

deterministik durum makinesi- — [Ya.N. Luginsky, M.S. Fezi Zhilinskaya, Yu.S. Kabirov. İngilizce Rusça Elektrik Mühendisliği ve Enerji Endüstrisi Sözlüğü, Moskova, 1999] Elektrik mühendisliği konuları, temel kavramlar EN sonlu deterministik otomat ... Teknik Çevirmen El Kitabı

Moore hafif makineli tüfek- (ikinci tür otomat) hesaplama teorisinde, sonlu bir otomat, sinyalin çıkış değeri, yalnızca bu otomatın mevcut durumuna bağlıdır ve Mealy otomatının aksine, girişe doğrudan bağlı değildir. değerler. Moore'un hafif makineli tüfeğinin adı ... Wikipedia

Otomatın sonucu nihai durumuna göre belirlenir.

Sonlu bir otomat belirlemek için çeşitli seçenekler vardır. Örneğin, bir durum makinesi beş parametreyle belirtilebilir: burada:

Durum makineleri pratikte, örneğin ayrıştırıcılarda, sözcük analizcilerinde ve model tabanlı yazılım testlerinde yaygın olarak kullanılmaktadır.

Açıklamanın diğer yolları

Durum diyagramı ( ya da bazen geçiş grafiği) - durum kümesinin ve geçiş fonksiyonunun grafiksel gösterimi. Köşeleri uzay aracının durumları, kenarları bir durumdan diğerine geçişler ve bu geçişin gerçekleştiği semboller olan yüklü tek yönlü bir grafiktir. Eğer q1 durumundan q2 durumuna geçiş aşağıdaki durumlardan biri ile gerçekleştirilebiliyorsa: birçok semboller varsa hepsi diyagram yayının (grafiğin bir dalı) üzerinde etiketlenmelidir.
Atlama tablosu- δ fonksiyonunun tablo halinde gösterimi. Tipik olarak böyle bir tabloda her satır bir duruma karşılık gelir ve her sütun bir geçerli giriş karakterine karşılık gelir. Satır ve sütunun kesişimindeki hücre, otomatın girişte belirli bir durumda olduğu durumda verilen sembolü alması durumunda gerçekleştirmesi gereken eylemi içerir.

determinizm

Sonlu otomatlar deterministik ve deterministik olmayan olarak ikiye ayrılır.

Deterministik durum makinesi

Deterministik bir sonlu otomat (DFA), her giriş sembolü dizisi için, otomatın mevcut durumdan geçebileceği yalnızca bir durumun bulunduğu bir otomattır.
Deterministik olmayan bir sonlu otomat (NFA), deterministik bir otomatın genelleştirilmesidir. Otomatların determinizmsizliği iki şekilde elde edilir:

Boş bir ε dizesiyle etiketlenmiş geçişler var	Çeşitli geçişler aynı sembolle etiketlenmiş olarak aynı durumdan çıkar

Otomatın şu şekilde verildiği durumu ele alırsak: , burada:

Sonra belirlenimsizliğin üçüncü işareti ortaya çıkıyor - otomat için birkaç başlangıç (başlangıç) durumunun varlığı.

Son iki açıklama nedeniyle, deterministik olmayan sonlu otomatların daha karmaşık olmasına rağmen, NFA'lar ağırlıklı olarak metin işlemeyle ilgili görevler için kullanılır.

Otomata ve normal diller

Uzmanlaşmış programlama dilleri

SFC (Sıralı Fonksiyon Tablosu) dili, endüstriyel mantık denetleyicilerini (PLC'ler) programlamak için yaygın olarak kullanılan grafiksel bir programlama dilidir.

SFC'de bir program, geçişlerle birbirine bağlanan adımların şematik bir dizisi olarak tanımlanır.

Durum makineleri kullanılarak modellerin geliştirilmesi

Notlar

Ayrıca bakınız

Sıralı mantık (Sıralı mantık)

Bağlantılar

Otomata teorisi / E. A. Yakubaitis, V. O. Vasyukevich, A. Yu.Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorents, A. F. Petrenko, V. P. Chapenko // Olasılık teorisi. Matematik istatistikleri. Teorik sibernetik. - M.: VINITI, 1976. - T. 13. - S. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Otomasyon problemlerini çözmek için sonlu otomatların kullanımı
Django çerçevesi için Python'da bir durum makinesinin örnek uygulaması

Wikimedia Vakfı. 2010.

Keynes, John Maynard
Durum diyagramı (otomata teorisi)

Diğer sözlüklerde "Sonlu Makine" nin ne olduğunu görün:

kullanılabilirlik durumu makinesi- (İTÜ T Y.1711). Telekomünikasyon konuları, temel kavramlar EN kullanılabilirlik durumu machineASM ... Teknik Çevirmen El Kitabı

Makalede basit durum makineleri ve bunların C++'ta anahtar yapıları, çalışma zamanı tabloları ve Boost Statechart kitaplığı kullanılarak uygulanması anlatılmaktadır.

giriiş

Kabaca söylemek gerekirse, sonlu durum makinesi (Sonlu Durum Makinesi), kullanıcının gözünde, içine bir şeyler aktarabileceğiniz ve oradan bir şeyler alabileceğiniz bir kara kutudur. Bu, karmaşık bir algoritmayı gizlemenize olanak tanıyan çok kullanışlı bir soyutlamadır, ayrıca durum makineleri çok verimlidir.

Sonlu otomatlar, durumlar ve geçişlerden oluşan diyagramlar olarak gösterilir. Basit bir örnekle açıklayayım:

Muhtemelen tahmin ettiğiniz gibi bu bir ampul durum diyagramıdır. Başlangıç durumu siyah bir daire ile gösterilir, geçişler oklarla gösterilir, bazı oklar imzalanır - bunlar, sonrasında makinenin başka bir duruma geçtiği olaylardır. Yani başlangıç durumundan hemen duruma geçiyoruz ışık kapalı- lamba yanmıyor. Düğmeye basarsanız makine durumunu değiştirecek ve işaretli oku takip edecektir. butona basınız, devlete ışık açık- lamba açık. Düğmeye bastıktan sonra ok işaretiyle bu durumdan tekrar bu duruma geçebilirsiniz. ışık kapalı.

Atlama tabloları da yaygın olarak kullanılmaktadır:

Makinelerin pratik uygulaması

Durum makineleri programlamada yaygın olarak kullanılmaktadır. Örneğin cihazın çalışmasını bir otomat şeklinde hayal etmek çok uygundur. Bu, kodu daha basit ve denemeyi ve bakımı daha kolay hale getirecektir.

Ayrıca, sonlu otomatlar her türlü metin ayrıştırıcı ve analizörünü yazmak için kullanılır, bunların yardımıyla alt dizeleri etkili bir şekilde arayabilirsiniz, düzenli ifadeler de sonlu bir otomat'a çevrilir.

Örneğin bir metindeki sayıları ve kelimeleri saymak için bir otomat uygulayacağız. Başlangıç olarak, bir sayının, boşluk karakterleriyle (boşluk, sekme, satır besleme) çevrelenmiş, 0'dan 9'a kadar isteğe bağlı uzunlukta bir rakam dizisi olacağını kabul edelim. Bir kelime, harflerden oluşan ve aynı zamanda boşluk karakterleriyle çevrelenmiş, keyfi uzunluktaki bir dizi olarak kabul edilecektir.

Bir diyagram düşünün:

Başlangıç durumundan duruma ulaşıyoruz başlangıç. Mevcut karakteri kontrol ediyoruz ve eğer bir harf ise duruma gidiyoruz Kelime olarak işaretlenen ok boyunca mektup. Bu durum, bir kelimeyi ele aldığımız anda, diğer simgelerin analizinin bu varsayımı doğrulayacağını ya da çürüteceğini varsayar. Bu nedenle, bir sonraki karakteri düşünün, eğer bir harfse, o zaman durum değişmez (şu şekilde işaretlenmiş dairesel oka dikkat edin) mektup). Karakter bir harf değilse ancak bir boşluk karakterine karşılık geliyorsa, bu, varsayımın doğru olduğu ve kelimeyi bulduğumuz anlamına gelir (ok boyunca hareket ederiz) Uzay bir duruma başlangıç). Eğer sembol ne harf ne de boşluk ise, o zaman varsayımda hata yapmışızdır ve düşündüğümüz dizi bir kelime değildir (oku takip ediyoruz) Bilinmeyen bir duruma Atlamak).

Hünerli Atlamak bir boşluk karakteriyle karşılaşıncaya kadar kalıyoruz. Boşluk bulunduktan sonra oku takip ediyoruz Uzay bir duruma başlangıç. Arama modelimize uymayan satırı tamamen atlamak için bu gereklidir.

Devlete geçişten sonra başlangıç arama döngüsü baştan itibaren tekrarlanır. Sayı tanıma dalı kelime tanıma dalına benzer.

Anahtar talimatlarını kullanan otomat

Birincisi olası durumlardır:

Bundan sonra, geçerli karakteri otomatın içine kaydırarak dize üzerinde yineleme yaparız. Otomatın kendisi, ilk önce mevcut durum bölümüne geçişi gerçekleştiren bir switch ifadesidir. Bölümün içinde, olaya (gelen karakter) bağlı olarak mevcut durumu değiştiren bir if-else yapısı vardır:

const size_t uzunluk = metin.uzunluk () ; for (size_t i = 0 ; i != uzunluk; ++ i) ( const char current = text[ i] ; switch (state) ( case State_Start: if (std:: isdigit (current)) ) ( state = State_Number; ) else if (std:: isalpha (current) ) ( state = State_Word; ) break ; case State_Number: if (std:: isspace (current) ) (

Burada şemaya bakıyoruz - mevcut durum sayı, etkinlik Uzay(boşluk karakteriyle karşılaşıldı), bu da bir sayının bulunduğu anlamına gelir:

BulunanNumber() ; durum = Durum_Başlangıç; ) else if (! std:: isdigit (current) ) ( state = State_Skip; ) break ; case State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (current) ) ( state = State_Skip; ) break ; case State_Skip: if (std:: isspace (current) ) ( state = State_Start; ) break ; ))

Sonuç:

Yüksek verim

Basit algoritmalar için uygulama kolaylığı

- bakımı zor

Çalışma Zamanı Yorumlaması

Bu yaklaşımın fikri basittir - bir geçiş tablosu oluşturmanız, onu doldurmanız ve ardından bir olay meydana geldiğinde tabloda aşağıdaki durumu bulmanız ve geçişi yapmanız gerekir:

enum Events( Event_Space, Event_Digit, Event_Letter, Event_Unknown ) ; void ProcessEvent(Olaylar olayı); ... struct Geçiş ( BaseState_ Durumlarını; Olaylar Olay_; TargetState_ Durumlarını Durumları; ) ; void AddTransition(Durumlardan Durumlar, Olaylar olayı, Durumlardan Duruma) ; ... typedef std::vector< transition>Geçiş Tablosu; Geçiş Tablosu Geçişleri_; Durumlar CurrentState_;

Tablonun doldurulması:

AddTransition(Durum_Başlangıç, Olay_Digit, Durum_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(Durum_Number, Event_Space, State_Start) ; AddTransition(Durum_Number, Olay_Harf, Durum_Atlama) ; AddTransition(Durum_Number, Olay_Bilinmeyen, Durum_Atlama) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

Oldukça açık bir şekilde ortaya çıktı. Netlik için yapılacak ödeme, makinenin daha yavaş çalışması olacaktır ki bu da tesadüfen çoğu zaman önemli değildir.

Otomatın belirli olayların meydana gelmesi üzerine bazı kodları bildirebilmesi için yapıya geçişle ilgili bilgileri ekleyebilirsiniz ( geçiş) işlev işaretçisi ( aksiyon) çağrılacak:

typedef void (DynamicMachine:: * Eylem) () ; struct Geçiş ( BaseState_ Devletleri; Olaylar Olay_; TargetState_ Durumlarını; Eylem Eylem_; ); ... void AddTransition(Durumdan Durumlar, Olaylar olayı, Durumdan Duruma, Eylem eylemi) ; ... AddTransition (State_Number, Event_Space, State_Start ve DynamicMachine:: FoundNumber ) ;

Sonuç:

Esneklik ve görünürlük

Bakımı daha kolay

- Anahtar bloklarına kıyasla daha düşük performans

Yürütme zamanının yorumlanması. Hız optimizasyonu

Görünürlük hızla birleştirilebilir mi? Bir otomatın anahtar bloklarına dayalı bir otomat kadar verimli olması pek olası değildir, ancak aradaki farkı kapatmak mümkündür. Bunu yapmak için, geçiş hakkında bilgi edinmek için bir arama yapmamak, durum ve olay sayısına göre bir seçim yapmak için tablodan bir matris oluşturmak gerekir:

Sonuç, bellek tüketimi pahasına elde edilir.

Sonuç:

Esneklik, görünürlük

Etkili

- Bellek tüketimi (muhtemelen önemsiz)

Durum Grafiğini Artır

Bir durum makinesini kendiniz uygulamanın çeşitli yollarını tartıştık. Bir değişiklik olarak, Boost'tan otomata oluşturmak için bir kütüphane düşünmeyi öneriyorum. Bu kütüphane çok güçlüdür, önerilen özellikler çok karmaşık sonlu durum makineleri oluşturmanıza olanak tanır. Buna çok kısaca bakacağız.

O halde önce olayları tanımlayalım:

namespace Events( struct Digit : boost::statechart::event< Digit>( ) ; struct Letter : boost::statechart::event< Letter>( ) ; struct Space : boost::statechart::event< Space>( ) ; structUnknown : boost::statechart::event< Unknown> { } ; }

Makinenin kendisi (şablonun ikinci parametresinin başlangıç durumu olduğuna dikkat edin):

struct Makine: boost::statechart::state_machine< Machine, States:: Start > { } ;

Ve devletlerin kendileri. Durumların içinde, geçişleri açıklayan bir türün tanımlanması gerekir ( reaksiyonlar) ve birden fazla geçiş varsa bunları boost::mpl::list türü listesinde listeleyin. İkinci şablon parametresi basit_durum– arabayı tanımlayan tip. Geçişler, geçiş şablonu parametreleriyle tanımlanır; Etkinlik - Sonraki Durum:

ad alanı Durumları ( struct Başlangıç : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reaksiyon; ) ); yapı Numarası: boost::statechart::simple_state< Number, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Letter , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reaksiyon; ) ); struct Word: boost::statechart::simple_state< Word, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Digit , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reaksiyon; ) ); struct Atla: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >reaksiyonlar; ) ); )

Makine inşa edilmiştir, yalnızca onu başlatmak için kalır ve şunları kullanabilirsiniz:

Makine makinesi; makine.initiate(); ...machine .process_event(Events::Space() ) ;

Sonuç:

Esneklik, genişletilebilirlik

- Yeterlik

Verim

Oluşturulan otomatların hızını kontrol etmek için bir test programı yazdım. Makineler aracılığıyla ~ 17 MB boyutunda metni sürdüm. İşte koşunun sonuçları:

Metin yükleniyor Metin uzunluğu: 17605548 bayt 0,19 sn BoostMachine Words çalıştırılıyor: 998002, sayılar: 6816 0,73 sn DynamicMachine Words çalıştırılıyor: 998002, sayılar: 6816 0,56 sn FastDynamicMachine Words çalıştırılıyor: 998002, sayılar: 6816 0,29 sn SimpleMa chine Words çalıştırılıyor : 998002, sayılar : 6816 0,20s

İncelenmemiş ne kaldı

Sonlu otomatların birkaç uygulaması daha ortaya çıkarılmadı (http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml ve http://www.rsdn.ru/article/alg/FiniteStateMachine.xml'yi öneririm), jeneratörler Açıklamalardan otomatlar oluşturan, Boost 1.44.0 sürümündeki Meta Durum Makinesi kütüphanesinin yanı sıra durum makinelerinin resmi açıklamaları. Meraklı okuyucu yukarıdakilerin hepsine aşina olabilir.

Sonlu otomat teorisi

Otomata teorisi, derleyici oluşturma teorisinin temelini oluşturur. Durum makinesi temel kavramlardan biridir. Bir otomat, gerçek hayattaki bir teknik cihaz anlamına gelmez, ancak böyle bir cihaz yapılabilir, ancak özellikleri ve davranışları bilgisayardaki bir program kullanılarak taklit edilebilecek bazı matematiksel modeller. Sonlu otomat, otomat teorisi modellerinin en basitidir ve kural olarak diğer tüm otomat türleri için bir kontrol cihazı görevi görür. Durum makinesinin bir dizi özelliği vardır:

· Durum makinesi bir dizi kolay derleme görevini çözebilir. Bir sözcük bloğu neredeyse her zaman bir durum makinesinin etrafında oluşturulur.

Sonlu durum makinesinin çalışması yüksek hız ile karakterize edilir.

· Durum makinesi simülasyonu sabit miktarda bellek gerektirir, bu da bellek yönetimini basitleştirir.

· Sonlu otomatları tasarlamanıza ve basitleştirmenize olanak tanıyan bir dizi teorem ve algoritma vardır.

Literatürde durum makinesinin birkaç mükemmel tanımı vardır. Ancak bunların ortak yanı, durum makinesinin, bazı giriş kümelerine ait giriş simgeleri dizilerini okuyan, sabit miktarda belleğe sahip bir bilgi işlem cihazını modellemesidir. Tanımlardaki temel farklılıklar otomatın çıktıda ne yaptığıyla ilgilidir. Otomatın çıktısı, verilen giriş dizisinin "izin verilebilir" olup olmadığının bir göstergesi olabilir. "Kabul edilebilir", iyi biçimlendirilmiş veya sözdizimsel olarak doğru bir dizedir. Örneğin, sayısal bir sabiti temsil etmesi gereken bir dize, iki ondalık nokta içeriyorsa hatalı kabul edilir.

Tanım: Durum makinesi, aşağıdaki nesneler kullanılarak tanımlanan resmi bir sistemdir:

sınırlı sayıda giriş sembolü;

sonlu bir durum kümesi;

· her bir çifti (mevcut durum, giriş sembolü) yeni bir durumla ilişkilendiren bir geçiş fonksiyonu;

başlangıç hali;

· kabul eden veya nihai olarak seçilen durumların bir alt kümesi.

Örnek. Sıfırlardan ve birlerden oluşan rastgele bir zincirdeki çift veya tek sayıda birleri kontrol eden bir denetleyicinin çalışmasını analiz edelim. Karşılık gelen sonlu otomatın tek sayıda bir içeren tüm dizelere "izin vermesi" ve çift sayıda dizeyi "reddetmesi" gerektiğini varsayalım. Bu otomata "eşlik denetleyicisi" adını verelim. Otomatın girişine 0 ve 1 dışındaki sembollerin beslenemeyeceğine inanıyoruz. Yani denetleyicinin giriş alfabesi set (0, 1)'dir. Zamanın belirli bir anında sonlu otomatın yalnızca bir giriş sembolüyle ilgilendiğini ve sonlu bir durum kümesi kullanarak giriş zincirinin önceki sembolleri hakkındaki bilgileri depoladığını varsayıyoruz. Durumlar kümesi olarak (çift, tek) kümesini ele alacağız, bu durumlardan biri ilk durum olarak seçilmelidir. İlk adımda okuma birimlerinin sayısı sıfıra eşit olduğundan ve sıfır bir çift sayı olduğundan durum (çift) olsun. Bir sonraki giriş sembolünü okurken otomatın durumu ya değişir ya da aynı kalır ve yeni durumu giriş sembolüne ve mevcut duruma bağlıdır. Bu hal değişikliğine geçiş denir.

Otomatın çalışması matematiksel olarak d(Stack, x) = Snew formundaki bir geçiş fonksiyonuyla açıklanabilir. Aksi takdirde şu şekilde yazılabilir:

d(çift, 0) = çift d (çift, 1) = tek.

d(tek, 0) = tek. d (tek, 1) = çift

Denetleyicinin tek bir kabul durumu vardır, ODD ve EVEN bir "reddetme" durumudur. 1101 zinciri girişine beslendiğinde otomatın geçiş sırasını yansıtalım.

EVEN ® ODD ® EVEN® EVEN® ODD

Böyle bir otomatın geçiş tablosu şu şekildedir: