Düzenli bir dil tanımı, otomat teorisidir. Düzenli diller ve sonlu durum makineleri

Düzenli gramerler, sonlu otomatlar ve düzenli kümeler (ve bunların düzenli ifadelerini ifade eden), normal dilleri tanımlamanın üç farklı yoludur.

Beyan

Bir dil, ancak ve ancak sol-doğrusal (sağ-doğrusal) bir dilbilgisi tarafından verilmişse PM'dir. Bir dil, ancak ve ancak düzenli bir küme ise, sol-doğrusal (sağ-doğrusal) bir dilbilgisi ile belirtilebilir.

Bir dil, ancak ve ancak bir sonlu durum makinesi kullanılarak belirtilmişse PM'dir. Bir dil, ancak ve ancak bir PM ise durum makinesi tarafından tanınır.

Bu yöntemlerin üçü de eşdeğerdir. Belirtilen yollardan birinde belirtilen bir dilin, aynı dili tanımlayan başka bir yol oluşturmasına izin veren algoritmalar vardır. Detaylı Açıklama bu algoritmalar literatürde bulunmaktadır (listeye bakınız).

Örneğin, doğru-doğrusal bir dilbilgisi tarafından verilen bir dil için düzenli bir ifade bulmak için, düzenli katsayılı bir denklem sistemi oluşturmak ve çözmek gerekir.

Programlama dilleri teorisinde en önemli rol, CA ve düzenli gramerlerin denkliği tarafından oynanır, çünkü bu tür gramerler programlama dillerinin sözcük yapılarını tanımlamak için kullanılır. Bilinen bir dilbilgisi temelinde bir otomat oluşturduktan sonra, verilen dil için bir tanıyıcı elde ederiz. Böylece dilin sözcüksel yapıları için ayrıştırma sorununu çözmek mümkündür.

Bilinen bir düzenli dilbilgisi temelinde bir CA oluşturmak için, bunun bir otomat formuna indirgenmesi gerekir. Otomatın durumları kümesi, dilbilgisinin terminal olmayan sembolleri kümesine karşılık gelecektir. 2.3.2 Normal dillerin özellikleri

Bu işlemin herhangi bir elemanı üzerinde yapılması sonucunda aynı kümeye ait yeni bir eleman elde edilen bir kümeye bazı işlemlere göre kapalı denir.

Düzenli kümeler, kesişim, birleşim, tümleyen, iterasyon, birleştirme, sembol isimlerini değiştirme ve sembol yerine karakter dizisi değiştirme işlemlerine göre kapalıdır.

Normal diller için, diğer dil türleri için çözülemeyen birçok problem çözülebilir. Örneğin, dilin hangi şekilde belirtildiğine bakılmaksızın aşağıdaki sorunlar çözülebilir:

Denklik problemi: İki normal dil L 1 (V) ve L 2 (V) verilmiştir. Eşdeğer olup olmadıklarını belirlemek gerekir.

Bir zincirin bir dile ait olma sorunu. Normal bir dil L (V) verildiğinde, bir V * sembolleri dizisi. Bu dizenin dile ait olup olmadığını kontrol etmek istiyorsunuz.

Dilin boşluğu sorunu. Normal bir dil L (V) verilir. Bu dilin boş olup olmadığını kontrol etmek gerekir, yani. en az bir zincir bulun, L (V).

Bazen belirli bir dilin düzenli olduğunu kanıtlamak gerekir. Bu dili, dikkate alınan yollardan biriyle ayarlamak mümkünse, normaldir. Ancak böyle bir yöntem bulunamazsa, dilin düzenli olup olmadığı veya onu tanımlamanın bir yolunu bulmanın mümkün olmadığı bilinmemektedir. Söz konusu dilin düzenli olup olmadığını kontrol etmenin basit bir yöntemi vardır. Bazı diller için sözde olduğu kanıtlanmıştır. büyüme lemması, o zaman düzenlidir. Bu lemma başarısız olursa, dil düzenli değildir.

