Sözlüksel analiz. Düzenli diller ve sonlu otomatlar
kayıttaki işlem ve parantezlerin sembol ve işaretlerinin alfabesindeki toplam karakter sayısına göre r .temel. Uzunluk 1: ve ifadeleri için otomatlar aşağıdaki şekilde gösterilmiştir.
Pirinç. 5.1.
Bu üç otomattan her birinin sahip olduğuna dikkat edin. nihai durumlar kümesi bir devletten oluşur.
indüksiyon adımı. Şimdi varsayalım ki her biri için Düzenli ifade uzunluk<= k
построен соответствующий
НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное
Düzenli ifade r uzunluğu k+1 . Son işleme bağlı olarak, üç biçimden birine sahip olabilir: (r 1 + r 2), (r 1 r 2) veya (r 1) * . Sırasıyla L r1 ve L r2 dillerini tanıyan NFA'lar olsun ve olsun. Genelliği kaybetmeden, farklı durumlara sahip olduklarını varsayacağız: 
.
Ardından, diyagramı Şekil 1'de gösterilen NFA . 5.2, dili tanır.
Pirinç. 5.2.
Bu makine var durum kümesi, burada q 0 yeni bir başlangıç durumudur, qf yeni (benzersiz!) bir son durumdur ve program M 1 ve M 2 otomat programlarını ve dört yeni geçiş komutunu içerir: . Açıkçası, NFA M tarafından tanınan dil, L (M1) ve L(M2)'den gelen tüm kelimeleri içerir. Öte yandan, her kelime q 0 ila q f alır ve ilk adımdan sonra onu taşıyan yol q 0 1 veya q 0 2'den geçer. M 1 ve M 2 durumları kesişmediğinden, ilk durumda bu yol q f'ye yalnızca q f 1'den bir geçişle ulaşabilir ve sonra 
. Benzer şekilde, ikinci durumda .
İfade için, Lr dilini tanıyan NFA'nın diyagramı aşağıdaki şekilde gösterilmiştir.
Pirinç. 5.3.
Bu makine var durum kümesi 
, başlangıç durumu q 0 = q 0 1 , son durum q f = q f 2 ve program M 1 ve M 2 otomat programlarını ve bir yeni talimat içerir - son durum M 1'den başlangıç durumu M 2'ye geçiş , yani. . Burada ayrıca q 0 = q 0 1'den q f = q f 2'ye giden herhangi bir yolun q f 1'den q 0 2'ye a -geçişinden geçtiği açıktır. Bu nedenle, M tarafından izin verilen herhangi bir kelime, L M1)'deki bazı kelimelerin L M2)'deki bazı kelimelerle birleştirilmesidir ve bu tür kelimelerin herhangi bir şekilde birleştirilmesine izin verilir. Bu nedenle, NFA M dili tanır.
r = r 1 * olsun. L r =L r1* = L M1 * dilini tanıyan NFA'nın şeması şekil 2'de gösterilmiştir. 5.3.
Pirinç. 5.3.
Bu makine var durum kümesi, burada q 0 yeni bir başlangıç durumudur, qf yeni (benzersiz!) bir son durumdur ve program M1 otomat programını ve dört yeni geçiş komutunu içerir: . Açıkça, . Yinelemenin tanımı gereği, boş olmayan w sözcüğü için 
bazı k >= 1 için w kelimesi k alt sözcüğe bölünebilir: w=w 1 w 2 ... w k ve hepsi bu. Her i= 1,... ,k için wi kelimesi q 0 1 ile q f 1'i eşler. O zaman M diyagramındaki w kelimesi için bir yol vardır.
Buradan, . Tersine, eğer bir kelime q 0'ı qf'ye çevirirse, o zaman ya var olur ya da -geçiş yoluyla q 0 1 yoluyla taşınır, sonunda q f 1'den -geçiş yoluyla qf ile biter. Bu nedenle, böyle bir kelime.
Teorem 4.2 ve 5.1'den doğrudan elde ederiz
Sonuç 5.1. Her biri için Düzenli ifade bu ifadeyle temsil edilen dili tanıyan deterministik sonlu bir otomat verimli bir şekilde inşa edilebilir.
Bu ifade bir örnektir sentez teoremleri: görev tanımına göre (dil olarak Düzenli ifade) onu yürüten bir program (DFA) etkili bir şekilde oluşturulmuştur. Sohbet de doğrudur - analiz teoremi.
Teorem 5.2. Her deterministik (veya deterministik olmayan) sonlu otomat için, bir kişi inşa edilebilir Düzenli ifade, bu otomat tarafından tanınan dili temsil eder.
Bu teoremin ispatı oldukça tekniktir ve dersimizin kapsamı dışındadır.
Böylece, sonlu otomata dilleri sınıfının sınıfla çakıştığı sonucuna varabiliriz. düzenli diller. Aşağıda, basitçe onu arayacağız otomata dilleri sınıfı.
Teorem 5.1'in ispatında oluşturulan otomat M r
Temel Tanımlar Σ alfabesindeki düzenli ifadeler ve bunların gösterdiği düzenli kümeler tekrarlı olarak şu şekilde tanımlanır: 1) düzenli bir kümeyi ifade eden bir düzenli ifade; 2) e, düzenli bir kümeyi (e) gösteren bir düzenli ifadedir; 3) bir Σ ise, o zaman a normal kümeyi (a) gösteren bir düzenli ifadedir; 4) p ve q, P ve Q düzenli kümelerini gösteren düzenli ifadeler ise, o zaman a) (p+q) P Q'yu gösteren bir düzenli ifadedir; b) pq, PQ'yu ifade eden düzenli bir ifadedir; c) p*, P*'yi gösteren bir düzenli ifadedir; 5) başka hiçbir şey düzenli bir ifade değildir.
Temel tanımlar Önceliklendirme: * (yineleme) – en yüksek öncelik; birleştirme; + (birlik). Yani 0 + 10* = (0 + (1 (0*))). Örnekler: 1. 01, (01) anlamına gelir; 2. 0* - (0*); 3. (0+1)* - (0, 1)*; 4. (0+1)* 011 - 0 ve 1'den oluşan ve 011 dizisiyle biten tüm dizilerin kümesi anlamına gelir; 5. (a+b) (a+b+0+1)*, a veya b ile başlayan tüm dizilerin (0, 1, a, b)* kümesi anlamına gelir.
Lemmanın ana tanımları: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
RT ve RM RM iletişimi, RT tarafından oluşturulan dillerdir. Örneğin: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Birleştirme: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (balina, kedi) veya 5 ve 6 numaralı Önermelere göre k(u+o)m = balina + kedi (balina, kedi) . Yineleme: x = a, x* X* = (e, a, aaa, …), yani x* = e + xxx + …
RT ve RM ilişkisi Birleştirme ve birleştirme yinelemesi: (xy)* = e + xyxyxy + ... (x + y)* = e + (x + y)(x + y) + ... = = e + xx + xy + yx + yy + xxx + … Örnek: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111…). Birleşim değişmeli: x + y = y + x Birleşme değil: xy ≠ yx
RT ve PM arasındaki ilişki Öncelik örnekleri: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, …), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …). Yeni önermeler: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; vesaire.
Düzenli denklem sistemleri Düzenli katsayılı denklem X = a. X + b'nin bir çözümü vardır (en küçük sabit nokta) a*b: aa*b + b = (aa* + e)b = a*b Düzenli katsayılı denklem sistemi: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 \u003d α 20 + α 21 X 1 + α 22 X 2 + ... + α 2 n. ………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Bilinmeyenler – Δ = (X 1, X 2, …, Xn).
Düzenli denklem sistemleri Çözüm algoritması (Gauss yöntemi): Adım 1. i = 1 olarak ayarlayın. Adım 2. i = n ise, adım 4'e gidin. Aksi takdirde, Xi için denklemleri Xi = αXi + β (β = β 0) olarak yazın + βi +1 Xi+1 + … + βn.Xn). Ardından, Xi+1, …, Xn denklemlerinin sağ taraflarında Xi'yi α*β düzenli ifadesi ile değiştiririz. Adım 3. i'yi 1 artırın ve adım 2'ye dönün. Adım 4. Xn için denklemi Xn = αXn + β olarak yazın. 5. adıma gidin (i = n ile). Adım 5. Xi denklemi Xi = αXi + β şeklindedir. Xi– 1, …, X 1 denklemlerinde Xi yerine α*β koyarak Xi = α*β çıkışına yazın. Adım 6. i = 1 ise durun, aksi takdirde i 1 azaltın ve 5. adıma dönün.
DFA'nın RW'ye dönüşümü DFA M = (Q, Σ, δ, q 0, F) için Δ = Q: 1 olan düzenli katsayılara sahip bir sistem oluşturuyoruz. αij: = ; 2. δ(Xi, a) = Xj, a Σ ise αij: = αij + a; 3. Xi F veya δ(Xi,) = HALT ise, o zaman αi 0: = e. Çözdükten sonra istenen RV X 1 = q 0 olacaktır.
DFA'yı RW'ye dönüştürme Örnek: sabit noktalı bir sayı için, q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 sistemini elde ederiz. + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Burada: s sayının işaretidir, s = "+" + "-"; p – ondalık nokta, p = ". "; d - sayılar, d = "0" + "1" + ... + "9".
DFA'dan RW'ye dönüştürme Çözüm: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Üçüncü denklemden: q 3 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). Dördüncü denklemden: q 4 = dq 4 + e = d*.
DFA'yı RW'ye Dönüştür Ters: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd* + dd *(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Dolayısıyla bu DFA, RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e)'ye karşılık gelir. Basitleştirmek için: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Daha kısa bir notasyon için pozitif iterasyonu kullanabilirsiniz aa* = a*a = a+: (s + e) )(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
DFA'dan RT'ye dönüştürme DFA geçiş fonksiyonu grafiğini temel düzenli ifade işlemleriyle eşleme: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
DFA'yı RT'ye dönüştürme Daha karmaşık işlem kombinasyonları: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*
DFA'dan RW'ye dönüştürme RW (s + e)(pd+ + d+(pd* + e)) için: q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
Gerçek Zamanlı Programlama Normal İfadeleri: Birçok programlama dilinde (PHP, Java. Script, …); Eklentiler olarak uygulanır (örneğin, .NET platformu için Regex sınıfı). Yazı formlarındaki farklılıklar: x? = x + e x(1, 3) = x + xxx vb.
RT Programlama Normal İfade Sınıfı Yapıları (System.Text.Regular.Expressions): Karakter Kaçış Dizisi Yorumu b Köşeli parantez içinde kullanıldığında, "←" karakteriyle eşleşir (u 0008) t, r, n, a, f, v Tab (u 0009), satırbaşı (u 000 D), yeni satır (u 000 A), vb. c. X Kontrol karakteri (örneğin, c. C, Ctrl+C'dir, u 0003) e Escape (u 001 B) ooo Sekizli ASCII karakteri xhh Hex ASCII karakteri uhhhh Unicode karakteri Aşağıdaki karakter özel bir PB karakteri değildir. Tüm özel karakterler bu karakterle çıkarılmalıdır Örnek (örnekte örüntü ve arama dizisi verilmiş, dizide bulunan eşleşmelerin altı çizilmiştir): @"rnw+" – "rn. Burada n adet iki dizi var" .
Karakterlerin RT Alt Kümelerini Programlama. Dizinin sonu hariç herhangi bir karakter (n) Kümeden herhangi bir karakter [^xxx] Kümeden karakterler dışında herhangi bir karakter Aralıktan herhangi bir karakter ] Bir kümeyi veya aralığı diğerinden çıkar p(ad) Unicode tarafından belirtilen herhangi bir karakter kategori adı P (isim) Unicode kategorisi tarafından belirtilenler dışındaki herhangi bir karakter ad adı w Tanımlayıcıları belirtmekte kullanılan karakter kümesi W Tanımlayıcıları belirtmekte kullanılmayan karakter kümesi s Boşluklar S Boşluklar dışında her şey d Rakamlar D Rakam değil Örnekler: @ ". +" – "rn. Burada n tane iki satır var"; @"+" - "0xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0xabcfx"; @"p(Lu)" - "Şehir Işıkları"; // Lu - büyük harfler @"P(Lu)" - "Şehir"; @"p(Kirildir)" - "ha.OS"; // Dır-dir. Kiril - Rus harfleri
PB Programlama Çapası ^, A $, Z Dizisinin başında veya dizinin sonundaki "n" karakterine kadar z Dizinin sonunda G Önceki eşleşmenin bittiği yerde b Word sınır B Sözcük sınırında olmayan herhangi bir konum Örnekler: @ "G(d)" - "(1)(3)(5)(9)"; // üç eşleşme (1), (2) ve (3) @"bnS*ionb" – "ulus bağışı"; @"Bendw*b" – "son, borç verene dayanır".
RT İşlemlerini Programlama (nicelik belirteçleri) *, *? İterasyon +, +? Pozitif yineleme? , ? ? Sıfır veya bir eşleşme (n), (n)? Tam olarak n eşleşme (n, ), (n, )? En az n eşleşme (n, m), (n, m)? n'den m'ye eşleşmeler Örnekler (ilk niceleyiciler açgözlüdür, mümkün olduğu kadar çok öğe ararlar, ikincisi tembeldir, mümkün olduğunca az öğe ararlar): @"d(3, )" – "888 -5555"; @"^d(3)" - "913 -913"; @"-d(3)$" - "913 -913"; @"5+? 5" - "888 -5555"; // üç eşleşme - 55, 55 ve 55 @"5+5" - "888 -5555".
RT Programlama Gruplama () Grup otomatik olarak bir numara atadı (?:) Grubu kaydetme (?) veya (? "ad") Bir eşleşme bulunursa, adlandırılmış bir grup oluşturun (?) veya Önceden tanımlanmış bir grubu silin ve (? "ad-adı") yeni grupta önceden tanımlanan grup ile yeni grup (?imnsx:) arasında bir alt dize kaydet Gruptaki olası beş (? -imnsx:) seçeneğinden herhangi birini açar veya kapatır: i - durum duyarsız; s bir satırdır (o zaman ". " herhangi bir karakterdir); m – çok satırlı mod (“^” , “$” – her satırın başı ve sonu); n - isimsiz grupları yakalamayın; x - kalıptan çıkış yapılmayan boşlukları hariç tutun ve sayı işaretinden (#) sonra yorumları dahil edin (?=) Sıfır uzunluklu pozitif ileriye dönük iddia
RE programlama (?!) Sıfır uzunluklu negatif ileriye dönük iddia (?) İfadenin geri dönmeyen (açgözlü) kısmı Örnekler: @"(an)+" – "muz yıllıkları"; @"an+" – "muz yıllıkları"; // karşılaştır, üç eşleşme - an, an ve ann @"(? i: an)+" - "ba. NAnas yıllıkları"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://website/presentation/-112203859_437213351/image-24.jpg" alt="Programming RT Referans numarası Grup referansı k Adlandırılmış grup referansı Örnekler: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
RT Programlama Değişiklikleri $number Dizinin gruba karşılık gelen kısmını belirtilen sayıyla değiştirir $(name) Dizinin gruba karşılık gelen kısmını belirtilen adla değiştirir $$ Yerine koyar $ $& Tam sayının bir kopyasıyla değiştirin $` ile eşleşen giriş dizesinin metnini $" ile eşleşene kadar değiştir
Regex'in RT Programlama Sonuçları: Regex Matches() Match. Koleksiyon Maç Grupları() Grubu. Toplama Grup Yakalar() Yakalama. Koleksiyon Yakalamaları()
C++ CLI'de RT Programlama Örneği (Visual C++/CLR/CLR Konsol Uygulaması): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int match.Count = 0; while (m->Success) ( Console: : Write. Line(L"Match(0)", ++match.Count); for (int i = 1; i Gruplar->Say; i++) ( Grup ^g = m->Gruplar[i]; Konsol: : Yaz. Satır(L" Grup (0) = "(1)"", i, g-> Değer ); for (int j = 0; j Captures->Count; j++) ( Capture ^c = g->Captures[j]; Console: : Write.Line(L" Capture(0) = "(1)" , pozisyon = (2), uzunluk = (3)", j, c, c->İndeks, c->Uzunluk); ) ) m = m->Sonraki. Eşleşme(); ) dönüş 0; ) Sistem: : Metin : :Düzenli. ifade
Eylemlerin dahil edilmesi ve hata arama Bir sayıdaki anlamlı basamak sayısını sınırlama: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + e = s? = (+|-)? pd* + e = (pd*)? =(.d*)? @"(+|-)? (.d+|d+(.d*)?)" veya @"^(+|-)? (.d+|d+(.d*)?)$" Normal İfade r = yeni Normal İfade (@"^(+|-)? (. (? "rakam"d)+|(? "rakam"d)+(. (? "rakam"d)*)?)$"); Maç m = r. Maç("+1.23456789"); if (m. Başarı) ( Grup g = m. Gruplar["rakam"]; if (g. Yakalamalar. Sayı)
Eylemleri Etkinleştirme ve Hataları Bulma Bir Hatanın Konumunu Belirleme: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? ") basamak"d )*)?)"); string str = "+1.2345!678"; Maç m = r. Maç(str); if (m. Success) ( Group g = m. Groups["digit"]; if (g. Captures. Count 0) Console.Write.Line("1. konumdaki hata: beklenmeyen karakter "(0)"", str ); else if (m.Uzunluk
Eylemlerin etkinleştirilmesi ve hataların aranması Hatanın konumunun belirlenmesi: 1. giriş dizisinin (1) ilk konumu, eğer ilk eşleşme Index = 0 konumundan başlamazsa; 2. giriş dizisinin son konumu ile eşleşmiyorsa, son eşleşmeyi takip eden konum (eşleşme. Uzunluk + 1); 3. Eşleşmeler arasındaki ilk aranın konumu (eşleşme[i]. İndeks + eşleşme[i]. Uzunluk + 1), eğer önceki eşleşmeyi takip eden karakter bir sonraki eşleşmenin ilk karakteri değilse.
indeks) mola; dizin = m[i]. İndeks + m[i]. uzunluk; ) Konsol. yazmak. Line("(0) konumunda hata "(1)"", indeks + 1, str); ) "abc. xyz. pqr" doğrudur; + abc. xyz. pqr" - 1. konumdaki hata ("+"); "ABC. xyz. pqr!" – konum 12'de hata (“!”); "ABC. xyz!. pqr" - 8 konumundaki hata ("!").
Eylemlerin dahil edilmesi ve hata arama Ama! "ABC. xyz. +pqr" - 8 konumundaki hata (". "). Yeni model varyantı: @"w+(.w+)*(. (? !$))? " Doğrulama: "abc. xyz. +pqr" - 9. konumdaki hata ("+"); "ABC. xyz. pqr. "- 12 konumunda bir hata (". ").
Dengeli tanımlar: "(? "x")", "x" adlı koleksiyona bir öğe ekler; "(? "-x")", "x" koleksiyonundan bir öğeyi kaldırır; "(? (x)(? !))", "x" koleksiyonunda hiç öğe kalmadığını kontrol eder. Dil L, Pascal dilinin iç içe geçmiş ifadelerini anlatan “begin end; ': @"^s*((? "başlar+)+(? "-başlar"biter*; s*)+)*(? (başlar)(? !)$".
Bir dilin kelime dağarcığını düzenli ifadeler şeklinde tanımlamak ve bir dili KA yardımıyla tanımak daha uygundur. Bu nedenle, düzenli ifadeler biçimindeki dil tanımlarını FA biçimindeki bir tanıma dönüştürebilmek önemlidir. Böyle bir dönüşüm Kennet Thompson tarafından önerildi.
Durum makinesi beştir (S, S, d, S 0 , F)
S sonlu bir durumlar kümesidir.
S, sonlu bir geçerli giriş sinyalleri kümesidir.
d - geçiş işlevi. Sx(SÈ(e)) kümesini, deterministik olmayan sonlu bir otomatın durum kümesine yansıtır. Deterministik bir otomat için geçiş fonksiyonu, SxS kümesini otomatın durum kümesine yansıtır. Başka bir deyişle, duruma ve giriş sembolüne bağlı olarak d, otomatın yeni durumunu belirler.
S 0 - sonlu otomatın başlangıç durumu, S 0 О S.
F, otomatın son durumlarının kümesidir, F О S.
Bir durum makinesinin çalışması bir dizi adımdan oluşur. Adım, otomatın durumu ve giriş sembolü tarafından belirlenir. Adımın kendisi, otomatın durumunu değiştirmekten ve giriş dizisinin bir sonraki sembolünü okumaktan oluşur.
Düzenli ifadeleri durum makinesine dönüştürmek için aşağıdaki kurallar vardır.
1 Düzenli ifade “e”, iki durumun otomatına ve aralarında bir e-geçişe dönüştürülür (Şekil 1).
Şekil 1. - E-geçiş için otomat
2 Bir karakter “a”dan gelen bir düzenli ifade, a giriş sinyaline göre iki durum ve bunlar arasında bir geçişten sonlu durum makinesine dönüştürülür (Şekil 2).
Şekil 2. - a sembolüne göre atlamak için otomat
3 Düzenli bir rs ifadesi olsun ve r ifadesi için sonlu otomatlar olsun ve s ifadesi zaten oluşturulmuş durumda. Daha sonra iki otomata seri olarak bağlanır. Şekil 3, r ve s dilleri için ilk otomatları göstermektedir. Şekil, bu dillerin birleştirilmesinin tanınması için bir otomat göstermektedir.
r için otomatik s için otomatik
Şekil 3. - İlk otomata
Şekil 4. - Dilleri birleştirme makinesi
4 Bir düzenli ifade olsun r | r ifadesi ve s ifadesi için s ve sonlu otomatlar zaten oluşturulmuştur (Şekil 3). O zaman ortaya çıkan otomatta, iki otomattan birini çalıştırmanın bir alternatifi olmalıdır. Yani, r | ifadesinin otomatıdır. Şekil 3'teki r ve s için otomatlar için s, Şekil 5'te gösterilen forma sahiptir.
Şekil 5. - Dilleri birleştirmek için makine
5 İnşa edilmiş sonlu otomat r ile düzenli bir r* ifadesi olsun. Bu durumda, r ifadesinin otomatını atlama olasılığı için iki yeni durum tanıtılır ve r otomatının çoklu tekrarı olasılığı için son ve başlangıç durumları arasında bir e-geçiş eklenir. r düzenli ifadesi için Şekil 3'e benzer bir otomat oluşturulursa, Şekil 6'da gösterilen sonlu otomat r* düzenli ifadesine karşılık gelir.
Ayarlar
Kleene'nin teoremine göre, herhangi bir düzenli ifade, bu düzenli ifade tarafından belirtilen sözlükleri tanımak için algoritmanın resmi bir modeli olan sonlu bir otomat ile ilişkilendirilebilir. En genel terimlerle, sonlu bir otomat tanıyıcı, kendisine özgü sonlu bir dizi giriş akış durumu ve bunlar arasındaki geçişlerle tanımlanır. Giriş karakterinden ve geçerli durumdan sonraki olası durumları belirleyen geçiş işlevine uygun olarak belirli bir alfabeden giriş akışının karakterleri alındığında bir durum değişikliği meydana gelir. Muhtemel durumlar arasında, durum makinesi tanıyıcısının sırasıyla giriş akışı belirteçlerinin işlenmesinin başında ve sonunda olabileceği başlangıç (başlangıç) ve son (izin veren) durumlar seçilir. Girdi karakter dizisi, sonlu otomatı başlangıç durumundan son durumlardan birine aktarabilen bir geçiş dizisi oluşturabiliyorsa, kabul ettiği ve tanıdığı normal kümeye ait olduğu kabul edilir.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
tablo 1
| 0 | 1 | |
| Q1 | 4. Çeyrek | Q2 |
| Q2 | Q3 | Q1 |
| Q3 | Q2 | 4. Çeyrek |
| 4. Çeyrek | Q1 | Q3 |
Geçiş tablosunun sütunları, giriş alfabesinin karakterlerini temsil eder ve satırlar, DFA'nın mevcut durumlarına karşılık gelir. Her satırın öğeleri, giriş alfabesinin karşılık gelen karakterlerini alırken mevcut durumdan geçmesi gereken DFA durumlarını gösterir. Özellikle, bu geçiş tablosunun ilk satırından, Q1 başlangıç durumunda 0 ve 1 sembollerinin alınmasının, DFA'yı sırasıyla Q4 ve Q2 durumlarına aktardığı sonucu çıkar.
Giriş sırasını geçiş tablosundan tanırken, kabul eden durumlardan birine ulaşılıp ulaşılmadığını belirlemek için DFA'nın durum değişikliklerini izlemek kolaydır. Özellikle, çift sayıda sıfır ve bir içeren bir ikili vektör 01001000 için, dikkate alınan DFA, her geçişin onu çağıran giriş alfabesinin karakteriyle etiketlendiği aşağıdaki geçiş dizisini oluşturur:
Ç1 0 Ç4 1 Ç3 0 Ç2 0 Ç3 1 Ç4 1 Ç1 0 Ç4 0 Ç1
Bu geçiş dizisi, kabul durumu Q1 ile sona erer, bu nedenle ikili vektör 01001000, dikkate alınan DFA tarafından tanınan normal kümeye aittir ve yukarıdaki düzenli ifadeyi karşılar.
Sonuç olarak, gayri resmi inşa etme yönteminin kabul edildiğine dikkat edilmelidir.
Sonlu otomatların özelliklerinin daha fazla çalışılması ve özellikle sentez probleminin çözümü için aşağıdaki teorem önemlidir.
Teorem 7.7 (belirleme teoremi). Herhangi bir sonlu otomat için, eşdeğer bir deterministik sonlu otomat inşa edilebilir.
Teoremi kanıtlamak için, ilk olarak, orijinalinden deterministik sonlu bir otomat oluşturmak için algoritmayı tanımlamak gerekir; ikincisi, gerçekten de deterministik ve orijinaline eşdeğer sonlu bir otomat verdiğini kesin olarak kanıtlayarak bu algoritmayı doğrulayın. Burada yalnızca deterministik bir otomat oluşturmak için algoritmayı sunuyoruz.
Keyfi bir sonlu otomatın eşdeğer bir deterministik olana dönüşümü iki aşamada gerçekleştirilir: önce \lambda etiketli yaylar kaldırılır, ardından gerçek belirleme gerçekleştirilir.
1. λ-geçişlerinin kaldırılması (\lambda etiketli yaylar).
Orijinal durum makinesinden hareket etmek için M=(V,Q,q_0,F,\delta) eşdeğer sonlu otomata M"=(V,Q",q_0,F",\delta")λ geçişleri olmadan, orijinal M grafiğinde aşağıdaki dönüşümleri gerçekleştirmek yeterlidir.
A. Yalnızca \lambda etiketli yaylarla girilen başlangıç durumu dışındaki tüm durumlar kaldırılır; bu, sonlu M" otomatının Q" kümesini tanımlar. Açıktır ki Q"\subseteq Q . Bu durumda, başlangıç durumunun aynı kaldığını varsayıyoruz.
B. Sonlu M" otomatının yay kümesi ve etiketleri (dolayısıyla M" geçiş fonksiyonu) aşağıdaki gibi tanımlanır: herhangi iki durum için p,r\in Q",~ p\to_(a)r ancak ve ancak a\in V ise ve M grafiğinde aşağıdakilerden biri geçerliyse geçerlidir: ya p'den r'ye etiketi a sembolünü içeren bir yay vardır ya da şöyle bir q durumu vardır: p\Rightarrow_(\lambda)^(+)q ve q\to_(a)r . Bu durumda, genel olarak konuşursak, tepe noktası q, Q "kümesine ait olmayabilir, yani, M" otomatına geçerken kaybolabilir (Şekil 7.11). Ama eğer q\in Q" ise, o zaman doğal olarak yay (q,r) M" içinde korunacaktır ve a sembolü bu yayın etiketine ait sembollerden biri olacaktır (Şekil 7.12).
Böylece, M" içinde, etiketleri \lambda'dan farklı olan ve Q" kümesinden bir çift durum (köşe) bağlayan tüm yaylar M saklanır (a maddesine göre çıkarılmaz). Ek olarak, herhangi bir p,q,r durum üçlüsü için (mutlaka farklı değildir!), öyle ki p,r\in Q" ve p'den q'ya sıfır olmayan uzunlukta bir yol vardır ve etiketi \lambda'ya eşittir (yani, λ-geçiş yolu) ve q'dan r'ye etiketi giriş alfabesinin a sembolünü içeren bir yay açar, M"'de p'den r'ye etiketi içeren bir yay oluşturulur. a sembolü (bkz. Şekil 7.11).
V. Sonlu M" otomatının F" son durumları kümesi, tüm q\in Q" durumlarını, yani a maddesine göre silinmeyen sonlu M otomatının durumlarını içerir; q\Rightarrow_(\lambda)^(\ast)q_f bazı q_f\in F için (yani, ya q durumunun kendisi sonlu M otomatının son durumudur ya da ondan sonlu otomatın son durumlarından birine \lambda etiketli yaylar boyunca sıfır olmayan uzunlukta bir yol vardır. otomat M ) (Şek. 7.13).
2. Aslında kararlılık.
İzin vermek M=(Q,V,q_0,F,\delta)λ geçişleri olmayan sonlu bir otomattır. Eşdeğer bir deterministik sonlu otomat M_1 inşa edelim.
Bu sonlu otomat, durum kümesi M sonlu otomatın durum kümesinin tüm alt kümelerinin kümesi olacak şekilde tanımlanır. Bu, sonlu otomat M_1'in her bir bireysel durumunun, sonlu otomat M'nin durum kümesinin bazı alt kümeleri olarak tanımlandığı anlamına gelir. Bu durumda, yeni sonlu otomatın başlangıç durumu (yani M_1 ), eski sonlu otomatın (yani M ) başlangıç durumunu içeren tekil bir alt kümedir ve yeni sonlu otomatın son durumları, aşağıdakileri içeren Q alt kümeleridir. orijinal sonlu otomat M'nin en az bir finali.
Bundan böyle, biraz konuşma özgürlüğüne izin vererek, sonlu otomat M_1'in durumlarını bazen durum kümeleri olarak adlandıracağız. Bununla birlikte, bu tür her durum kümesinin yeni sonlu otomatın ayrı bir durumu olduğunu, ancak onun durumlarının bir kümesi olmadığını açıkça anlamak önemlidir. Aynı zamanda, orijinal ("eski") sonlu otomat M için, bu tam olarak onun durumlarının kümesidir. Mecazi olarak konuşursak, eski sonlu otomatın durumlarının her bir alt kümesi, yeni sonlu otomatın* bir durumuna "çöker".
*Formel olarak, Q_1 kümesi, 2^Q kümesiyle birebir örtüşen bir küme olarak tanımlanmalıdır, ancak yine de Q_1'in 2^Q ile çakıştığını düşünmek bizim için daha uygundur, çünkü küme sonlu bir otomatın durumlarının sayısı, boş olmayan herhangi bir sonlu küme olabilir.
Yeni sonlu otomatın geçiş fonksiyonu, a giriş sembolü ile S durum kümesinden M_1 sonlu otomat, eski sonlu otomatın tüm durum kümelerinin birleşimi olan durum kümesine gidecek şekilde tanımlanır. bu eski sonlu otomatın her bir durum kümesinden a sembolünden geçtiği S . Bu nedenle, sonlu otomat M_1 yapı gereği deterministiktir.
Yukarıdaki sözlü açıklama şu şekilde formüllere çevrilebilir: M_1 durum makinesini oluşturuyoruz, böylece
M_1=(Q_1,V,\(q_0\),F_1,\delta_1), Nerede
\begin(cases)Q_1=2^Q,\quad F_1=\(T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end(durumlar)
Yeni sonlu otomatın durumları arasında \varnothing bir durum olduğuna dikkat edelim ve (7.8)'e göre, \delta_1(\varnothing,a)=\varnothing herhangi bir giriş karakteri için a . Bu, böyle bir durumda bir kez M_1 durum makinesinin onu terk etmeyeceği anlamına gelir. Genel olarak, herhangi bir a girdi sembolü için \delta(q,a)=q olacak şekilde sonlu bir otomatın herhangi bir q durumu, sonlu otomatın soğurucu durumu olarak adlandırılır. Böylece, deterministik durum makinesi M_1'in durumu soğurucudur. Şunu da belirtmekte fayda var \delta_1(S,a)=\varhiçbir şey ancak ve ancak eğer her q\in S için (S durumları kümesinden eski sonlu otomatın durumları) \delta(q,a)=\varhiçbirşey, yani M grafiğinde, bu tür her q durumu, a sembolü ile işaretlenmiş herhangi bir yay bırakmaz.
Böyle bir algoritma ile elde edilen sonlu otomatın orijinaline eşdeğer olduğu kanıtlanabilir.
Örnek 7.9.Şekil 1'de gösterilen sonlu otomatı belirliyoruz. 7.14.
λ geçişleri olmayan eşdeğer bir sonlu otomat, şekil 2'de gösterilmektedir. 7.15. Yalnızca "boş" yaylar girdiği için q_2 tepe noktasının kaybolduğuna dikkat edin.
Ortaya çıkan otomatı belirlemek için, çoğuna \(q_0\) başlangıç durumundan ulaşılamayabilecek olan 2^3=8 durumlarının tümünü yazmak kesinlikle gerekli değildir. \(q_0\) durumlarından ve yalnızca onlardan erişilebilir elde etmek için sözde çekme yöntemini kullanırız.
Bu yöntem genel durumda aşağıdaki gibi açıklanabilir.
Orijinal sonlu otomatta (boş yaylar olmadan), başlangıçtan itibaren erişilebilen tüm durum kümelerini tanımlarız, yani. her giriş karakteri a için \delta(q_0,a) kümesini buluruz. Yeni otomattaki bu tür kümelerin her biri, ilkinden doğrudan erişilebilen bir durumdur.
Tanımlanan durum kümelerinin her biri S ve her giriş sembolü a için, kümeyi buluruz \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). Bu adımda elde edilen tüm durumlar, 2 uzunluğundaki bir yol boyunca ilk tepe noktasından ulaşılabilen yeni (deterministik) bir otomatın durumları olacaktır. Açıklanan prosedürü, yeni durum kümeleri (boş olan dahil) görünmeyene kadar tekrarlıyoruz. Bu durumda, sonlu otomat M_1'in bu tür tüm durumlarının başlangıç durumundan erişilebilen \(q_0\) elde edildiği gösterilebilir.
Şekil 1'deki sonlu durum makinesi için. 7.15 elimizde:
\begin(hizalı)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\cup \delta(q_3,b)= \(q_1\)\cup\(q_1\)=\(q_1\). \end(hizalı)
Artık yeni durum kümeleri olmadığından, "çekme" prosedürü burada sona erer ve Şekil 1'de gösterilen grafiği elde ederiz. 7.16.
Normal Dil Tamamlayıcısı
Belirleme teoreminin önemli teorik sonuçlarından biri aşağıdaki teoremdir.
Teorem 7.8. Düzenli bir dilin tamamlayıcısı düzenli bir dildir.
L, V alfabesinde düzenli bir dil olsun. O zaman L dilinin tamamlayıcısı (bir dizi sözcük olarak) dildir. \overline(L)=V^(\ast)\setminus L.
Teorem 7.7'ye göre, normal bir L dili için, L'yi kabul eden deterministik sonlu bir otomat M inşa edilebilir. Her tepe noktasından deterministik bir otomatta olduğundan, her giriş sembolü için tam olarak bir tepe noktasına geçiş tanımlandığından, o zaman, alfabedeki x dizisi ne olursa olsun V , bunun için M'de başlangıçtan başlayarak benzersiz bir yol vardır. x dizisinin okunduğu durum. M otomatının x dizisine izin verdiği açıktır, yani x\in L(M) , ancak ve ancak belirtilen yolun son durumu nihai ise. Bu, x\notin L(M) zincirinin ancak ve ancak belirtilen yolun son durumunun nihai olmadığı anlamına gelir. Ancak, x zincirine ancak ve ancak orijinal sonlu otomat M izin vermiyorsa izin veren sonlu bir M" otomatına ihtiyacımız var. L dilinin tamamlanmasına izin veren deterministik otomat.
Kanıtlanmış teorem, aşağıdaki yöntemle belirli bir dizi zincire izin vermeyen sonlu bir otomat oluşturmamıza izin verir: önce, belirli bir dizi zincire izin veren bir otomat oluştururuz, sonra onu belirler ve tümleyen için otomata geçeriz. Teorem 7.8'in ispatında belirtildiği gibi.
Örnek 7.10. A. 101 dizisi hariç \(0;1\) alfabesindeki tüm dizilere izin veren sonlu bir otomat oluşturalım.
İlk olarak, tek bir zincir 101'e izin veren sonlu bir otomat inşa ediyoruz. Bu otomat, şekil 2'de gösterilmektedir. 7.17.
Bu otomat yarı deterministiktir, ancak tam olarak tanımlanmadığından deterministik değildir. Bunu belirleyelim ve Şekil 1'de gösterilen deterministik eşdeğer sonlu bir otomat elde edelim. 7.18.
Ve son olarak, eklemeye geçerek (ve durumları yeniden adlandırarak), Şekil 1'de gösterilen otomatı elde ederiz. 7.19.
Ortaya çıkan otomatta, s_3 tepe noktası dışındaki tüm köşelerin son olduğunu unutmayın.
Teorem 7.8'in ispatında tartışılan tümleyene geçişin yalnızca deterministik bir otomatta gerçekleştirilebileceğine de dikkat edin. Şekil 1'de gösterilen otomatta son ve son olmayan köşelerin rollerini tersine çevirirsek, 7.17'de \(\lambda,1,10\) dilini kabul eden bir otomat alırdık ki bu - kolayca görülebileceği gibi - 101 dizisi dışındaki tüm dizilerin kümesi değildir.
Ayrıca, Şekil 1'deki sonlu durum makinesine dikkat edin. 7.19, 101 dizisini içeren ancak dizinin kendisiyle eşleşmeyen tüm dizilere izin verir. Örneğin, 1011 zincirini taşıyan yol şu şekildedir: s_0,s_1,s_2,s_3,t.
B. 101 dizisini içerenler dışında \(0;1\) alfabesindeki tüm dizilere izin veren sonlu bir otomat inşa edelim. Her dizesi 101 dizisinin bir oluşumunu içeren bir L dilini ele alalım. aşağıdaki gibi tanımlanır:
L=(0+1)^(\ast)101(0+1)^(\ast).
L dilini tamamlamak için bir otomat oluşturmamız gerekiyor.
Bu durumda doğrudan düzenli ifadeden, L diline izin veren sonlu bir otomat oluşturmak kolaydır (Şekil 7.20).
Daha sonra "çekme" yöntemi ile belirleme işlemini gerçekleştireceğiz. Belirlemenin sonucu, Şek. 7.21.
Sorunun tam çözümü için, yalnızca Şekil. 7.21 son ve son olmayan köşelerin rollerini değiştirin (Şekil 7.22).
V. Sadece ve sadece \(0;1\) alfabesindeki 01 dizisiyle başlamayan ve 11 dizisiyle bitmeyen dizilere izin veren sonlu bir otomat oluşturma fikrini tartışalım (yani, x,y\in\(0;1\) ) zincirleri ne olursa olsun, 01x biçimine ve y11 biçimindeki dizelere izin verilmez.
Bu durumda, kendisi için sonlu bir otomat oluşturmak istediğiniz dilin tümleyeni, 01 dizisiyle başlayan veya 11 dizisiyle biten bu tür tüm sıfır ve birler dizilerinin kümesidir. Bu dizi dizisini kabul eden bir otomat birleştirmek için bir otomat olarak inşa edilmiştir. 01(0+1)^(\ast)+(0+1)^(\ast)11 Kleene teoreminin ispatında olduğu gibi (bkz. Teorem 7.6).
Düzenli diller sınıfının tümleyen altında kapalı olma özelliği (bkz. Teorem 7.8), bu sınıfın kesişim, küme-teorik ve simetrik farklılıklar altında kapalı olduğunu hemen ima eder.
Sonuç 7.3. Herhangi iki normal dil L_1 ve L_2 için aşağıdaki ifadeler doğrudur:
1) L_1\cap L_2 kesişimi düzenlidir;
2) L_1\setminus L_2 farkı düzenlidir;
3) simetrik fark L_1\varüçgen L_2 düzenli.
İfadelerin geçerliliği kimliklerden kaynaklanmaktadır:
\begin(hizalı) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\triangle\ ,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end(hizalı)
İlk olarak, elde edilen sonuçlar, birleştirme, kesişme ve toplama işlemlerine ilişkin normal diller sınıfının, birimin evrensel dil olduğu ve sıfırın boş dil olduğu bir Boole cebri olduğunu iddia etmemizi sağlar. . İkincisi, düzenli diller ailesinin bu cebirsel özellikleri, iki keyfi sonlu otomatın denkliğini tanıma gibi önemli bir sorunu çözmemize izin verir.
Tanım 7.10'a göre, izin verdikleri diller aynıysa, sonlu otomatlar eşdeğerdir. Bu nedenle, M_1 ve M_2 otomatlarının eşdeğerliğini doğrulamak için, L(M_1) ve L(M_2) dillerinin simetrik farkının boş olduğunu kanıtlamak yeterlidir. Bunu yapmak için ise, bu farkı kabul eden bir otomat oluşturmak ve kabul ettiği dilin boş olduğunu doğrulamak yeterlidir. Genel olarak, bir durum makinesi dilinin boş olduğunu fark etme sorunu, durum makinesi boşluk sorunu olarak adlandırılır. Bu problemi çözmek için otomatın başlangıç durumundan ulaşılabilen son durum kümesini bulmak yeterlidir. Sonlu durum makinesi yönlendirilmiş bir grafik olduğundan, bu problem örneğin genişlik öncelikli arama kullanılarak çözülebilir. Sonlu otomatın izin verdiği dil, ancak ve ancak başlangıç durumundan ulaşılabilen nihai durumlar kümesi boşsa boştur. Uygulamada, bir minimizasyon algoritması kullanarak sonlu otomatların denkliğini tanımak tercih edilir, ancak şimdi, denklik problemini çözmenin temel olasılığının Teorem 7.7'den ve onun cebirsel sonuçlarından kaynaklandığını vurgulamak bizim için önemlidir.
