Genel durumda, dil sonsuz bir kümedir ve sonsuz nesnelerin tanımlanması bile zordur: yalnızca öğelerin listelenmesiyle tanımlanamazlar. Bir dili belirleyen herhangi bir sonlu mekanizmaya dilbilgisi adı verilir.
Biçimsel bir dil, bazı sonlu alfabelerdeki dizilerden oluşur. Biçimsel diller, insan-makine iletişimine yönelik yapay dilleri, yani programlama dillerini içerir.
Biçimsel bir dilin tanımını belirtmek için öncelikle alfabeyi, yani her biri sınırsız sayıda kopya halinde çoğaltılabilen (sıradan basılı harfler gibi) semboller (veya harfler) adı verilen bir dizi nesneyi belirtmek gerekir. veya sayılar) ve ikinci olarak dilin resmi dilbilgisini tanımlamak, yani tanımlanan dile ait dizileri (düzenli zincirler) oluşturmak için sembollerin kullanıldığı kuralları listelemek.
Biçimsel dilbilgisi kuralları ürünler (çıkarım kuralları), yani orijinal zincire (aksiyom) belirli bir sırayla uygulandığında yalnızca doğru zincirler üreten temel işlemler olarak düşünülebilir. Belirli bir zincirin oluşturulması sürecinde kullanılan kuralların dizisi, onun sonucudur. Bu şekilde tanımlanan dil biçimsel bir sistemdir.
Doğru zincirleri belirleme yöntemine göre biçimsel dilbilgileri üretken ve tanıyıcı dilbilgilerine ayrılır. Üretken gramerler L dilinin gramerlerini içerir,
yapısını gösteren herhangi bir “doğru” zincirin oluşturulması mümkünken, tek bir yanlış zincirin oluşturulması imkansızdır. L dilinin tanıma dilbilgisi, keyfi olarak seçilen bir dizenin doğru olup olmadığının belirlenmesine ve eğer doğruysa yapısının belirlenmesine olanak tanıyan bir dilbilgisidir. Tanıma dilbilgisi, rastgele bir dizenin belirli bir dile ait olması için kriteri belirler.
Biçimsel gramerler dilbilim ve programlamada yaygın olarak kullanılmaktadır.
doğal diller ve programlama dillerinin incelenmesiyle bağlantılı bilgi.
Otomatik ve dilsel modeller, temelleri N. Chomsky'nin eserlerinde atılan biçimsel dilbilgisi teorisi temelinde inşa edilmiştir. Bu teorinin ele aldığı ana nesneler, herhangi bir nitelikteki boş olmayan herhangi bir A kümesinin temel elemanları olan sembollerin yanı sıra bu elemanlardan oluşturulan zincirlerdir. A kümesine alfabe de denir.
Sembolleri Latin alfabesinin küçük harfleriyle ve soldan sağa doğru yönelmiş sayacağımız ffghhh biçimindeki zincirlerle göstereceğiz. Zincirleri ayrıca özel sembollerle de göstereceğiz - Latin alfabesinin büyük harfleri veya Yunan harfleri, örneğin: = ffg, B = abba. Tek bir karakter içermeyen boş bir zincirini dikkate alalım.
Bir zincirin uzunluğu, bu zincirde yer alan karakter sayısı olacaktır.
Zincirin uzunluğu şu şekilde gösterilir:
| | = | ffg | = 3;
| B | = | baba| = 4;
İki X ve Y zincirinin birleşimi, soldaki X zincirinin ve sağdaki Y zincirinin doğrudan birleştirilmesiyle elde edilen bir Z zinciridir. Örneğin, eğer X = ffg, Y = ghh ise, o zaman X ve Y'nin birleşimi Z = ffgghh zinciridir. Birleştirme işlemini o sembolü ile gösterelim. Bu işlemin özellikleri
aşağıdaki gibi yazılabilir:
1) kapanma özelliği:
o: A* × A* → A*;
2) çağrışım özelliği:
(∀X ∈ A*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
burada A*, boş zincir dahil olmak üzere sözlüğün temel elemanlarından (sembollerinden) oluşan sonlu bir A kümesinden oluşan tüm olası zincirlerin (tabii ki sonsuz) kümesini belirtir; x sembolü iki kümenin Kartezyen çarpımının çalışmasını belirtir; ve X, Y, Z, A*'ya ait keyfi zincirlerdir.
(A*, 0) çiftini düşünün. O operasyonunun listelenen özellikleri dikkate alındığında, bu çift, kimlik elemanı olan bir yarı grup veya bir monoiddir. Cebirde, yalnızca her yerde tanımlanmış bir ilişkisel işlemle donatılmış bir kümeye (bu durumda A*) yarı grup adı verilir.
Bir dize, L diline ait olabilir veya olmayabilir. L ≤ A* (burada A* bir monoiddir) dizelerinden oluşan herhangi bir küme, eğer bu diziler kümesi A alfabesinde tanımlanmışsa, biçimsel dil olarak adlandırılır.
Örnek 1. A, Rus alfabesindeki harflerden oluşan bir küme olsun. Daha sonra beş harften oluşan diziler kümesi L1 biçimsel dilini temsil eder. Aynı alfabede tanımlanan dilin bir başka örneği de L2 beş harfli dizidir.
Yazım sözlüğünde bulunabilecek Rus dilinin kelimeleri. Ah...
L1 dilinin birçok dizisi Rusça sözcük olmadığından L2 ⊂ L1 görülebilir.
B ve C, A* kümesinin bazı alt kümeleri olsun.
B ve C kümelerinin çarpımı zincirlerin D kümesidir;
B ve C zincirlerinin birleştirilmesinden oluşur;
D = ( X o Y | X ∈ B, Y ∈ C).
Ürün şu şekilde gösterilir: D = BC.
A alfabesini düşünün. 'den oluşan kümeyi A0 ile gösterelim. Tanımlamak
alfabenin derecesini her n ≥ 1 için Аn = An-1 A olarak bölün.
Alfabenin tüm olası zincirlerinin kümesinin olduğunu göstermek zor değil
Böyle bir diziye A alfabesinin yinelemesi denir. Alfabenin kesik yinelemesi
Favita A denir
X ve Y, A* kümesinin zincirleriyse, X zincirine zincirin alt zinciri denir.
Y tomurcukları, A*'dan U ve V zincirleri olduğunda öyle ki
Ayrıca, eğer U boş bir zincir ise, o zaman X alt zincirine zincirin başı denir.
ki Y ve eğer V boş bir zincirse, o zaman X'e Y zincirinin kuyruğu denir.
İki X ve Y dizisinin birleşimi XY veya XY ile gösterilir. A* x A*'dan (P1, Q1), (P2, Q2), ..., (Pn, Qn) zincir çiftlerini düşünün. Thue'nun ilişkileri herhangi bir değerin uyması gereken kurallar olacaktır.
A* kümesinden bir X = U Pi V tomurcuğu, aynı A* kümesinden (i = 1, 2, ..., n) bir Y = U Qi V zinciri ile ilişkilendirilecektir (i = 1, 2, ..., n) ve bunun tersi de geçerlidir. Bu ilişkiler sözde ilişkisel hesaba yol açar.
Y zinciri, X zincirinden bir Thue ilişkisinin tek bir uygulamasıyla (yani Pi alt zincirini Qi alt zinciriyle değiştirerek) elde ediliyorsa, X ve Y'nin bitişik zincirler olduğunu söyleyeceğiz.
Bir dizi zincir varsa, Xn zinciri X0 zinciriyle ilişkilidir.
X0, X1, ..., Xn,
öyle ki Xi-1 ve Xi bitişik zincirlerdir.
Örnek 2. A, Rus alfabesinin harfleri kümesi olsun.
Lim Thue'nun ilişkisi, bir kelimenin herhangi bir harfini diğeriyle değiştirme hakkından oluşur. Daha sonra UN, MUSE, LUZA, ASMA, POSE, ZAMAN, LİMAN, KEK zincirleri dizisinde herhangi iki bitişik zincir bitişiktir ve UN ve KEK zincirleri verilen ilişkiler anlamında ilişkilidir.
Thue ilişkilerinin tanıtılması, çeşitli türlerdeki otomatik dil modellerinin yapımında kullanılan birçok dil arasından belirli dil sınıflarının tanımlanmasını mümkün kılar.
X zinciri Y zincirine bitişikse ve bunun tersi durumda Y zinciri bitişikse Thue ilişkileri iki taraflıdır.
X zinciri. Biçimsel dilbilgisi teorisi açısından daha ilginç olan,
Yönün tanıtıldığı ilişkiler var.
Bu durumda bunlara Thue yarı bağıntıları veya çarpımları ve açıklamaları denir.
şu şekilde demek istiyorum:
(P1 → Q1), (P2 →Q2), ..., (Pn → Qn).
Bir ürün grubunun olması durumunda Y zincirinin eksik olduğunu söyleriz.
doğrudan X zincirinden üretilir ve eğer U ve V zincirleri mevcutsa X ⇒ Y olarak gösterilir;
X = U Pi V, Y = U Qi V,
ve (Pi → Qi) – bu setin ürünleri.
Ayrıca X'in Y'yi doğurduğu da söylenir.
Her biri için X0, X1, ..., Xn zincirlerinden oluşan bir dizi varsa
i = 1, 2, ..., n'den önce
X i-1 ⇒ X i,
daha sonra Xn'nin X0'dan oluştuğunu söylerler (X0, Xn'yi üretir) ve bunu X0 ⇒ * Xn olarak gösterirler. .
Chomskyan gramerleri resmi kombinatoryal şemalara karşılık gelir,
Thue yarı ilişkilerine dayanan Thue yarı sistemleridir
Dipnot: Bu bölümde disiplinin temelleri tartışılmaktadır: “biçimsel dilbilgisi”. Bu disiplin, sembollerle yapılan her türlü işlemi dikkate alır ve sonuçları, yapay zekanın yanı sıra resmi ve "insan" dillerinin analizinde yaygın olarak kullanılır. Bu ders dersteki en önemli ve aynı zamanda anlaşılması en zor derstir. Bu bağlamda yazar, matematiksel kanıtları atlayarak okuyucuya yalnızca kendi sonuçlarını sunmaktadır. Materyali daha iyi anlamak için önceki ve sonraki derslere başvurmanız gerekebilir.
10.1. Alfabe
İnsan herhangi bir dili öğrenmeye alfabeyle başlar. İÇİNDE resmi gramer Dil, anlamından bağımsız olarak tanımlanır. Üstelik aynı dil birden fazla gramerden oluşturulabilir! Tıpkı okulda olduğu gibi - sonuç (ders kitabının sonunda okunabilir) makbuzu kadar önemli değil - not defterine kaydedilen sorunun çözümü. Bu nedenle alfabenin tanımına resmi olarak da yaklaşalım.
Tanım. Bir alfabe, boş olmayan sonlu bir öğeler kümesidir.
“Klasik” bir dilde alfabe bir dizi harften oluşur. Fonetikte insanlar tarafından üretilen bir dizi konuşma sesi. Müzikte bu bir dizi nota vb.'dir.
Alfabeyi kullanarak tanımlamak genellikle mümkündür sonsuz küme kelimeler Dilbilgisi kullanılarak oluşturulabilen (başka bir deyişle dilbilgisi tarafından oluşturulan) tüm kelimelerin kümesine dil denir. Alfabenin aksine dil sonsuz olabilir.
Herhangi son sıra alfabe karakterleri buna kelime veya daha profesyonel anlamda zincir denir. (a, b, c) karakterlerinden oluşan zincirler şu diziler olacaktır: a, b, c, aa, ab, bc, ac, bb, abba ve diğerleri. Boş bir A zincirinin varlığına da izin verilir - sembollerin tamamen yokluğu. Zincirdeki karakterlerin sırası da önemlidir. Yani ab ve ba zincirleri farklı zincirlerdir. Ayrıca değişken ve sembol olarak büyük Latin harfleri kullanılacak, zincirleri belirtmek için ise küçük Latin harfleri kullanılacak. Örneğin:
X = SVT Listeleme 10.1.
S, V ve T karakterlerinden ve bu sırayla oluşan bir dize.
Tanım. Bir zincirin uzunluğu, bu zincirdeki karakter sayısıdır. |x| olarak gösterilir . Örneğin: |L| = 0, |A| = 1, |BA| = 2, |ABBA| = 4.
Eğer x ve y dize ise, bunların birleşimi xy dizisi olacaktır. Birleştirme sırasında zincirlerin yeniden düzenlenmesi sonucu değiştirir (grup teorisinde olduğu gibi). Eğer z = xy bir zincir ise, x zincirin başı, y ise kuyruğudur. Eğer zincirin başını önemsemiyorsak şunu belirteceğiz:
Z = … x Listeleme 10.2.
ve kuyruğu umursamıyorsak şunu yazacağız:
Z = x ...Liste 10.3.
Tanım. İki zincir kümesinin çarpımı, bu kümelerde yer alan tüm zincirlerin birleşimi olarak tanımlanır. Örneğin, A = (a, b) ve B = (c,d) olarak ayarlanırsa, o zaman:
AB = (ac, ad, bc, bd) Listeleme 10.4.
Kümelerin çarpımında birleştirmede olduğu gibi faktörlerin sırası önemlidir.
Hem zincirleri birleştirirken hem de zincir kümelerini çarparken birleşme yasası şu şekilde yazılır:
Z = (ab)c = a(bc) = abc Listeleme 10.5.
D = (AB)C = A(BC) = ABC Listeleme 10.6.
Ve son olarak zincirin derecesini belirliyoruz. Eğer x boş olmayan bir zincir ise, o zaman x 0 = (L), x 1 = x, x 2 = xx, x n = x(x) (n-1). Aynı şey kümelerin derecesi için de geçerlidir.
10.2. Terminal ve terminal olmayan semboller
Terminal kavramı ve terminal olmayan semboller ikame (veya üretim) kuralı kavramıyla yakından ilgilidir. Bunu tanımlayalım.
Tanım. Bir üretim veya ikame kuralı, şu şekilde yazılan sıralı bir (U, x) çiftidir:
U::= x Listeleme 10.7.
burada U bir semboldür ve x boş olmayan bir sonludur karakter dizisi.
Yalnızca sağ tarafta görünen karakterlere denir terminal karakterleri. Kuralların hem sol hem de sağ tarafında bulunan sembollere terminal olmayan semboller veya dilin sözdizimsel birimleri denir. Birçok terminal olmayan semboller VN olarak gösterilir ve terminal karakterleri-VT.
Not. Bu terminal tanımı ve terminal olmayan semboller KS gramerleri ve A gramerleri için geçerlidir (bkz. bölüm 10.4.3).
Tanım. Bir gramer G[Z], aşağıdakileri içeren sonlu, boş olmayan bir kurallar kümesidir: terminal olmayan sembol Z bir dizi kural üzerinde en az bir kez. Z karakterine başlangıç karakteri denir. Sonra hepimiz terminal olmayan semboller onu şu şekilde belirteceğiz<символ>.
[Örnek 01]
Dilbilgisi: "sayı"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
Başka bir tanım verelim:
Tanım. Aşağıdaki durumlarda v zinciri doğrudan w zincirini oluşturur:
v=x y ve w = xuy Liste 10.8.
Nerede ::= u bir gramer kuralıdır. Bu v => w olarak gösterilir. Ayrıca w'nin v'den doğrudan çıkarılabileceğini de söylüyoruz. Bu durumda x ve y zincirleri boş olabilir.
Tanım. Eğer u0, u1, …, u[n] (n > 0) gibi sonlu bir çıktı zinciri varsa, v'nin w'yi ürettiğini veya w'nin v'ye indirgendiğini söyleriz.
V = u0 => u1 => u2 => ... => u[n] = w Listeleme 10.9.
Bu diziye n uzunluğunda pin denir ve v =>+ w ile gösterilir. Ve sonunda şunu yazıyorlar:
V =>* w if v => w veya v =>+ w Liste 10.10.
10.3. Cümleler
Tanım. G[Z] bir gramer, x bir dize olsun. O zaman x'e cümlesel form denir, eğer
Tanım. G[Z] bir gramer olsun. Ve w = xuy bir cümlesel form olsun. O zaman u'ya w cümle formunun bir cümlesi denir. terminal olmayan sembol , Eğer:
Z =>* x y ve =>+ u Listeleme 10.11.
Z =>* x y ve => u Listeleme 10.12.
o zaman u dizisine basit bir ifade denir.
"Cümle" terimine dikkat etmelisiniz. Gerçek şu ki =>+ u (u zinciri şundan çıkarılabilir: ) u'nun x cümle biçimindeki bir cümle olduğu anlamına gelmez y; aynı zamanda gerekli zincirden düşülebilirlik X
y, dilbilgisi Z'nin ilk sembolünden.<чс>İfadeyi açıklamak için, [Örnek 01] cümle biçimini düşünün<чс>1. Bu, sembolün şu anlama geldiği anlamına mı geliyor?<число> ::= <чс>bir kural varsa bir ifadedir:<число><1>? Tabii ki hayır, çünkü zincirleme mümkün değil:<число>- başlangıç karakterinden:<чс>. Cümle biçimindeki cümleler nelerdir?
<число> => <чс> => <чс><цифра> => <чс><1>1? Çıktıyı düşünün:
Listeleme 10.13.
<число> =>* <чс>Böylece,<чс> =>+ <чс>Ve
1 Listeleme 10.14.
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
Bu öğeler, onları dilin cümlelerini oluşturan gerçek sözcüklerden ayırmak için açılı parantez içine alınmıştır. Örneğimizde sözlük şu beş kelimeden veya "karakterden" oluşur: V= (ev, meşe, karanlık, eski, (nokta)). Dilbilgisinin, bir dilde bu semboller kullanılarak cümlelerin nasıl oluşturulabileceğine ilişkin bilgileri içeren belirli kuralları vardır. Bu kurallardan biri:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
Bu kural şu şekilde yorumlanır: “Bir cümle, bir özne, ardından bir yüklem, sonra bir nesne ve bir noktadan oluşabilir.” Dilbilgisinde farklı yapıdaki cümleleri tanımlayan başka kurallar da olabilir. Ancak bu gramerde böyle bir kural yoktur. Kuralların geri kalanı şöyle:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое>® gizler
5. <прилагательное>® eski
6. <существительное>® ana sayfa
7. <существительное>® meşe
Bu dilbilgisini bir cümle oluşturmak (veya çıktısını almak) için uygulayalım.
Kural 1'e göre cümle şöyle görünür:
<предложение>1®<tabi e><сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><ek> 3 →
3 →<sıfat e><существительное> <сказуемое> <прилагательное> <существительное> 4 →Eski <существительное> <сказуемое> <sıfat e><существительное>
4 →Eskimiş <существительное > <сказуемое> eskimiş <существительное >
6.7 →Eski ev <сказуемое> eski meşe
4 → Eski ev, yaşlı meşe ağacının gölgesinde kalıyor
Böylece hazır bir teklif alıyoruz:
Eski bir ev eski bir meşe ağacı tarafından gizlenmiş.
Bu sonuç bir ağaç olarak görselleştirilebilir. Çıktı ağacı, çeşitli ara öğelere hangi kuralların uygulandığını gösterir ancak bunların uygulanma sırasını gizler. Böylece ortaya çıkan zincirin, ara elemanların değiştirilme sırasına bağlı olmadığı görülmektedir. Ağacın olduğunu söylüyorlar "sözdizimsel yapı" teklifler.
Çıkarım fikri, kurala benzer kuralların diğer yorumlarını gösterir <подлежащее> ® <прилагательное> <существительное> . " demek yerine ders Bu sıfat, ardından isim"şunu söyleyebiliriz ders"oluşturur" (veya "ondan türetilir" veya "ile değiştirilebilir")<sıfat><существительное>.
Yukarıdaki gramer kullanılarak üç cümle daha türetilebilir:
Eski bir meşe ağacı eski evi gizlemektedir.
Eski ev, eski evi gizler.
Eski bir meşe, eski bir meşeyi gizler.
Bu cümleler ve daha önce türetilen cümlelerin hepsi bu dilbilgisi tarafından oluşturulan cümlelerdir.
Bu dört cümleden oluşan kümeye, belirli bir dilbilgisi tarafından tanımlanan ("onun tarafından oluşturulan" veya "ondan türetilen") dil denir.
Resmi sistemlerden biri, A alfabesi ve formun sonlu bir ikame kümesi ile tanımlanan ikame sistemi veya Thue yarı sistemidir (adını Norveçli matematikçi Axel Thue'dan almıştır):
burada αi, βi muhtemelen A'da boş olan kelimelerdir, Þ daha önce bizim tarafımızdan "ima eder", "türetilmiş" olarak anlaşılan bir ikame sembolüdür.
Thue sistemi şu formun ilişkilerini kullanır:
ikame çiftleri olarak anlaşılır:
α i Þ β i (solda);
β i Üα i (sağda).
Thue yarı sisteminde, α i Þβ i ikamesi, R i çıkarım kuralı olarak yorumlanır. Amerikalı matematikçi N. Chomsky, 50'li yıllarda bu yarı sistemleri kullanarak, onların özel durumu olan resmi dilbilgisi teorisini oluşturup geliştirdi.
V'nin boş olmayan bir semboller dizisi - bir alfabe (veya sözlük) olmasına izin verin ve bu nedenle, V alfabesindeki tüm sonlu kelimelerin V * kümesi verilmiş olsun. V alfabesindeki resmi dil L, V *'nin keyfi bir alt kümesidir. . Dolayısıyla, V, Rus dilinin harflerini, noktalama işaretlerini, boşluk karakterlerini vb. içeriyorsa, o zaman V *, büyük Rus edebiyatının (yazılı ve gelecek) tüm eserlerini içeren varsayımsal bir settir.
Kelimeler, matematiksel işaretler, geometrik resimler vb. de sembol olarak kullanılabilir.
Diller belirtilir veya belirlenir dilbilgisi– belirli bir dilin tüm zincirlerini ve yalnızca bunları üreten bir kurallar sistemi.
Biçimsel dilbilgisi – biçimsel sistem, matematik.
Biçimsel gramerleri tanımak, üretmek ve dönüştürmek vardır.
tanımak, eğer verilen herhangi bir dizge için o dizgenin verilen gramer açısından doğru olup olmadığına karar verir.
Biçimsel dilbilgisine denir üretken, eğer doğru bir zincir oluşturabilirse.
Biçimsel dilbilgisine denir dönüştürücü Eğer doğru oluşturulmuş herhangi bir zincir için eşlemesini doğru bir zincir şeklinde oluşturur.
Üretken biçimsel dilbilgisi sınıfını düşünün.
G'nin üretken biçimsel dilbilgisi dörtlüdür
g=
burada T, sonlu terminal (ana) sembollerin sonlu, boş olmayan bir kümesidir;
N - sonlu, boş olmayan, terminal olmayan (yardımcı) semboller kümesi;
P, boş olmayan sonlu bir çıkarım kuralları (üretimler) kümesidir;
S başlangıç karakteridir.
T - uçbirim sözlüğü - dilbilgisi tarafından oluşturulan zincirlerin oluşturulduğu bir dizi başlangıç sembolü;
N - terminal olmayan sözlük - kaynak sembol sınıflarını belirten bir dizi yardımcı sembol.
Sonlu bir küme G gramerinin tam bir sözlüğüdür.
Çıkarım kuralı, φÞψ formundaki ikili ilişkilerin sonlu, boş olmayan bir kümesidir; burada φ ve ψ, V sözlüğündeki zincirlerdir ve Þ sembolü "ile değiştirilmiştir".
β zinciri, G gramerindeki α zincirinden doğrudan çıkarılabilir (αβ gösterimi; hangi gramerden bahsettiğimiz açıksa G alt simgesi atlanır) eğer α=α 1 φα 2 , β=α 1 ψα 2 , (φÞψ ).
β zinciri, "i =0,1,...,n-1 E i => şeklinde bir E 0 =α, E 1 ,E 2 ,…,E n =β dizisi varsa α'dan çıkarılabilir. E ben +1.
Bu diziye α'dan gelen β çıkışı adı verilir ve n, çıkışın uzunluğudur.
β'nın α'dan çıkarsanabilirliği α=> n β ile gösterilir (eğer türetmenin uzunluğunu belirtmeniz gerekiyorsa).
G dilbilgisi tarafından oluşturulan L(G) dili, S'den türetilen terminal sözlüğü T'deki dizeler kümesidir; burada S, bu dilbilgisinin amaçlandığı dilsel nesnelerin sınıfını belirten ilk semboldür. İlk sembole dilbilgisinin amacı veya aksiyomu denir.
L(G)=L(G 1) ise G ve G 1 gramerleri eşdeğerdir.
Doğal bir dili biçimsel dilbilgisi teorisi açısından tanımlarken, terminal sembolleri kelimeler veya morfemler - dilin en küçük anlamlı birimleri (kökler, son ekler vb.), terminal olmayan semboller - kelime sınıflarının adları olarak yorumlanır ve ifadeler (konu, yüklem, yüklem grubu vb. .p.). Bir karakter dizisi genellikle doğal dil cümlesi olarak yorumlanır.
Örnek 1. Gramer şu şekilde verilsin:
T-(a,b), N-(S,A,B), S-S,
P=(1. SŞaB; 2.SŞbA; 3. AŞaS; 4. AŞbAA; 5. AŞa; 6.BŞbS; 7. BŞaBB; 8. BŞb).
Tekliflerin tipik sonuçları:
Kullanılan çıkarım kuralının numarası okların üzerinde parantez içinde belirtilmiştir. Çıkış sona eriyor çünkü sol tarafı ab'ye eşit olan bir P kuralı yoktur.
Böyle bir üretken dilbilgisinin grafiği Şekil 2'de gösterilmektedir. 125.
Pirinç. 125. Üretken gramer grafiği
Burada a ve b son köşelerdir (terminal).
Örnek 2. Gramer şu şekilde verilsin:
T=(<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};
N=(<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};
Zincirin çıktısını alabilirsiniz<прилежный> <студент> <выполняет> <домашнее задание>.
Açıkçası, son çıkarım zinciri nihaidir ve doğal dildeki bir cümleyi temsil eder. Benzer şekilde zinciri de türetebilirsiniz.<ленивый> <студент> <не выполняет> <домашнее задание>. Bu örnekte terminal olmayan sembollerin sözdizimsel kategoriler olduğuna dikkat edin.
Çıktı aynı zamanda Şekil 2'de gösterilen yapı ağacıyla da açıklanabilir. 126.
Pirinç. 126. Cümle çıktısının yapısal ağacı
Dilbilgisi, bir sembol yerine, seri bağlantının bir zinciri gösterdiği ve paralel bağlantının zincirlerin varyantlarını gösterdiği anahtarlama devrelerine benzeyen Pascal dilinde olduğu gibi Wirth sözdizimsel diyagramları olarak adlandırılan diyagramlarla da belirlenebilir.
Yani biçimsel gramerler tanıyabilir, üretebilir, dönüştürebilir. Ayrıca biçimsel dilbilgisi teorisinde dört tür gramerin oluşturduğu dört tür dil vardır. Dilbilgisi, R kuralları sistemine giderek artan kısıtlamalar getirerek ayırt edilir.
Gramerlerin ve ürettikleri dillerin genel kabul görmüş sınıflandırması, dört tür grameri içeren Chomsky hiyerarşisidir.
0 gramer yazın j ve y'nin V'den herhangi bir dizi olabileceği, çıkarım kurallarına hiçbir kısıtlamanın getirilmediği bir dilbilgisidir. Böyle bir dilbilgisi bir Turing makinesi tarafından uygulanabilir. Bu durumda Turing makinesinin durumu terminal olmayan (yardımcı) sembollere karşılık gelir ve banttaki semboller terminal olanlara karşılık gelir. Zincir oluşturma kuralları bir komut sistemi tarafından tanımlanır.
Dilbilgisi yazınŞekil 1, tüm kuralları aАbÞawb biçiminde olan bir gramerdir; burada wÎТUN, A, terminal olmayan bir semboldür. A ve b zincirleri kuralların bağlamıdır. Kullanıldığında değişmezler. Bu nedenle, 1. tip gramerlerde, tek bir terminal sembolü A, yalnızca a ve b bağlamında boş olmayan bir w dizisine (A, w ile değiştirilebilir) gider. Tip 1 gramerlere bağlama duyarlı veya bağlama duyarlı denir.
Tip 2 dilbilgisi yalnızca AÞa biçimindeki kurallara izin verilen bir gramerdir; burada aÎТUN, yani. a, V'nin boş olmayan bir zinciridir. Tip 2 gramerlere bağlamdan bağımsız veya bağlamdan bağımsız denir. Modern algoritmik diller bağlamdan bağımsız dilbilgisi kullanılarak açıklanmaktadır.
Dilbilgisi yazın 3 – АŞaB veya AÞb biçiminde kurallara sahiptir; burada А,ВОN; a,bÎT.
Burada A,B,a,b karşılık gelen sözlüklerin tek karakterleridir (zincir değil). Bu tür gramerlerle tanımlanan dillere denir otomatik veya normal.
Bu durumda formun düzenli ifade dili (normal dil) kullanılır:
Böyle bir dil sonlu bir otomat (Kleene teoremi) tarafından verilir. Çoğu algoritmik dilde ifadeler, sonlu durum makineleri veya düzenli ifadeler kullanılarak belirtilir.
Sonlu bir otomatla normal bir dil belirleme örneğini ele alalım:
X=(0,1) – giriş simgeleri kümesi;
Y=(S,A,B,q k ) – dahili durumlar kümesi, q k – son durum, S – başlangıç durumu.
Bazen birkaç son durum dikkate alınır ve bir F kümesi halinde birleştirilir. Bu durumda, F=(qk) olur.
j: geçiş fonksiyonu – deterministik olmayan:
Sonlu, deterministik olmayan bir otomatın geçiş grafiği, Şekil 2'de gösterilmektedir. 127.
Pirinç. 127. Sonlu, deterministik olmayan bir otomatın geçiş grafiği
Karşılık gelen üretken dilbilgisi:
Karşılık gelen normal dil L= 
:
0, 010, 01010,...
Derleyicilerin yapımında biçimsel gramer teorisi kullanılır. Derleyici kaynak programı ayrıştırır. Aynı zamanda belirli bir karakter zincirinin doğru oluşturulmuş bir cümle olup olmadığı belirlenir ve eğer öyleyse formu geri yüklenir. Ayrıştırma veya sözdizimsel analiz, özel bir program - bir ayrıştırıcı (ayrıştırmak - ayrıştırmak) tarafından gerçekleştirilir. Bu sorunu çözmek için LEX ve YACC gibi özel programlar geliştirilmiştir.
UNIX işletim sisteminin standart LEX ve GREP programları vardır - bunlar normal dil teorisi temel alınarak oluşturulmuştur.
LEX programı, metnin sözcüksel analizini gerçekleştirir ve metni belirli bir düzenli ifadeler dizisine göre parçalara ayırır.
GREP programı - normal bir ifade kullanarak bir model seçer - yani. giriş sembolü akışından gelen sembollerin beslendiği sonlu durum makinesini oluştururken bir veya daha fazla dosyada bağlamsal arama gerçekleştirir.
Bir dilden diğerine otomatik çeviri sistemlerinde konu, yüklem, tanım ve tümleç tanımlanır; daha sonra gerekli dilin kurallarına göre uygun bir teklif hazırlanır.
Şu anda bilgisayarlar Promt, Magic Gooddy, Socrat Personal gibi çevirmenleri kullanıyor. Ayrıca .Context, Socrat Dictionary, MultiLex gibi basit sözlükler de kullanılmaktadır.
Dilsel bilginin biçimsel gramerler kullanılarak temsili, yapay zeka unsurları içeren sistemler gibi bir alanda kullanılan genel olarak bilgi temsili modellerinden biridir. Bilginin verilerden farklı olduğu, örneğin verilerin yalnızca karşılık gelen bilgisayar programı tarafından anlamlı bir şekilde yorumlanması ve bilgide anlamlı yorumlama olasılığının her zaman mevcut olması bakımından farklı olduğu unutulmamalıdır. Kullanıcı ile doğal veya doğal dile yakın bir arayüz sağlayan sistemlerin yazılım ve donanım kısmı hayata geçirilmektedir. dil işlemcisi Görevi, doğal dildeki metinleri bilgisayarın birlikte çalıştığı dahili temsilin resmi diline doğrudan ve ters tercüme etmektir.
Japonya'da bazı şirketler, ev sahibiyle iletişim kurabilen "konuşan" ev robotları satmaya başladı bile.
Dilsel işlemcinin bildirimsel ve prosedürel kısımları vardır. Birincisi sözlüklerin bir tanımını içerir, ikincisi ise doğal dildeki metinlerin analizi ve sentezi için bir algoritmadır.
Bilginin temsiline yönelik mantıksal modeller, önermeler ve yüklemlerin hesabını zaten biliyoruz.
Belirli bir konu alanıyla ilgili anlamsal (kavramsal) bilgiyi resmileştirmenin temeli, anlamsal ağlardır. Anlamsal bir ağ, köşeleri belirli nesnelerle ilişkilendirilen ve yaylar aralarındaki anlamsal ilişkilerle ilişkilendirilen yönlendirilmiş bir grafiktir. Köşe etiketleri doğası gereği referans niteliğindedir ve belirli adları temsil eder. İsimlerin rolü örneğin doğal dildeki kelimeler olabilir. Yay etiketleri bir ilişkiler kümesinin öğelerini belirtir. Ek olarak, çoğunlukla kalıplaşmış durumları temsil etmeye yönelik bir veri yapısı olarak tanımlanan bilgiyi temsil etmek için çerçeveler kullanılır.
Gödel'in teoremleri
Matematiksel mantıkta yüklem hesabının tutarlı olduğu kanıtlanmıştır; ve öğelerinin aynı anda görüntülenmesi mümkün değildir. Ek olarak, Gödel'in yüklem hesabının tamlığına ilişkin teoremi sayesinde, yüklem hesabında genel olarak geçerli bir formül çıkarılabilir.
Ele alınan yüklem hesabı birinci dereceden yüklem hesabıdır. İkinci dereceden analizde, yüklemlere göre niceleyiciler mümkündür, yani. "P(P(x)) biçimindeki ifadeler veya işlevlere göre.
Dolayısıyla önermeler mantığının tüm doğru ifadelerinin kümesi numaralandırılabilir ve karar verilebilirdir. Yüklem mantığının tüm doğru ifadelerinin kümesi numaralandırılabilir (tam olmasından dolayı), fakat karar verilemez (konu alanının sonsuz olmasından dolayı).
Matematiksel mantıktaki bir başka biçimsel teori olarak, İtalyan matematikçi Giuseppe Peano (1858-1932) tarafından önerilen sözde biçimsel aritmetik dikkate alınır. Peano, Î, U, I sembollerini ve işlemlerini tanıttı ve mantığı bir matematik disiplini olarak sunan ilk kişi oldu. Matematiği mantığa indirgemeye yönelik ilk girişim Alman matematikçi ve mantıkçı Gottlieb Frege (1848-1925) tarafından yapıldı. Kümeyi bir kavramın hacmi olarak tanımlayan oydu. Şunları yazdı: "Aritmetik, mantığın bir parçasıdır ve deneyimden veya düşünceden herhangi bir kanıt temeli almamalıdır." Tüm kümelerin kümesiyle ilgili ünlü paradoks, Frege'nin sisteminde Bertrand Russell tarafından tanımlanan bir çelişkidir.
Gödel, resmi aritmetik içeren herhangi bir resmi T teorisinin eksik olduğunu kanıtladı: doğru olan kapalı bir F formülü içerir, ancak ne F ne de T'de türetilebilir. Gödel'in ünlü eksiklik teoremine göre, resmi aritmetik içeren herhangi bir tutarlı resmi T teorisi için, T'nin tutarlılığını ifade eden formül T'de kanıtlanamaz.
Bu nedenle, aritmetik ve sayı teorisi, aksiyel olmayan teorilerdir ve aritmetiğin tüm doğru ifadelerinin kümesi sayılamaz.
Gödel'in teoremlerinin önemli metodolojik önemi vardır. Yeterince zengin matematik teorileri için yeterli formalizasyonların olmadığı ortaya çıktı. Doğru, tamamlanmamış herhangi bir T teorisi, ona doğru olan ancak T'de türetilemez bir formülün aksiyom olarak eklenmesiyle genişletilebilir, ancak yeni teori de eksik olacaktır; Ek olarak, bir teorinin meta özelliklerini, resmi teorinin kendi araçlarını kullanarak incelemek imkansızdır; Herhangi bir T metateorisinin en azından tutarlılığı kanıtlayabilmesi için T'den daha zengin olması gerekir.
Böylece, matematiği, tek meşru araçlar olarak ilan edilebilecek ve bunların yardımıyla herhangi bir teorinin meta-teorilerini inşa etmeye yönelik belirli bir sabit araçlar kümesi olarak yapılandırma yaklaşımı sorgulanmaktadır. Ancak bu kesinlikle biçimsel yaklaşımın çöküşü değildir. Çözülemeyen sorunların varlığı, yapıcı bir yaklaşımın uygun olmadığı anlamına gelmez; eğer bir şeyi yapamıyorsa, bu sadece kimsenin yapamamasından kaynaklanmaktadır.
Maddi olarak tanımlanmış teorilerin tam olarak formüle edilmesinin imkansızlığı, kavramın bir eksikliği değil, hiçbir kavramın ortadan kaldıramayacağı nesnel bir gerçektir.
Bir teorinin yeterli şekilde resmileştirilmesinin imkansızlığı, ya onun resmileştirilebilir parçalarının aranması ya da daha güçlü bir resmi teori inşa edilmesi gerektiği anlamına gelir; ancak bu yine eksik olacak, ancak belki de orijinal teorinin tamamını içerecektir.
KLASİK OLMAYAN MANTIK
GİRİŞ………… ………………………………….…………….4
Bölüm 1. DİLLER VE GRAMER. SEMBOLLER, TANIMLAR VE SINIFLANDIRMA………………………………………………………………………………6
1.1. Dil grameri kavramı. Tanımlar……………………………………………………7
1.2. Gramerlerin Chomsky'ye göre sınıflandırılması………………………..…………………13
1.3. KS- ve A-gramer oluşturma teknikleri………………………………………………………..16
1.4. KS gramerlerinde sözdizimsel çıkarım ağaçları. Performans
Durum grafiği biçiminde A-grameri. Dilbilgisinin belirsizliği……………..19
1.5. A dillerinin sözdizimsel analizi…………………………………………………..23
Alıştırmalar………………………………………………………………………………….29
Bölüm 2. TANIYICILAR VE MAKİNELER.……………………………….….…………32
Bölüm 3. OTOMATİN DİL BİLGİSİ VE SONLU MAKİNELER…………….35
3.1. Otomatik gramerler ve sonlu otomatlar…………………………………….35
3.2.Deterministik olmayan ve deterministik A gramerlerinin denkliği...... 36
Egzersizler………………………………………………………………………………… 41
Bölüm 4. EŞDEĞER BAĞLAMDAN BAĞIMSIZ DÖNÜŞÜMLER
VE OTOMATİK DİL BİLGİLERİ………………………………………………..….42
4.2. Dilbilgisindeki çıkmaz kuralların ortadan kaldırılması………………………………………46
4.3. Genelleştirilmiş KS gramerleri ve gramerlerin uzatma biçimine indirgenmesi…….48
4.4. Sol yinelemenin ve sol çarpanlara ayırmanın ortadan kaldırılması……………………………..…52
Alıştırmalar……………………………………………………………………………….53
Bölüm 5. OTOMATİK VE BAĞLAMDAN BAĞIMSIZ DİLLERİN ÖZELLİKLERİ…55
5.1. A dilleri ve KS dilleri zincirlerine genel bakış…………………………………………………………..55
5.2. Diller üzerinde işlemler……………………………………………………………….59
5.2.1. CS dillerindeki işlemler………………………………………………………59
5.2.2. A dilleri üzerinde işlemler………………………………………………………62
5.2.3. K dilleri üzerinde işlemler………………………………………………………66
5.3. Uygulamaya yönelik sonuçlar…………….…………………………………………………………….67
5.4. KS dilbilgisi ve dillerinin belirsizliği…………………………………………………………71
Alıştırmalar…………………………………………………………………………………….74
Bölüm 6. Bilgisayar Bilimleri Dillerinin Sözdizimsel Analizi……………………………...……...75
6.1. CS dillerini analiz etme yöntemleri. Öncelik gramerleri………………….…75
6.2. Wirth'in öncelikli gramerleri……………………………………………………………...77
Floyd'un öncelikli gramerleri…….…………………………………………………………79
Öncelik fonksiyonları………………………………………………………81
Egzersizler………………………………………………………………………………84
Bölüm 7. Anlambilime Giriş……………………………………………………….85
7.1. Lehçe ters gösterimi….………………………………………………………85
7.2. POLIZ’in yorumlanması……………………………….…………………………..….87
7.3. POLIZ için komutlar oluşturuluyor………………………………….…………...89
7.4. İfadeleri POLIZ'e çevirmek için Zamelson ve Bauer'in algoritması………..……….91
7.5. Dilbilgilerini niteliklendirin………………………………………………………………………………97
Alıştırmalar…………………………………………………………………………………..100
Bölüm 8. DERLEMENİN ANA AŞAMALARI……………………………………...……100
ÇÖZÜM
BAŞVURU…………………………………………………………………………………105
KONU DİZİNİ……………………………………………………….…….…115
giriiş
Dilbilim- dil bilimi. Matematiksel dilbilim- Dil oluşturma ve öğrenmenin resmi yöntemleriyle ilgilenen bir bilim.
Biçimsel gramer teorisi- dillerin biçimsel gramerlerini tanımlama yöntemlerini, zincirlerin bir dile aitliğini analiz etmek için yöntemler ve algoritmalar oluşturma yöntemlerini ve ayrıca algoritmik dilleri makine diline çevirme algoritmalarını içeren matematiksel dilbilimin bir bölümü.
Bu teorinin yaratılması ve geliştirilmesinin itici gücü, bilgisayar teknolojisinin gelişmesi ve bunun sonucunda da kişi ile bilgisayar arasındaki iletişim araçlarına duyulan ihtiyaçtı. Tüm uygulamalarda bilgisayar, kullanıcının problem çözme algoritmaları ve ilk verilerle iletişim kurabileceği bir dili anlamalıdır. Her bilgisayarın, ikili kodla temsil edilen ve bireysel işlemci işlemlerini yansıtan kendi makine talimatları dili vardır. Bilgisayar teknolojisinin gelişiminin ilk aşamalarında programcılar bilgisayarlarla bu ilkel dilde iletişim kuruyorlardı, ancak insanlar makinenin dijital dili açısından iyi düşünemiyorlardı. Programlamanın otomasyonu, önce montaj dillerinin, ardından da yüksek seviyeli algoritmik dillerin yaratılmasına yol açtı; bu dillerden yerel makine diline çeviri, bilgisayarın kendisine emanet edildi. Bu tür çeviri programlarına denir yayıncılar.
Birçok yazılım geliştiricisi, dili bir makineye açıklama sorunuyla karşı karşıyadır. Yeni diller icat etmek insan doğasıdır. Burada sadece yeni algoritmik programlama dilleri için karmaşık derleyicilerden bahsetmiyoruz. Herhangi bir otomatik sistemin bazı giriş sorgulama dillerini anlaması gerekir. Yeni bilgi teknolojileri, bilgisayar teknolojisi ve programlama teknolojisi alanında değil, belirli bir alanda uzman olan son kullanıcının (bilim adamı, tasarımcı, teknoloji uzmanı, operatör) sorunlarını bilgisayarda çözmede katılımını içerir. Bu problemin kaliteli bir çözümü için, kullanıcı ile bilgisayar arasında akıllı bir arayüzün bulunması gerekir: Kullanıcı, problemler oluşturmalı ve çözümlerinin sonuçlarını, bildiği konu alanına göre elde etmelidir. Yani, alana özgü geniş bir dil yelpazesi geliştirmek gereklidir. Bir yazılım uzmanı dillerin nasıl oluşturulduğunu ve yazılım desteklerini bilmelidir.
Dili bir makineye açıklamak için onun nasıl çalıştığını ve onu nasıl anladığımızı net bir şekilde anlamamız gerekir. Düşündüğümüzde ana dilimizi nasıl anladığımızı bilmediğimizi görüyoruz. Bu anlayışın süreci bilinçaltı ve sezgiseldir. Ancak bir çevirmen yaratabilmek için metni, bu metnin gerektirdiği eylemlere dönüştürecek bir algoritmaya sahip olmak gerekir ve bu da, bunu gerektirir. dil resmileştirme. Dilin biçimselleştirilmesi sorunları matematiksel dilbilim tarafından çözülür. Doğal diller çok karmaşıktır ve bunları tamamen resmileştirmek henüz mümkün değildir. Algoritmik diller ise tam tersine, zaten formalizasyon göz önünde bulundurularak yaratılmıştır. Biçimsel diller teorisi, matematiksel dilbilimin en gelişmiş dalıdır ve esasen dili bir makineye açıklamaya yönelik bir tekniği temsil eder. Bu teorinin tanımlarına, modellerine ve yöntemlerine bakmadan önce doğal dillerden örnekler kullanarak bazı kavramlara bakalım.
Dil- belirli kurallara göre oluşturulmuş bir dizi cümle (ifade).
Dilbilgisi- Bir ifadenin bir dile ait olup olmadığını belirleyen bir dizi kural.
Herhangi bir dil, karar verilebilirlik ve belirsizlik özelliklerini karşılamalıdır.
Dil çözülebilir, eğer sonlu bir süre içinde bir cümlenin veya cümlenin dile ait olduğunu belirlemek mümkünse. Dil açıktır, herhangi bir ifadenin benzersiz bir şekilde anlaşılması durumunda.
Dilbilgisinin ana bölümleri sözdizimi ve anlambilimdir.
Sözdizimi- Bir dilde cümlelerin doğru şekilde kurulmasını belirleyen bir dizi kural.
Anlambilim- Bir dildeki cümlelerin anlamsal veya anlamsal doğruluğunu belirleyen bir dizi kural.
Bir cümle sözdizimsel olarak doğru ve anlamsal olarak yanlış olabilir.
Sözdizimi genellikle bir dildeki tüm ifadelerin anlamlı olmasının gerekmemesi nedeniyle basitleştirilmiştir. Fütüristlerin ne demek istediğini veya bazı politikacıların konuşmalarını anlamak çoğu zaman zordur. Bu bağlamda akademisyen L.V. Shcherba'nın örneği ilginçtir: "Glokka kuzdra shteko bokr'ı kelleştirdi ve bokrenka'yı kıvırıyor." Bu, cümlenin üyeleri tarafından ayrıştırılabildiği için Rusça bir ifadedir, ancak anlamı belirsizdir.
Bir cümlenin sözdizimsel analizi bir ayrıştırma ağacı biçiminde yazılabilir. Ağacın özne, yüklem, özne grubu, cümle gibi düğümleri sözdizimsel kavramlara karşılık gelir, yaprakları ise cümlenin oluşturulduğu kelimelerdir. Bir ağacın yaprak ve dallarından bazılarını keserek cümlesel bir biçim (çıkarılabilir bir zincir) elde ederiz.
<предложение>
İfadenin belirsizliğinin doğası, "Anne kızını seviyor" ifadesi için aynı ayrıştırma ağacı örneği kullanılarak açıklanabilir.
Bu ifade belirsizdir çünkü iki ayrıştırma seçeneği vardır. Sözdizimsel belirsizlik doğrudan anlamsal belirsizliği beraberinde getirir. Ancak, kelimelerin belirsiz anlamlarından dolayı anlaşılmayabilecek, sözdizimsel olarak net ifadelere örnekler de sunabilirsiniz. Algoritmik dilin net olması gerektiğini hatırlayalım.
Biçimsel dil, doğal dillerdeki sıradan dilsel kavramların genelleştirilmesi olarak ortaya çıkan matematiksel bir soyutlamadır. Biçimsel diller teorisi esas olarak dillerin sözdizimini inceler ve çeviri, derleme ve derlemeyi içeren sözdizimsel olarak kontrol edilen çeviri süreçlerinin temelini oluşturur. Bu teorinin temelleri Amerikalı matematikçi N. Chomsky tarafından 50'li yılların sonu ve 60'lı yılların başında atılmış ve bilgisayar teknolojisinin gelişmesiyle birlikte günümüze kadar gelişmeye devam etmektedir. Bu teorinin ana unsurları üzerinde duralım.