Aşırı büyüme lemması aşağıdaki gibi formüle edilmiştir. Size düzenli bir dil ve bu dile ait yeterince uzun bir sembol dizisi verilirse, içinde istediğiniz kadar tekrarlanabilen boş olmayan bir alt dize ve bu şekilde elde edilen tüm dizeleri bulabilirsiniz. ayrıca incelenen normal dile ait olacaktır.

Resmi olarak, lemma aşağıdaki gibi yazılmıştır. L dili verilirse, o zaman p> 0 sabiti, öyle ki L ve p ise, zincir 0 şeklinde yazılabilir.

Örnek. L = (a n b n n> 0) dilini düşünün. Dillerin çoğalmasıyla ilgili lemmayı kullanarak bunun düzenli olmadığını kanıtlayalım.

Bu dilin düzenli olmasına izin verin, o zaman aşırı büyüme lemması bunun için geçerli olmalıdır. Bu dilin bir zincirini alalım = a n b n ve formda yazalım. a + veya b + ise, i dizgisi, lemma koşullarıyla çelişen herhangi bir i için dile ait değildir. a + b + ise, 2 dizesi de L diline ait değildir. Bir çelişki elde ettik, bu nedenle dil düzenli değildir.

Normal setlerve düzenli ifadeler

Normal setler

Bu bölümde, bir tür formüllerle tanımlanması çok kolay olan, sınırlı bir kelime dağarcığı üzerindeki zincir kümeleri sınıfını ele alacağız. Bu kümelere düzenli denir.

Tanım 1.İzin vermek 1 ve V2 - birçok zincir. Üç işlem tanımlayalımbu setlerde.

Birleşim: V 1 V 2 = ( |   V 1) veya   V 2.

Birleştirme (ürün, yapıştırma): Vl V2 = ( |   V 1,   V 2) Birleştirme işlemi işareti genellikle kullanılmaz.

Örnek: V, = (abc, ba), V2 = (b, cb). V1V2 = (abcb, abccb, bab, bacb).

V n ile n kümelerinin V ürününü gösteririz: V n = VV ... V, V ° = () (burada -boş zincir).

Örnek: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc).

3. Yineleme: V * = V 0 V 1 V 2  ... =   = 0 ∞ V n.

Örnek: V = (a, bc), V * = (, a, bc, aa, abc, bcbc, bca, aaa, aabc, ...).

Tanım 4.13.Sonlu bir kelime dağarcığı üzerinde düzenli kümeler sınıfı V kasideşöyle:

birlik ST;

birleştirme ST;

S * ve T * yinelemesi.

5. Bir küme, 1-4 kurallarının sınırlı sayıda uygulamasıyla oluşturulamıyorsa, o zaman düzensizdir.

Düzenli küme örnekleri: (ab, ba) * (aa); (b) ((c)  (d, ab) *). Düzensiz küme örnekleri: (a n b n | n> 0); ( |  zincirinde, a ve b sembollerinin oluşum sayısı aynıdır).

Düzenli ifadeler

Düzenli kümelerin iyi yanı, düzenli ifadeler diyeceğimiz formüllerle çok basit bir şekilde tanımlanabilmeleridir.

Tanım 2.Hedef sözlük üzerinde normal ifade sınıfı V kasideşöyle:

toplamları R1 + R2;

ürünleri R1R2;

yinelemeleri R1 * ve R2 *'dir.

4. Eğer ifade, 1-3 kuralının sınırlı sayıda uygulamasıyla oluşturulmadıysa, o zaman düzenli değildir.

İşin sembolü atlanabilir. Herhangi bir cebirde olduğu gibi parantez sayısını azaltmak için işlem öncelikleri kullanılır: yineleme en yüksek önceliğe sahiptir; daha az öncelikli iş; ekleme en düşük önceliğe sahiptir.

Normal ifade örnekleri: ab + ba *; (aa) * b + (c + dab) *.

