Otomata teorisinin düzenli dil tanımı. Normal dilleri belirtme yöntemleri. Alfabe, kelime, dil
3 numaralı laboratuvar çalışması
Düzenli diller ve sonlu otomatlar teorisi kullanılıyorsa, sözcüksel bir analizörün geliştirilmesi oldukça basittir. Bu teori çerçevesinde, aynı türdeki sözcük birimlerinin sınıfları, cümleleri karşılık gelen üretken dilbilgisi kullanılarak açıklanan resmi diller (tanımlayıcıların dili, sabitlerin dili vb.) Olarak kabul edilir. Üstelik bu diller o kadar basittir ki, gramerlerin en basiti olan normal gramer tarafından üretilirler.
Tanım 1. üretken dilbilgisi G =
Bir otomat dilbilgisi tarafından oluşturulan L (G) diline, otomat (normal) dil veya sonlu sayıda duruma sahip bir dil denir.
örnek 1. Tanımlayıcının harflerden ve rakamlardan oluşan bir dizi olması ve tanımlayıcının ilk karakterinin yalnızca bir harf olabilmesi durumunda, bir tanımlayıcı sınıfı, aşağıdaki üretken düzenli dilbilgisi ile tanımlanır: G =
N= (I, K), T = (b, c), S=(I),
P = ( 1. I::= b
Burada b, c sırasıyla harfleri ve sayıları belirtmek için genelleştirilmiş terminal sembolleridir.
"bbcbc" tanımlayıcısını oluşturma işlemi aşağıdaki ikame dizisiyle açıklanmaktadır.
ben => bbc => bbc => bbcK => bbcbK => bbcbc
Ancak LA'nın asıl görevi sözcük birimlerinin oluşturulması değil, bunların tanınmasıdır. Normal bir dili tanıma sürecinin matematiksel modeli, sonlu durum makinesi (FA) adı verilen bir bilgi işlem cihazıdır. "Sonlu" terimi, bilgi işlem cihazının sabit ve sonlu miktarda belleğe sahip olduğunu ve bazı sonlu kümelere ait bir dizi giriş sembolünü işlediğini vurgular. KA'nın çeşitli türleri vardır; eğer KA çıkış fonksiyonu (işin sonucu) yalnızca sembollerin giriş sırasının kabul edilebilir olup olmadığının bir göstergesiyse, böyle bir KA'ya denir. son çözümleyici
Tanım 2. Aşağıdaki beşine sonlu otomat adı verilir:
bir =
Q = (q 0, q 1, …, q n -1) – durumların alfabesi (sonlu sembol kümesi);
δ: Q ×V →Q – geçiş fonksiyonu;
q 0 Є Q – sonlu otomatın başlangıç durumu;
F Є Q – son durumlar kümesi.
Uzay aracının çalışma şeması.
Her biri V'den bir sembol içerebilen hücrelere bölünmüş sonsuz bir bant vardır. Bandın üzerine α Є V* zinciri yazılır. Zincirin solundaki ve sağındaki hücreler boştur. Banttaki karakterleri sırayla okuyabilen, bant boyunca soldan sağa hareket edebilen, okuma kafasına sahip son bir kontrol cihazı (FCU) bulunmaktadır. Bu durumda kontrol ünitesi Q'dan herhangi bir durumda olabilir. Kontrol ünitesi her zaman q 0 başlangıç durumunda çalışmaya başlar ve F son durumlarından birinde biter. bant, kontrol ünitesi δ fonksiyonuna uygun olarak yeni bir duruma geçer.
Uzay aracı geçiş fonksiyonu aşağıdaki şekillerde temsil edilebilir:
· Bir takım takımlar;
· Durum diyagramı;
· Geçiş tablosu.
Durum makinesi komutu şu şekilde yazılır:
(q ben, a j) → q k, burada q ben, q k Є Q; a j Є V.
Bu komut, durum makinesinin q i durumunda olduğu, banttan a j sembolünü okuduğu ve q k durumuna gittiği anlamına gelir.
Grafiksel olarak komut, q i köşe noktasından q k köşe noktasına giden bir grafik yayı olarak temsil edilir ve giriş alfabesinin a j sembolüyle işaretlenir:
Tüm haritalamanın (δ) grafiksel temsiline sonlu durum makinesinin durum diyagramı denir.
Uzay aracı kendisini herhangi bir komutun sol tarafı olmayan bir (q i, a j) durumun içinde bulursa durur. Kontrol ünitesi, bantta kayıtlı olan α zincirinin tüm sembollerini sayarsa ve aynı zamanda q r Є F son durumuna giderse, o zaman α zincirine sonlu durum makinesi tarafından izin verildiğini söylerler.
Uzay aracı geçiş tablosu şu şekilde oluşturulmuştur: matris sütunları giriş alfabesindeki sembollere karşılık gelir, satırlar durum alfabesindeki sembollere karşılık gelir ve matris elemanları, belirli bir giriş sembolü kombinasyonu için uzay aracının gittiği durumlara karşılık gelir. ve devlet sembolü.
Düzenli bir dilbilgisi G = olsun
O zaman sonlu otomat A =
2) Q = N U (Z), Z N ve Z T, Z, uzay aracının son durumudur;
5) δ eşlemesi şu şekilde oluşturulur:
· G gramerindeki A i::= a j A k formundaki her ikame kuralı (A i, a j) → A k komutuyla ilişkilidir;
· A i::= a j formundaki her değiştirme kuralı (A i, a j) → Z komutuyla ilişkilidir;
Örnek 2.Örnek 1'deki dil bilgisi için bir CA oluşturun. A =
1) V = T = (b, c)
2) Q = N U (Z) = (I, R, Z)
3) q0 = (S) = (I)
5) δ: a) bir dizi komut biçiminde:
b) bir durum diyagramı şeklinde
Deterministik ve deterministik olmayan sonlu durum makineleri vardır. Uzay aracı denir kararsız KA (NKA), eğer durum diyagramında aynı işaretlere sahip birkaç yay bir tepe noktasından çıkıyorsa. Örneğin, örnek 2'deki KA bir NKA'dır.
Pratik amaçlar için, son tanıyıcının kendisinin giriş karakter dizisinin bitiş anını belirlemesi ve giriş dizisinin doğruluğu veya hatası hakkında bir mesaj vermesi gerekir. Bu amaçlar doğrultusunda, giriş zincirinin sağda uç işareti ├ ile sınırlı olduğu kabul edilir ve yorumlanan durumlar, uzay aracının durum diyagramına girilir:
Z – “giriş zincirine izin ver”;
O – “giriş zincirinde bir hata hatırlandı”;
E – “giriş zincirini reddet.”
Z ve E durumları sondur ve uzay aracı, doğru veya hatalı bir giriş zincirini işledikten sonra sırasıyla son işaretleyiciyi ├ okurken bunlara gider. O Durumu orta düzeydedir, uzay aracı, giriş zincirinde bir hata tespit edildiğinde uzay aracının herhangi bir geçerli durumundan bu duruma geçer ve son işaretleyici ├ gelene kadar orada kalır, ardından E durumuna geçer - “giriş zincirini reddeder. ”
L 1 ve L 2 alfabedeki diller olsun
Sonra, yani. dil birleştirme birinci dildeki tüm kelimelerin ikinci dildeki tüm kelimelerle birleşiminden oluşur. Özellikle, eğer , o zaman ve eğer , o zaman .
L dilinin “dereceleri” için gösterimi tanıtalım:
Böylece L i, L'den i ardışık kelimelere bölünebilen tüm kelimeleri içerir.
L dilinin yinelemesi (L) *, L'den birkaç ardışık kelimeye bölünebilen tüm kelimelerden oluşur:
Dereceler kullanılarak temsil edilebilir:
Dilde mevcut değilse, boş sözcüğü içermeyen, dilin "kesilmiş" bir yinelemesini düşünmek genellikle uygundur: 
. Bu yeni bir işlem değil, sadece ifadenin kullanışlı bir kısaltmasıdır.
Ayrıca, alfabeyi tek harfli sözcüklerden oluşan sonlu bir dil olarak düşünürsek, boş sözcükler de dahil olmak üzere alfabedeki tüm sözcükler kümesi için önceden tanıtılan gösterimin bu dilin yineleme tanımına karşılık geldiğini unutmayın.
Aşağıdaki tablo resmi bir tümevarımsal tanım sağlar düzenli ifadeler alfabe ve temsil ettikleri diller üzerinde.
| İfade r | Dil L r |
|---|---|
 |