Açıkçası, düzenli kümeler ve düzenli ifadeler oldukça yakındır. Ancak farklı varlıkları temsil ederler: düzenli bir küme, bir dizi zincirdir (genel durumda, sonsuzdur) ve normal ifadeyukarıdaki işlemler kullanılarak karşılık gelen düzenli kümenin nasıl oluşturulduğunu şematik olarak gösteren bir formül(ve bu formül sonludur).

R ^ normal bir R ifadesine karşılık gelen bir normal küme olsun. O halde:

Bu nedenle, düzenli bir ifade, sonsuz sayıda diziyi, yani bir dili tanımlayan sonlu bir formüldür.

Düzenli ifade örneklerine ve bunlara karşılık gelen dillere bakalım.

Düzenli ifade	karşılık gelen dil
	b ile başlayan ve ardından rastgele sayıda a karakteri gelen tüm dizeler
	a ve b'den gelen tüm dizeler, tam olarak iki b oluşumunu içerir
	b karakterlerinin yalnızca çiftler halinde göründüğü tüm a ve b dizeleri
(a + b) * (aa + bb) (a + b) *	En az bir bitişik a veya b çifti içeren a ve b'deki tüm zincirler
(0+1)*11001(0+1)*	11001 alt zincirini içeren tüm 0 ve 1 zincirleri
	a ile başlayan ve b ile biten tüm a ve b dizeleri

Açıkçası, bir dizi dizi, ancak ve ancak düzenli bir ifadeyle temsil edilebiliyorsa normaldir. Bununla birlikte, aynı diziler grubu farklı normal ifadelerle temsil edilebilir, örneğin, a karakterlerinden oluşan ve en az iki a içeren bir dizi dizi ifadelerle temsil edilebilir: aa * a; bir * aa *; aaa *; a * aa * aa * vb.

Tanım 3.İki normal ifade R1 ve R2 eşdeğer olarak adlandırılır (belirtilen Rı = R2) ancak ve ancakr1 ^ = r2 ^ .

Böylece, aa * a = a * aaa * = aaa * = a * aa * aa *. Soru, iki düzenli ifadenin denkliğinin nasıl belirleneceğidir.

teorem1 . Herhangi bir normal ifade için R, S ve T adil:

Bu ilişkiler, karşılık gelen dizi kümelerinin eşitliği kontrol edilerek kanıtlanabilir. Normal ifadeleri basitleştirmek için kullanılabilirler. Örneğin: b (b + aa * b) = b (b + aa * b) = b ( + aa *) b = ba * b. Dolayısıyla b (b + aa * b) = ba * b, bu açık değildir.

Kleene teoremi

Normal ifadeler, normal dilleri tanımlayan sonlu formüllerdir. Ancak sonlu otomatların da benzer bir özelliği vardır - ayrıca dilleri de tanımlarlar. Soru ortaya çıkıyor: durum makineleri tarafından tanımlanan dil sınıfları ve birbirleriyle ilişkili düzenli ifadeler nasıl? biz belirtiriz Ve birçok otomatik dil, R, bir dizi normal dildir. Amerikalı matematikçi Stephen Kleene, aşağıdaki teoremi kanıtladı.

teorem2 . (Kleene teoremi.) Düzenli kümeler ve otomat dillerinin sınıfları çakışır, yani, bir = r .

Başka bir deyişle, her otomat dili bir formül (düzenli ifade) ile belirlenebilir ve her düzenli küme sonlu bir otomat tarafından tanınabilir. Bu teoremi yapıcı olarak iki adımda kanıtlayacağız. İlk adımda, herhangi bir otomat dilinin düzenli bir küme olduğunu kanıtlıyoruz (veya aynı olan, herhangi bir sonlu otomat için, bu otomat tarafından tanınan dili tanımlayan bir düzenli ifade oluşturulabilir). İkinci adımda, herhangi bir düzenli kümenin bir otomat dili olduğunu (veya herhangi bir düzenli ifade için aynı olan, ilgili düzenli kümenin zincirlerini tam olarak kabul eden sonlu bir otomat inşa edebileceğini) kanıtlıyoruz.

Durum makinesi modelinin bir genellemesi olarak geçiş grafiği modelini tanıtalım. Geçiş grafiğinde, bir başlangıç ​​ve isteğe bağlı sayıda son köşe vardır ve yönlendirilmiş kenarlar, durum makinesinin aksine, sembollerle değil, normal ifadelerle etiketlenir. Geçiş grafiği bir if zincirini kabul eder a ilk tepe noktasından son tepe noktalarından birine giden yolu işaretleyen R 1 R 2 ... R n düzenli ifadelerinin çarpımı tarafından açıklanan dizgiler grubuna aittir. Bir geçiş grafiğinin izin verdiği zincirler kümesi, kabul ettiği dili oluşturur.

Pirinç. 1. Geçiş grafiği

İncirde. 1, örneğin abbca zincirine izin veren bir geçiş grafiğini gösterir, çünkü q son durumuna götüren s-> r-> p-> s-> r-> q yolu düzenli ifade zinciriyle işaretlenmiştir.  • a • b *   · c * a. Sonlu bir otomat, bir geçiş grafiğinin özel bir durumudur ve bu nedenle otomatların izin verdiği tüm dillere geçiş grafikleri tarafından da izin verilir.

Teorem 3.Her otomat dili düzenli bir kümedir, bir  R.

Kanıt. Başlangıç ​​noktasından son tepe noktasına kadar olan tek kenarın düzenli bir R ifadesi ile işaretlendiği bir başlangıç ​​ve bir son tepe noktasına sahip bir geçiş grafiği, R ^ dilini kabul eder (Şekil 1).

Pirinç. 2. Normal bir dil FT'sini kabul eden bir geçiş grafiği

Şimdi her otomat dilinin, kabul edilen dili eşdeğer bir forma değiştirmeden herhangi bir geçiş grafiğinin düzenli bir indirgenmesi olduğunu kanıtlayalım (Şekil 2).

Herhangi bir sonlu otomat ve herhangi bir geçiş grafiği her zaman, yalnızca giden kenarları olan yalnızca bir başlangıç ​​tepe noktasının ve yalnızca gelen kenarları olan yalnızca bir son tepe noktasının olduğu normalleştirilmiş bir biçimde temsil edilebilir (Şekil 3).

Pirinç. 3. Bir başlangıç ​​ve bir son tepe noktası olan bir geçiş grafiği

Normalleştirilmiş biçimde sunulan bir geçiş grafiğiyle, bu geçiş grafiğinin izin verdiği dili korurken, iki indirgeme işlemi gerçekleştirilebilir - bir kenar küçültme ve bir tepe noktası küçültme -:

a) kenarın azaltılması:

B ) tepe noktasının azaltılması (değiştirme, tepe noktasından geçen her yol için gerçekleştirilir ve ardından elde edilemez bir durum olarak atılır):

Açıkça, her indirgeme işlemi geçiş grafiği tarafından tanınan dili değiştirmez, ancak kenarların sayısını veya köşelerin sayısını azaltır ve sonunda indirgemeler geçiş grafiğini Şekil 2'de gösterilen forma getirecektir. 2. Teorem ispatlandı: her otomat dili düzenli bir kümedir.

Örnek

Bir sonlu durum makinesi A verilsin:

Normalleştirilmiş bir formda eşdeğer bir geçiş grafiği oluşturuyoruz.

Köşe 3'ün azaltılması:

Yayların azaltılması ve R = R kuralının uygulanması:

Köşe 2'nin azaltılması:

Yay ve tepe noktasının azaltılması 1:

Böylece, otomat A tarafından tanınan dil, düzenli bir ifadeyle belirtilir: R A = b + (a + bb) (b + ab) * a.

Kleene teoremini diğer yönde ispatlayalım.

Teorem 2.Her normal set bir otomat dilidir: R  A.