|
| la =(a) | |
| r 1 ve r 2 olsun | L r1 ve L r2 -temsil edilebilir |
| düzenli ifadeler. | onların dilleri. |
| Daha sonra aşağıdaki ifadeler | |
| düzenlidir | ve dilleri temsil eder: |
| r=(r 1 +r 2) | |
| r=(r 1 çevre 2) |  |
| r=(r1) * | L r =L r1 * |
Kayıt yaparken düzenli ifadeler Birleştirme işaretini atlayacağız ve * işleminin birleştirme ve +'dan daha yüksek önceliğe sahip olduğunu ve birleştirmenin +'dan daha yüksek önceliğe sahip olduğunu varsayacağız. Bu, birçok parantezlerin atlanmasına izin verecektir. Örneğin, 
10(1*+0) şeklinde yazılabilir.
Tanım 5.1. İki düzenli ifadeler Temsil ettikleri diller aynıysa r ve p'nin eşdeğer olduğu söylenir; Lr = Lp . Bu durumda r = p yazıyoruz.
Örneğin aşağıdakileri kontrol etmek kolaydır düzenli özellikleri operasyonlar:
- r + p= p+ r (birleşimin değişme özelliği),
- (r+p) +q = r + (p+q) (birliğin ilişkilendirilebilirliği),
- (r p) q = r (p q) (birleştirmenin ilişkilendirilebilirliği),
- (r *) * = r * (yineleme yetersizliği),
- (r +p) q = rq + pq(DAĞILMA).
Örnek 5.1. Örnek olarak çok açık olmayan bir eşitliği kanıtlayalım: (r + p) * = (r * p *) *.
L 1 sol tarafıyla, L 2 sağ tarafıyla temsil edilen dil olsun. Boş kelime her iki dile de aittir. Kelime boş değilse, yinelemenin tanımı gereği dile ait alt kelimelerin birleşimi olarak temsil edilebilir. Ancak bu dil, L"=L r * L p * (neden?) dilinin bir alt kümesidir. Bu nedenle 
. Tersine, eğer bir kelime ise, o zaman L " diline ait alt kelimelerin bir birleşimi olarak temsil edilebilir. Bu tür alt kelimelerin her biri v biçiminde temsil edilebilir v= v 1 1 ... v k 1 v 1 2 ... v l 2, burada tüm i=1, ... , k bir alt kelimedir ve tüm j=1, ... , l için bir alt kelimedir (k veya l'nin 0'a eşit olması mümkündür). Ancak bu, w'nin her biri ve'ye ait olan alt kelimelerin birleşimi olduğu anlamına gelir.
Normal dil
Dil teorisinde düzenli set(veya, normal dilde) aşağıdaki özellikleri karşılayan resmi bir dil olarak adlandırılır. Bu basit özellikler, düzenli kümeler sınıfının bir bütün olarak incelenmesine uygun olacak şekildedir ve elde edilen sonuçlar, biçimsel dillerin birçok önemli durumuna uygulanabilir. Yani düzenli küme kavramı matematiksel yapıya bir örnektir.
Düzenli bir kümenin tanımı
Σ sonlu bir alfabe olsun. Normal setΣ alfabesindeki R(Σ), aşağıdaki özyinelemeli özelliklerle tanımlanır:
| №. | Mülk | Tanım |
| 1 | Boş küme Σ alfabesinde düzenli bir kümedir | |
| 2 | Yalnızca bir boş dizeden oluşan bir küme, Σ alfabesinde düzenli bir kümedir | |
| 3 | Σ alfabesinin herhangi bir sembolünden oluşan bir küme, Σ alfabesinde düzenli bir kümedir | |
| 4 | Herhangi iki küme Σ alfabesinde düzenli ise, bu durumda bunların birleşimi de Σ alfabesinde düzenli bir kümedir | |
| 5 | Herhangi iki küme Σ alfabesinde düzenli ise, o zaman bunların eleman çiftlerinin tüm olası kombinasyonlarından oluşan küme de Σ alfabesinde düzenli bir kümedir | |
| 6 | Herhangi bir küme Σ alfabesinde düzenli ise, o zaman bu kümenin elemanlarının olası tüm kombinasyonlarından oluşan küme aynı zamanda Σ alfabesinde de düzenli bir kümedir | |
| Aşağıdakilerden başka hiçbir şey alfabede düzenli bir küme değildir Σ |
Ayrıca bakınız
- Otomata yaklaşımına dayalı bir ayrıştırıcı oluşturma
Wikimedia Vakfı. 2010.
Diğer sözlüklerde “Normal dil” in ne olduğuna bakın:
normal dil- - Telekomünikasyon konuları, normal dildeki temel kavramlar... Teknik Çevirmen Kılavuzu
- (Latince düzenliius, regula kuralından). Doğru, doğru düzenlenmiş, yapılmış. Makinenin düzenli çalışması. Hatta vuruş. Düzenli yaşam. Doğru, düzgün, monoton bir hayat. Rus dilinde yer alan yabancı kelimeler sözlüğü.... ... Rus dilinin yabancı kelimeler sözlüğü
Santimetre … Eşanlamlılar sözlüğü
Antik yazı dili- Uzun yazılı geleneklere sahip bir dil, yani birkaç yüzyıl önce belirli bir dilin yapısına uyarlanmış bir yazı dili almış ve dilin yazılı versiyonunun işleyişi epizodik değil, düzenliydi... . .. Toplumdilbilimsel terimler sözlüğü
Bu terimin başka anlamları da vardır, bkz. Quechua. Quechua'nın Kendi Adı: Qhichwa Simi, Runa Simi Ülkeleri ... Wikipedia
Aynı boyuttaki bir basamağa dayanan sütun veya direk ızgaralı bir binanın çerçevesi (Bulgarca; Български) tekdüze iskelet (Çekçe; Čeština) pravidelný skelet (Almanca; Almanca) regelmäßiges Skelett (Macarca; Magyar) szabályos... ... İnşaat sözlüğü
- [FRANSIZ PARKI] geometrik olarak düzenli bir düzene sahip bir park, genellikle eksenel bir düzen (Bulgarca; Български) frenski parkı (Çekçe; Čeština) francouzský park (Almanca; Almanca) regelmäßiger Park; Französischer Parkı… … İnşaat sözlüğü
Quechua Kendi Adı: Qhichwa Simi, Runa Simi Ülkeler: Arjantin, Bolivya, Kolombiya, Peru, Şili, Ekvador Bölgeler: And Dağları Resmi durumu: Peru ... Wikipedia
Tagalog dili- (tagal, tagala, tagalo; tagalog) Filipin dillerinden biri. İlk dağıtım alanı, Filipinler Cumhuriyeti'nin politik, ekonomik ve kültürel açıdan en önemli bölgesi olan adanın orta ve güney kısımlarıdır... ... Dilbilimsel ansiklopedik sözlük
Kitabın
- Türetilmiş fiiller. Fince dilbilgisinin sırları. Ders kitabı, Safronov V.D.. Kılavuz, Rus dili eğitim literatüründe Fince dilbilgisinin en ilginç ve yeterince sunulmamış bölümlerinden biri olan türetilmiş fiillere ayrılmıştır. Fiillerden ve isimlerden oluşurlar...