Kanıt. Her düzenli ifade için, R tarafından verilen dili tanıyan bir sonlu otomat Ar (muhtemelen deterministik olmayan) oluşturulabileceğini gösterelim. Bu tür otomatların tanımı yinelemeli olarak verilmiştir.

(A'nın ilk ve son durumları birleştirilir).

Örnek(devam)

3 numaralı laboratuvar çalışması

Düzenli diller ve sonlu durum makineleri teorisi kullanılıyorsa, sözcük çözümleyicisinin geliştirilmesi yeterince kolaydır. Bu teori çerçevesinde, aynı tür belirteçlerin sınıfları, karşılık gelen üretken dilbilgisi kullanılarak açıklanan cümleler kümesi olan resmi diller (tanımlayıcıların dili, sabitlerin dili vb.) olarak kabul edilir. Ayrıca, bu diller o kadar basittir ki, en basit gramerler tarafından üretilirler - normal bir gramer.

tanım 1... üretici dilbilgisi G = , kuralları şu şekildedir: A :: = aB veya C :: = b, burada A, B, C Є N; a, b Є Т, düzenli (otomatik) olarak adlandırılır.

Bir otomat dilbilgisi tarafından üretilen L (G) diline, bir otomat (normal) dili veya sonlu sayıda durumu olan bir dil denir.

örnek 1... Tanımlayıcı bir harf ve sayı dizisiyse ve tanımlayıcının ilk karakteri yalnızca bir harf olabilirse, tanımlayıcıların sınıfı, aşağıdaki üretken düzenli dilbilgisi ile tanımlanır G = , burada

N = (I, K), T = (b, q), S = (I),

P = (1.I :: = b

Burada b, c sırasıyla harfler ve sayılar için genelleştirilmiş terminal sembolleridir.

"bbts" tanımlayıcısını oluşturma süreci, aşağıdaki ikame dizisiyle açıklanmaktadır.

I => bK => bbK => bbtsK => bbtsbK => bbts

Bununla birlikte, LA'nın ana görevi, sözcük birimlerinin oluşturulması değil, tanınmasıdır. Normal dil tanıma sürecinin matematiksel modeli, sonlu otomat (CA) 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 girdi karakterini işlediğini vurgular. var Çeşitli tipler CA, CA'nın çıkış işlevi (çalışma sonucu) yalnızca karakter giriş sırasına izin verilip verilmediğinin bir göstergesiyse, böyle bir CA denir. son tanıyıcı

Tanım 2. Aşağıdaki beşe sonlu otomat denir:

bir = , burada V = (a 1, a 2,…, a m) giriş alfabesidir (sonlu bir sembol seti);

Q = (q 0, q 1,…, q n -1) - durumların alfabesi (sonlu bir sembol seti);

δ: Q × V → Q geçiş fonksiyonudur;

q 0 Є Q, sonlu otomatın başlangıç ​​durumudur;

F Є Q - son durumlar kümesi.

SC çalışma şeması.

Her biri V'den bir karakter içerebilen hücrelere bölünmüş sonsuz bir bant vardır. Bant bir α Є V * zinciri içerir. Zincirin solundaki ve sağındaki hücreler boştur. Bant boyunca soldan sağa hareket ederek sırayla şeritten karakterleri okuyabilen bir okuma kafasına sahip bir son kontrol cihazı (CU) vardır. Bu durumda, CU, Q'dan herhangi bir durumda olabilir. CU, çalışmasına her zaman q 0 başlangıç ​​durumunda başlar ve F son durumlarından birinde biter. Her seferinde, bant üzerinde yeni bir hücreye geçerek, CU, δ fonksiyonuna göre yeni bir duruma geçer.

Uzay aracının geçiş işlevi aşağıdaki şekillerde temsil edilebilir:

· Bir takım takımlar;

· Durum diyagramı;

· Geçiş tablosu.

Durum makinesi komutu aşağıdaki gibi yazılır:

(q i, a j) → q k, burada q i, q k Є Q; bir j Є V.

Bu komut, durum makinesinin q i durumunda olduğu, banttan a j sembolünü okuduğu ve q k durumuna geçtiği anlamına gelir.

Grafiksel olarak, komut, q i köşesinden q k köşesine giden ve giriş alfabesinin a j sembolü ile işaretlenen grafiğin bir yayı şeklinde temsil edilir:

Tüm eşlemenin δ grafiksel gösterimine durum makinesi durum diyagramı denir.

Uzay aracı kendisini herhangi bir komutun sol tarafı olmayan bir durumda (q i, a j) bulursa durur. UU, şeritte yazılı olan α dizisinin tüm sembollerini sayar ve aynı zamanda q r Є F son durumuna geçerse, α zincirinin sonlu bir otomat tarafından kabul edildiği söylenir.

CA'nın geçiş tablosu şu şekilde oluşturulmuştur: matrisin sütunları giriş alfabesindeki sembollere karşılık gelir, satırlar durum alfabesindeki sembollere karşılık gelir ve matrisin öğeleri CA'nın geçtiği durumlara karşılık gelir. giriş sembolü ve durum sembolünün belirli bir kombinasyonu için.

Normal bir dilbilgisi olsun G = , kuralları şu şekildedir: А ben :: = a j A k veya А ben :: = a j, burada А i, A k Є N ve a j Є T.

Sonra sonlu otomat A = Normal gramer G'nin ürettiği aynı dili kabul etmek şu şekilde oluşturulur:

2) Q = NU (Z), Z N ve Z T, Z - uzay aracının son durumu;

5) Eşleme δ şu şekilde oluşturulur:

· А i :: = a j A k biçimindeki G dilbilgisindeki her ikame kuralı, (А i, a j) → A k;

· А i :: = a j biçimindeki her bir ikame kuralı (А i, a j) → Z komutuyla ilişkilidir;

Örnek 2.Örnek 1'deki dilbilgisi için CA'yı oluşturun. Elimizde A = var. , nerede

1) V = T = (b, c)

2) Q = NU (Z) = (I, R, Z)

3) q 0 = (S) = (I)

5) δ: a) bir dizi komut olarak:

b) bir durum diyagramı şeklinde

Deterministik ve deterministik olmayan sonlu otomatları ayırt edin. uzay aracı denir kararsız CA (NCA), durumlarının şemasında bir tepe noktasından aynı işaretlere sahip birkaç yay çıkıyorsa. Örneğin, örnek 2'deki uzay aracı uzay aracıdır.

Pratik amaçlar için, son tanıyıcının, giriş dizisinin doğruluğu veya yanlışlığı hakkında bir mesaj verilmesiyle karakter giriş dizisinin bitiş anını belirlemesi gerekir. Bu amaçlar için, giriş zincirinin sağda uç işaretçisi ├ ile sınırlandığı kabul edilir ve yorumlanan durumlar SC durum diyagramına dahil edilir:

Z - "giriş zincirini kabul et";

О - "giriş zincirinde bir hata kaydedildi";

E - "giriş basamağını reddet."

Z ve E durumları nihaidir ve CA, doğru veya hatalı giriş zincirini işledikten sonra sırasıyla son işaretçiyi ├ okurken bunlara girer. O durumu orta düzeydedir, giriş zincirinde bir hata tespit edildiğinde CA, CA'nın kabul edilebilir herhangi bir durumundan geçer ve son işaretleyici gelene kadar içinde kalır, ardından E durumuna geçiş gerçekleştirilir - “reddet giriş zinciri”.

Bu bölümde, teorinin unsurlarını özetlemeye başlıyoruz. resmi diller.

"Formal dil" dediğimizde, burada sunulan sonuçların öncelikle insanlar tarafından özel amaçlar için icat edilen yapay dillerin, örneğin programlama dillerinin tanımlanmasında kullanıldığını kastediyoruz. Ancak özel olarak icat edilmiş yapay (biçimsel) diller ile kendiliğinden ortaya çıkan ve gelişen doğal diller arasında aşılmaz bir engel yoktur. Doğal dillerin karmaşık gramer kuralları, yani. oldukça katı bir şekilde resmileştirilmiştir ve en "bilimsel olarak geliştirilmiş" programlama dili bile, açık bir şekilde anlaşılması bir sorun olan "karanlık yerler" içerir.

Dil öğrenirken akılda tutulması gereken üç ana husus vardır.

Birincisi dil sözdizimi ... Bir dil, bir "kelime" kümesidir; burada bir "kelime", belirli bir "harf" dizisidir - önceden belirlenmiş bazı alfabenin sembolleri. "Harf" ve "kelime" terimleri farklı şekillerde anlaşılabilir (bu terimlerin matematiksel tanımı aşağıda verilecektir). Dolayısıyla, "harfler", örneğin Rus dili veya Pascal programlama dili gibi bazı doğal veya resmi dillerin alfabesinin harfleri olabilir. O zaman "kelimeler", "harflerin" sonlu dizileri olacaktır: timsah "," tam sayı". Bu tür kelimelere "sözlük" denir. "Fakat bir" harf "bir" kelime "(a" sözlük ") olabilir. dil, ancak yalnızca belirli kurallara uyan böyle bir dizi. "Krykadil" kelimesi Rus dilinin bir sözlük birimi değildir ve "iff" kelimesi "Pascal" da bir sözlük değildir. "Seni seviyorum" cümlesi, tıpkı "x: = = t" gösteriminin doğru yazılmış bir Pascal atama operatörü olmadığı gibi, Rus dilinin doğru bir cümlesi değildir. Dilin sözdizimi *, "harflerin" "doğru" dizilerini oluşturmanın mümkün olduğu bir kurallar sistemidir. Bir dilin her kelimesi, o dile özgü belirli bir yapı ile karakterize edilir. O zaman, bir yandan, belirli bir yapıya sahip sözcükleri sıralamak veya üretmek için mekanizmalar geliştirmek ve diğer yandan bunu kontrol etmek için mekanizmalar geliştirmek gerekir. verilen kelime verilen dile aittir. Her şeyden önce, klasik biçimsel diller kuramı tarafından incelenen tam da bu mekanizmalardır.

İkinci yönü ise dilin anlambilimi ... Semantik **, belirli bir “anlam”ın dilindeki kelimelerin karşılaştırılmasını gerektirir. Değerlendirme. "Örneğin, matematiksel bir formül yazarken, belirli sözdizimi kuralları(parantezlerin yerleştirilmesi, sembollerin yazılışı, sembollerin sırası vb.), ancak bunun yanında formülün çok kesin bir anlamı vardır, bir anlamı vardır.

Dil bir iletişim aracıdır, bilgi aktarımıdır. Anlaşılmak istiyorsak, sadece sözdizimsel olarak doğru bir şekilde, bir kelimedeki harflerin ve bir cümledeki kelimelerin doğru sırasını gözlemlemekle kalmamalı, konuşmamızı oluşturmalı, aynı zamanda konuşmada ifade ettiğimiz fikirlerin anlamına da dikkat etmeliyiz. matematiksel teoriler"anlam" nispeten yakın zamanda ortaya çıktı ve bir sonraki bölüme ek olarak, programlama dillerinin anlambiliminin matematiksel açıklamasına yönelik bazı yaklaşımları çok kısaca ele alacağız.

* "Sözdizimi" kelimesi eski Yunanca "syn" - "birlikte" ve "taksiler" - "düzen, düzen" kelimelerinden gelir. Böylece sözdizimi "oluşturma" olarak anlaşılabilir.

** Eski Yunanca "sema" - "işaret, işaret" ve "semantikos" - "belirleyen" kelimelerinden.

Son olarak, üçüncü yön - dilin pragmatiği ... Pragmatik, anadili bir konuşmacı tarafından belirlenen hedeflerle ilişkilidir: örneğin, bir kişi sözdizimi ile ilgili olmayan, konuştuğu veya yazdığı dilin anlambilimiyle değil, örneğin bir para miktarı belli. Pragmatik, bireyin hedef belirleme faaliyetini etkileyen daha çok sosyo-felsefi bir disiplindir. En azından ona dokunmayacağız.

Bu bölüm ilk olarak, en önemlisi üretici dilbilgisi kavramı olan biçimsel dillerin matematiksel teorisinin temel kavramlarını ve daha sonra sözde düzenli dilleri ele alacaktır. Düzenli diller teorisi, sonlu otomatlar teorisi ile birlikte, tüm biçimsel diller teorisinin temelini oluşturur.

• Alfabe, kelime, dil

• üretici dilbilgisi

  Daha önce belirtildiği gibi, klasik biçimsel diller teorisi, öncelikle bir dilin sözdizimini inceler. "İyi biçimlendirilmiş" dizeleri oluşturma ve tanıma mekanizmalarını tanımlayan matematiksel bir sözdizimi modeli sunar. Bu bölümde, bu mekanizmalardan ilkine bakacağız.

dilleri birleştirme işlemlerini biliyoruz. Birleştirme ve yineleme işlemlerini tanımlayalım (bazen Kleene kapanışı olarak adlandırılır).

Alfabedeki diller L 1 ve L 2 olsun

Sonra, yani dillerin sıralanması 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 ardışık i sözcüklerine bölünebilecek tüm sözcükleri içerir.

L dilinin bir yinelemesi (L) *, L'den birkaç ardışık kelimeye bölünebilen tüm kelimelerden oluşur:

Dereceler kullanılarak temsil edilebilir:

Boş bir kelime içermeyen bir dilin "kesilmiş" bir yinelemesini, eğer o dilde değilse, düşünmek genellikle uygundur: ... Bu yeni bir işlem değil, sadece bir ifade için uygun bir stenografidir.

Ayrıca, alfabeyi tek harfli kelimelerden oluşan sonlu bir dil olarak düşünürsek, alfabedeki boş kelime de dahil olmak üzere tüm kelimelerin kümesi için daha önce tanıtılan atamanın bu dilin yinelemesinin tanımına karşılık geldiğine dikkat edin.

Aşağıdaki tablo resmi bir endüktif tanım sağlar düzenli ifadeler alfabe ve temsil ettikleri diller üzerinden.

ifade r	Dil Sol
	L bir = (a)
r 1 ve r 2 olsun	L r1 ve L r2 temsil edilebilir
düzenli ifadeler.	onları diller.
Daha sonra aşağıdaki ifadeler
düzenli	ve dilleri temsil eder:
r = (r 1 + r 2)
r = (r 1 circr 2)
r = (r 1) *	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, parantezlerin çoğunu atlayacaktır. Örneğin, 10 (1*+0) olarak yazılabilir.

Tanım 5.1... 2 düzenli ifadeler r ve p, temsil ettikleri diller çakışırsa, yani eşdeğer olduğu söylenir. L r = L p. Bu durumda r = p yazarız.

Kontrol etmek kolaydır, örneğin, düzenli özellikleri operasyonlar:

• r + p = p + r (birleşimin değişebilirliği),
• (r + p) + q = r + (p + q) (çağrışım çağrışımı),
• (r p) q = r (p q) (birleştirme çağrışımı),
• (r *) * = r * (yinelemenin bağımsızlığı),
• (r + p) q = rq + pq(dağıtım).

Örnek 5.1... Örnek olarak çok açık olmayan bir eşitliği ispatlayalım: (r + p) * = (r * p *) *.

L 1, sol tarafıyla temsil edilen dil ve L 2 - sağ taraf olsun. Boş kelime her iki dile de aittir. Boş olmayan bir kelime ise, yinelemenin tanımı gereği, dile ait alt kelimelerin bir dizilimi olarak temsil edilebilir. Ancak bu dil, L "= L r * L p * (neden?) dilinin bir alt kümesidir. ... 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 şeklinde 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 birine ait olan ve dolayısıyla, alt sözcüklerin bir dizilimi olduğu anlamına gelir.