Dalam kes umum, bahasa ialah set tak terhingga, dan objek tak terhingga bahkan sukar untuk ditakrifkan: mereka tidak boleh ditakrifkan dengan hanya menyenaraikan elemen. Sebarang mekanisme terhingga untuk menentukan bahasa dipanggil tatabahasa.
Bahasa formal ialah satu set rentetan dalam beberapa abjad terhingga. Bahasa formal termasuk bahasa buatan untuk komunikasi manusia-mesin—bahasa pengaturcaraan.
Untuk menentukan perihalan bahasa formal, adalah perlu, pertama sekali, untuk menentukan abjad, iaitu, satu set objek yang dipanggil simbol (atau huruf), setiap satunya boleh diterbitkan semula dalam bilangan salinan yang tidak terhad (seperti huruf bercetak biasa. atau nombor), dan, kedua, untuk mentakrifkan tatabahasa formal bahasa, iaitu, menyenaraikan peraturan yang menggunakan simbol untuk membina urutan kepunyaan bahasa yang ditakrifkan—rantai biasa.
Peraturan tatabahasa formal boleh dianggap sebagai produk (peraturan inferens), iaitu, operasi asas yang, apabila digunakan dalam urutan tertentu pada rantai asal (aksiom), hanya menghasilkan rantai yang betul. Urutan peraturan yang digunakan dalam proses menghasilkan rantaian tertentu adalah kesimpulannya. Bahasa yang ditakrifkan dengan cara ini adalah sistem formal.
Mengikut kaedah menentukan rantai yang betul, tatabahasa formal dibahagikan kepada yang generatif dan pengiktirafan. Tatabahasa generatif termasuk tatabahasa bahasa L,
dari mana adalah mungkin untuk membina mana-mana rantai "betul" yang menunjukkan strukturnya, dan adalah mustahil untuk membina satu rantai yang salah. Tatabahasa pengiktirafan bahasa L ialah tatabahasa yang membolehkan seseorang menentukan sama ada rentetan yang dipilih secara sewenang-wenangnya betul dan, jika betul, kemudian untuk menentukan strukturnya. Tatabahasa pengecaman menetapkan kriteria untuk rentetan arbitrari untuk dimiliki dalam bahasa tertentu.
Tatabahasa formal digunakan secara meluas dalam linguistik dan pengaturcaraan.
pengetahuan berkaitan dengan kajian bahasa semula jadi dan bahasa pengaturcaraan.
Model automatik dan linguistik dibina berdasarkan teori tatabahasa formal, asas-asasnya diletakkan dalam karya N. Chomsky. Objek utama yang digunakan oleh teori ini ialah simbol, yang merupakan unsur asas bagi mana-mana set tidak kosong A dalam sebarang sifat, serta rantai yang dibina daripada unsur-unsur ini. Set A juga dipanggil abjad.
Kami akan menandakan simbol dengan huruf kecil abjad Latin, dan rantai – dalam bentuk ffghhh, yang akan kami anggap berorientasikan dari kiri ke kanan. Kami juga akan menandakan rantai dengan simbol khas - huruf besar abjad Latin atau huruf Yunani, contohnya: = ffg, B = abba. Mari kita perkenalkan rantai kosong yang tidak mengandungi satu aksara.
Panjang rantai ialah bilangan aksara yang disertakan dalam rantaian ini.
Panjang rantai ditunjukkan seperti berikut:
| | = | ffg | = 3;
| B | = | abba| = 4;
Penyambungan dua rantai X dan Y ialah rantai Z yang diperoleh dengan mencantumkan rantai X di sebelah kiri dan rantai Y di sebelah kanan. Contohnya, jika X = ffg, Y = ghh, maka penyatuan X dan Y ialah rantai Z = ffgghh. Mari kita nyatakan operasi penggabungan dengan simbol o. Sifat operasi ini
boleh ditulis seperti berikut:
1) harta penutupan:
o: A* × A* → A*;
2) harta pergaulan:
(∀X ∈ A*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
di mana A* menandakan set semua rantai yang mungkin (tak terhingga, sudah tentu), terdiri daripada set terhingga A unsur asas (simbol) kamus, termasuk rantai kosong ; simbol x menandakan operasi hasil darab Cartesan bagi dua set; dan X, Y, Z ialah rantai sembarangan milik A*.
Pertimbangkan pasangan (A*, 0). Dengan mengambil kira sifat tersenarai bagi operasi o, pasangan ini ialah semikumpulan dengan unsur identiti atau monoid. Dalam algebra, hanya satu set (dalam kes ini A*) yang dilengkapi dengan operasi bersekutu yang ditentukan dipanggil semikumpulan.
Rentetan mungkin tergolong dalam bahasa L atau mungkin bukan. Mana-mana set rentetan L ≤ A* (dengan A* ialah monoid) dipanggil bahasa formal jika set rentetan ini ditakrifkan dalam abjad A.
Contoh 1. Biarkan A ialah satu set huruf abjad Rusia. Kemudian set rentetan yang terdiri daripada lima huruf mewakili bahasa formal L1. Satu lagi contoh bahasa yang ditakrifkan dalam abjad yang sama ialah set L2 lima huruf
perkataan bahasa Rusia yang boleh didapati dalam kamus ejaan. Aduh-
seseorang boleh melihat L2 ⊂ L1, kerana banyak rentetan bahasa L1 bukan perkataan Rusia.
Biarkan B dan C ialah beberapa subset bagi set A*.
Hasil darab bagi set B dan C ialah set D bagi rantai, iaitu
terdiri daripada penyambungan rantai B dan C, i.e.
D = ( X o Y | X ∈ B, Y ∈ C).
Produk ditandakan seperti berikut: D = BC.
Pertimbangkan abjad A. Mari kita nyatakan set yang terdiri daripada dengan A0. takrifkan
bahagikan darjah abjad sebagai Аn = An-1 A untuk setiap n ≥ 1.
Ia tidak sukar untuk menunjukkan bahawa set semua kemungkinan rantai abjad
Set sedemikian dipanggil lelaran abjad A. Lelaran abjad yang dipotong
Favita A dipanggil
Jika X dan Y ialah rantai bagi set A*, maka rantai X dipanggil subrantai bagi rantai itu
tunas Y, apabila terdapat rantai U dan V daripada A* sedemikian
Lebih-lebih lagi, jika U adalah rantai kosong, maka subchain X dipanggil ketua rantai
ki Y, dan jika V ialah rantai kosong, maka X dipanggil ekor rantai Y.
Penyatuan dua rentetan X dan Y dilambangkan XY atau XY. Pertimbangkan pasangan rantai (P1, Q1), (P2, Q2), ..., (Pn, Qn) daripada A* x A*. Hubungan Thue akan menjadi peraturan mengikut mana-mana nilai
putik X = U Pi V daripada set A* akan dikaitkan dengan rantai Y = U Qi V daripada set A* yang sama (i = 1, 2, ..., n) dan sebaliknya. Hubungan ini membawa kepada apa yang dipanggil kalkulus bersekutu.
Jika rantaian Y diperoleh daripada rantai X dengan satu aplikasi satu hubungan Thue (iaitu, menggantikan subchain Pi dengan subchain Qi), kita akan mengatakan bahawa X dan Y ialah rantai bersebelahan.
Rantaian Xn berkorelasi dengan rantai X0 jika terdapat urutan rantai
X0, X1, ..., Xn,
supaya X i-1 dan Xi ialah rantai bersebelahan.
Contoh 2. Biarkan A ialah set huruf abjad Rusia yang mana
hubungan lim Thue, yang terdiri daripada hak untuk menggantikan mana-mana satu huruf perkataan dengan mana-mana huruf lain. Kemudian dalam urutan rantai FLOUR, MUSE, LUZA, VINE, POSE, TIME, PORT, CAKE, mana-mana dua rantai bersebelahan adalah bersebelahan, dan rantai FLOUR dan CAKE dikaitkan dalam erti kata hubungan yang diberikan.
Pengenalan hubungan Thue memungkinkan untuk mengenal pasti kelas bahasa tertentu di antara banyak bahasa, yang digunakan dalam pembinaan model linguistik automatik pelbagai jenis.
Hubungan Thue adalah dua belah jika rantai X bersebelahan dengan rantai Y, dan sebaliknya, rantai Y bersebelahan dengan
rantai X. Lebih menarik, dari sudut teori tatabahasa formal, ialah
Terdapat hubungan di mana arah diperkenalkan.
Dalam kes ini, mereka dipanggil semi-hubungan Thue atau produk dan perihalan.
bermaksud seperti berikut:
(P1 → Q1), (P2 →Q2), ..., (Pn → Qn).
Dalam kes di mana terdapat satu set produk, kami mengatakan bahawa rantai Y tidak lengkap.
dijana terus daripada rantai X, dan dilambangkan sebagai X ⇒ Y jika wujud rantai U dan V sedemikian
X = U Pi V, Y = U Qi V,
dan (Pi → Qi) – produk daripada set ini.
Dikatakan juga bahawa X melahirkan Y.
Jika terdapat urutan rantai X0, X1, ..., Xn supaya bagi setiap satu
sebelum i = 1, 2, ..., n
X i-1 ⇒ X i ,
maka mereka mengatakan bahawa Xn dijana daripada X0 (X0 menjana Xn), dan menandakannya sebagai X0 ⇒ * Xn. .
Tatabahasa Chomskyan sepadan dengan skema gabungan formal,
iaitu separa sistem Thue berdasarkan separa hubungan Thue
Anotasi: Bahagian ini membincangkan asas-asas disiplin: "tatabahasa formal". Disiplin ini menganggap sebarang operasi dengan simbol, dan kesimpulannya digunakan secara meluas dalam analisis bahasa formal dan "manusia", serta dalam kecerdasan buatan. Syarahan ini adalah yang paling penting dan, pada masa yang sama, syarahan yang paling sukar untuk difahami dalam kursus. Dalam hal ini, penulis membentangkan pembaca hanya dengan kesimpulannya, meninggalkan bukti matematik. Untuk lebih memahami bahan tersebut, anda mungkin perlu merujuk kuliah sebelumnya dan seterusnya.
10.1. Abjad
Seseorang mula mempelajari apa-apa bahasa dengan abjad. DALAM tatabahasa formal bahasa ditakrifkan tanpa mengira maknanya. Selain itu, bahasa yang sama boleh dibentuk oleh beberapa tatabahasa! Ia seperti di sekolah - hasilnya (yang boleh dibaca di penghujung buku teks) tidak sepenting resitnya - penyelesaian kepada masalah yang direkodkan dalam buku nota. Oleh itu, marilah kita mendekati definisi abjad secara formal.
Definisi. Abjad ialah set elemen terhingga yang tidak kosong.
Dalam bahasa "klasik", abjad ialah satu set huruf. Dalam fonetik, satu set bunyi pertuturan yang dibuat oleh manusia. Dalam muzik, ini adalah satu set nota, dsb.
Menggunakan abjad selalunya boleh diterangkan set tak terhingga perkataan Himpunan semua perkataan yang boleh dibuat menggunakan tatabahasa (dengan kata lain, dijana oleh tatabahasa) dipanggil bahasa. Tidak seperti abjad, bahasa boleh menjadi tidak terhingga.
mana-mana urutan akhir aksara abjad dipanggil perkataan, atau, lebih profesional, rantai. Rantaian yang terdiri daripada aksara (a, b, c) akan menjadi urutan berikut: a, b, c, aa, ab, bc, ac, bb, abba dan lain-lain. Kewujudan rantai kosong A juga dibenarkan - ketiadaan simbol sepenuhnya. Susunan watak dalam rantai juga penting. Jadi, rantai ab dan ba adalah rantai yang berbeza. Selanjutnya, huruf Latin besar akan digunakan sebagai pembolehubah dan simbol, dan huruf Latin huruf kecil akan menunjukkan rantai. Sebagai contoh:
X = Penyenaraian SVT 10.1.
rentetan yang terdiri daripada aksara S, V dan T, dan dalam susunan itu.
Definisi. Panjang rantai ialah bilangan aksara dalam rantai ini. Ia dilambangkan sebagai |x| . Sebagai contoh: |L| = 0, |A| = 1, |BA| = 2, |ABBA| = 4.
Jika x dan y ialah rentetan, maka penggabungan mereka akan menjadi rentetan xy. Menyusun semula rantai semasa penggabungan mengubah hasilnya (seperti dalam teori kumpulan). Jika z = xy ialah rantai, maka x ialah kepala dan y ialah ekor rantai itu. Jika kita tidak mengambil berat tentang kepala rantai, kita akan menandakan:
Z = … x Penyenaraian 10.2.
dan jika kami tidak mengambil berat tentang ekor, kami akan menulis:
Z = x ...Penyenaraian 10.3.
Definisi. Hasil darab dua set rantai ditakrifkan sebagai gabungan semua rantai yang termasuk dalam set ini. Contohnya, jika set A = (a, b), dan B = (c,d), maka:
AB = (ac, ad, bc, bd) Penyenaraian 10.4.
Dalam hasil darab set, seperti dalam penggabungan, susunan faktor adalah penting.
Kedua-dua apabila menggabungkan rantai dan apabila mendarabkan set rantai, hukum bersekutu kekal benar, ditulis sebagai:
Z = (ab)c = a(bc) = abc Penyenaraian 10.5.
D = (AB)C = A(BC) = Penyenaraian ABC 10.6.
Dan akhirnya, kami menentukan tahap rantaian. Jika x ialah rantai bukan kosong, maka x 0 = (L), x 1 = x, x 2 = xx, x n = x(x) (n-1). Begitu juga dengan darjah set.
10.2. Simbol terminal dan bukan terminal
Konsep terminal dan simbol bukan terminal berkait rapat dengan konsep peraturan penggantian (atau pengeluaran). Mari kita takrifkannya.
Definisi. Peraturan pengeluaran, atau penggantian, ialah pasangan tertib (U, x), ditulis sebagai:
U::= x Penyenaraian 10.7.
dengan U ialah simbol dan x ialah terhingga tidak kosong rentetan aksara.
Watak yang muncul hanya di sebelah kanan dipanggil aksara terminal. Simbol yang terdapat pada kedua-dua belah kiri dan kanan peraturan dipanggil simbol bukan terminal, atau unit sintaksis bahasa. Sekumpulan simbol bukan terminal dilambangkan sebagai VN, dan aksara terminal- VT.
Catatan. Takrif terminal dan simbol bukan terminal benar untuk tatabahasa KS dan tatabahasa A (lihat bahagian 10.4.3).
Definisi. Tatabahasa G[Z] ialah set peraturan yang terhingga dan tidak kosong yang mengandungi simbol bukan terminal Z sekurang-kurangnya sekali pada satu set peraturan. Watak Z dipanggil watak permulaan. Seterusnya kita semua simbol bukan terminal kami akan menandakannya sebagai<символ>.
[Contoh 01]
Tatabahasa: "nombor"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
Mari kita berikan definisi lain:
Definisi. Rantaian v secara langsung menjana rantai w jika:
V=x y dan w = xuy Penyenaraian 10.8.
di mana ::= u ialah peraturan tatabahasa. Ini dilambangkan sebagai v => w. Kami juga mengatakan bahawa w boleh ditolak secara langsung daripada v. Dalam kes ini, rantai x dan y boleh kosong.
Definisi. Kami mengatakan bahawa v menjana w, atau w dikurangkan kepada v, jika terdapat rantaian terhingga output u0, u1, …, u[n] (n > 0) supaya
V = u0 => u1 => u2 => ... => u[n] = w Penyenaraian 10.9.
Urutan ini dipanggil pin panjang n, dan dilambangkan dengan v =>+ w. Dan akhirnya mereka menulis:
V =>* w jika v => w atau v =>+ w Penyenaraian 10.10.
10.3. Frasa
Definisi. Biarkan G[Z] ialah tatabahasa, x rentetan. Maka x dipanggil bentuk ayat jika
Definisi. Biarkan G[Z] menjadi tatabahasa. Dan biarkan w = xuy menjadi bentuk ayat. Kemudian u dipanggil frasa bentuk ayat w untuk simbol bukan terminal , Jika:
Z =>* x y dan =>+ u Penyenaraian 10.11.
Z =>* x y dan => u Penyenaraian 10.12.
maka rentetan u dipanggil frasa mudah.
Anda perlu berhati-hati dengan istilah "frasa". Hakikat bahawa =>+ u (rantaian u boleh disimpulkan daripada ) tidak bermakna u ialah ayat dalam bentuk ayat x y; juga perlu penolakan rantai x y daripada simbol awal tatabahasa Z.
Untuk menggambarkan frasa, pertimbangkan [Contoh 01] bentuk ayat<чс>1 . Adakah ini bermakna bahawa simbol<чс>ialah frasa jika terdapat peraturan:<число> ::= <чс>? Sudah tentu tidak, kerana rantaian tidak mungkin:<число><1>- dari watak awal:<число>. Apakah ayat-ayat bentuk ayat?<чс>1 ? Pertimbangkan output:
<число> => <чс> => <чс><цифра> => <чс><1>Penyenaraian 10.13.
Oleh itu,
<число> =>* <чс>Dan<чс> =>+ <чс>1 Penyenaraian 10.14.
Mari kita pertimbangkan tatabahasa formal, yang sedikit sebanyak menyerupai serpihan tatabahasa Rusia dan menentukan bahasa formal yang terdiri daripada empat ayat Rusia. Tatabahasa formal ini menggunakan unsur-unsur yang bertindak sebagai ahli ayat atau bahagian ucapan:
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
Unsur-unsur ini disertakan dalam kurungan sudut untuk membezakannya daripada perkataan kosa kata sebenar yang membentuk ayat-ayat bahasa tersebut. Dalam contoh kami, kamus terdiri daripada lima perkataan atau "watak" berikut: V= (rumah, oak, tidak jelas, lama, (titik)). Tatabahasa mempunyai peraturan tertentu yang mengandungi maklumat tentang cara ayat dalam bahasa boleh dibina menggunakan simbol ini. Salah satu peraturan ini ialah:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
Peraturan ini ditafsirkan seperti berikut: "Ayat boleh terdiri daripada subjek, diikuti oleh predikat, kemudian objek, dan titik." Mungkin terdapat peraturan lain dalam tatabahasa yang mentakrifkan ayat daripada struktur yang berbeza. Walau bagaimanapun, dalam tatabahasa ini tidak ada peraturan sedemikian. Peraturan selebihnya ialah:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое>® mengaburkan
5. <прилагательное>® lama
6. <существительное>® rumah
7. <существительное>® oak
Mari kita gunakan tatabahasa ini untuk menjana (atau mengeluarkan) ayat.
Menurut peraturan 1, ayat itu kelihatan seperti:
<предложение>1®<subjek kepada e><сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><tambahan> 3 →
3 →<kata sifat e><существительное> <сказуемое> <прилагательное> <существительное> 4 →Lama <существительное> <сказуемое> <kata sifat e><существительное>
4 →Tua <существительное > <сказуемое> tua <существительное >
6.7 →Rumah lama <сказуемое> pokok oak tua
4 → Rumah lama dikaburi oleh pokok oak tua
Oleh itu, kami mendapat cadangan siap sedia:
Sebuah rumah lama dikaburi oleh pokok oak tua.
Kesimpulan ini boleh digambarkan sebagai pokok. Pepohon keluaran menunjukkan peraturan yang digunakan pada pelbagai elemen perantaraan, tetapi menyembunyikan susunan ia digunakan. Oleh itu, dapat dilihat bahawa rantai yang terhasil tidak bergantung pada susunan penggantian elemen perantaraan dibuat. Mereka mengatakan bahawa pokok itu "struktur sintaksis" tawaran.
Idea inferens menunjukkan tafsiran lain tentang peraturan yang serupa dengan peraturan <подлежащее> ® <прилагательное> <существительное> . Daripada berkata " subjek ini kata sifat, diikuti oleh kata nama", kita boleh katakan begitu subjek"menjana" (atau "diperolehi daripadanya", atau "boleh digantikan dengan")<kata sifat><существительное>.
Menggunakan tatabahasa di atas, tiga ayat lain juga boleh diterbitkan, iaitu:
Pokok oak tua mengaburi rumah lama.
Rumah lama mengaburi rumah lama.
Kayu oak tua mengaburi kayu oak tua.
Ayat-ayat ini dan ayat terbitan tadi adalah semua ayat yang dihasilkan oleh tatabahasa ini.
Set yang terdiri daripada empat ayat ini dipanggil bahasa, yang ditakrifkan oleh tatabahasa tertentu ("dihasilkan olehnya" atau "terdapat di dalamnya").
Salah satu sistem formal ialah sistem penggantian atau semi-sistem Thue (dinamakan sempena ahli matematik Norway Axel Thue), yang ditakrifkan oleh abjad A dan set penggantian terhingga bentuk:
dengan α i,β i ialah perkataan, mungkin kosong dalam A, Þ ialah simbol penggantian, yang sebelum ini difahami oleh kami sebagai "menyiratkan", "disimpulkan".
Sistem Thue menggunakan hubungan dalam bentuk:
difahami sebagai pasangan penggantian:
α i Þ β i (kiri);
β i Üα i (kanan).
Dalam separuh sistem Thue, penggantian α i Þβ i ditafsirkan sebagai peraturan inferens R i . Menggunakan separuh sistem ini, ahli matematik Amerika N. Chomsky pada tahun 50-an membentuk dan mengembangkan teori yang dipanggil tatabahasa formal, yang merupakan kes khas mereka.
Biarkan V menjadi set simbol bukan kosong - abjad (atau kamus) dan, dengan itu, diberikan set V * semua perkataan terhingga dalam abjad V. Bahasa formal L dalam abjad V ialah subset arbitrari bagi V * . Jadi, jika V mengandungi huruf bahasa Rusia, tanda baca, aksara ruang, dll., maka V * adalah set hipotesis yang merangkumi semua karya kesusasteraan Rusia yang hebat (bertulis dan masa depan).
Perkataan, tanda matematik, imej geometri dan sebagainya juga boleh digunakan sebagai simbol.
Bahasa ditentukan atau ditentukan tatabahasa– sistem peraturan yang menjana semua rantaian bahasa tertentu, dan hanya mereka.
Tatabahasa formal – sistem formal, kalkulus.
Terdapat mengiktiraf, menjana dan mengubah tatabahasa formal.
mengenali, jika untuk mana-mana rentetan tertentu ia memutuskan sama ada rentetan itu betul dalam erti kata tatabahasa yang diberikan.
Tatabahasa formal dipanggil generatif, jika ia boleh membina mana-mana rantai yang betul.
Tatabahasa formal dipanggil transformatif jika bagi mana-mana rantai yang dibina dengan betul ia membina pemetaannya dalam bentuk rantai yang betul.
Pertimbangkan kelas tatabahasa formal generatif.
Tatabahasa formal generatif G ialah empat kali ganda
G=
di mana T ialah set terhingga bukan kosong bagi simbol terminal (utama) terhingga;
N – set terhingga bukan kosong bagi simbol bukan terminal (bantuan);
P ialah set peraturan inferens tak terhingga (pengeluaran);
S ialah watak permulaan.
T – kamus terminal – satu set simbol awal dari mana rantai yang dihasilkan oleh tatabahasa dibina;
N – kamus bukan terminal – satu set simbol tambahan yang menunjukkan kelas simbol sumber.
Set terhingga ialah kamus lengkap tatabahasa G.
Peraturan inferens ialah set perhubungan binari tak terhingga yang terhingga dalam bentuk φÞψ, dengan φ dan ψ ialah rantai dalam kamus V, simbol Þ ialah "ganti dengan".
Rantaian β boleh disimpulkan secara langsung daripada rantai α dalam tatabahasa G (notasi αβ; subskrip G ditiadakan jika jelas tatabahasa yang kita maksudkan) jika α=α 1 φα 2 , β=α 1 ψα 2 , (φÞψ ).
Rantaian β boleh disimpulkan daripada α jika terdapat jujukan E 0 =α, E 1 ,E 2 ,…,E n =β, supaya "i =0,1,...,n-1 E i => E i +1.
Urutan ini dipanggil keluaran β daripada α, dan n ialah panjang keluaran.
Penolakan β daripada α dilambangkan dengan α => n β (jika anda perlu menentukan panjang terbitan).
Bahasa L(G) yang dijana oleh tatabahasa G ialah set rentetan dalam kamus terminal T yang diperoleh daripada S, di mana S ialah simbol awal yang menunjukkan kelas objek linguistik yang dimaksudkan tatabahasa ini. Simbol awal dipanggil matlamat tatabahasa atau aksiomnya.
Tatabahasa G dan G 1 adalah setara jika L(G)=L(G 1).
Apabila menerangkan bahasa semula jadi dari segi teori tatabahasa formal, simbol terminal ditafsirkan sebagai perkataan atau morfem - unit bahasa yang paling kecil bermakna (akar, akhiran, dll.), simbol bukan terminal - sebagai nama kelas kata dan frasa (subjek, predikat, kumpulan predikat, dll. .P.). Rentetan aksara biasanya ditafsirkan sebagai ayat bahasa semula jadi.
Contoh 1. Biarkan tatabahasa diberikan seperti berikut:
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).
Kesimpulan biasa cadangan:
Bilangan peraturan inferens yang digunakan ditunjukkan dalam kurungan di atas anak panah. Keluaran berakhir kerana tiada peraturan P dengan sisi kiri sama dengan ab.
Graf tatabahasa generatif sedemikian ditunjukkan dalam Rajah. 125.
nasi. 125. Graf tatabahasa generatif
Di sini a dan b ialah bucu akhir (terminal).
Contoh 2. Biarkan tatabahasa diberikan seperti berikut:
T=(<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};
N=(<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};
Anda boleh mengeluarkan rantai<прилежный> <студент> <выполняет> <домашнее задание>.
Jelas sekali, rantaian kesimpulan terakhir adalah muktamad dan mewakili ayat bahasa semula jadi. Begitu juga, anda boleh memperoleh rantaian<ленивый> <студент> <не выполняет> <домашнее задание>. Perhatikan bahawa dalam contoh ini simbol bukan terminal adalah kategori sintaksis.
Output juga boleh diterangkan oleh pokok struktur yang dipanggil ditunjukkan dalam Rajah. 126.
nasi. 126. Pohon struktur keluaran ayat
Tatabahasa juga boleh ditentukan oleh apa yang dipanggil gambarajah sintaksis Wirth - seperti dalam bahasa Pascal, yang menyerupai litar pensuisan di mana sambungan bersiri menunjukkan rantai, dan sambungan selari menunjukkan varian rantai - bukannya simbol.
Jadi, tatabahasa formal boleh mengenali, menjana, mengubah. Selain itu, dalam teori tatabahasa formal, terdapat empat jenis bahasa yang dihasilkan oleh empat jenis tatabahasa. Tatabahasa dibezakan dengan meletakkan sekatan yang meningkat berturut-turut pada sistem peraturan R.
Klasifikasi tatabahasa yang diterima umum dan bahasa yang dihasilkannya ialah hierarki Chomsky, yang mengandungi empat jenis tatabahasa.
Taip 0 tatabahasa ialah tatabahasa di mana tiada sekatan dikenakan ke atas peraturan inferens jÞy, di mana j dan y boleh menjadi sebarang rentetan daripada V. Tatabahasa sedemikian boleh dilaksanakan oleh mesin Turing. Dalam kes ini, keadaan mesin Turing sepadan dengan simbol bukan terminal (bantuan), dan simbol pada pita sepadan dengan simbol terminal. Peraturan untuk menjana rantai diterangkan oleh sistem arahan.
Jenis tatabahasa 1 ialah tatabahasa, semua peraturannya mempunyai bentuk aАbÞawb, di mana wÎТUN, A ialah simbol bukan terminal. Rantaian a dan b ialah konteks peraturan. Mereka tidak berubah apabila ia digunakan. Oleh itu, dalam tatabahasa jenis 1, simbol terminal tunggal A masuk ke dalam rentetan tidak kosong w (A boleh digantikan dengan w) hanya dalam konteks a dan b. Tatabahasa jenis 1 dipanggil konteks sensitif atau konteks sensitif.
Tatabahasa jenis 2 ialah tatabahasa di mana hanya peraturan dalam bentuk AÞa dibenarkan, di mana aÎТUN, i.e. a ialah rantaian tidak kosong V. Tatabahasa jenis 2 dipanggil tanpa konteks atau tanpa konteks. Bahasa algoritma moden diterangkan menggunakan tatabahasa bebas konteks.
Jenis tatabahasa 3 – mempunyai peraturan dalam bentuk АÞaB, atau AÞb, di mana А,ВОN; sedikit.
Di sini A,B,a,b ialah aksara tunggal (bukan rantai) bagi kamus yang sepadan. Bahasa yang ditakrifkan oleh tatabahasa jenis ini dipanggil automatik atau biasa.
Dalam kes ini, bahasa ungkapan biasa (bahasa biasa) dalam bentuk digunakan:
Bahasa sedemikian diberikan oleh automaton terhingga (teorem Kleene). Dalam kebanyakan bahasa algoritma, ungkapan ditentukan menggunakan mesin keadaan terhingga atau ungkapan biasa.
Mari kita pertimbangkan contoh menentukan bahasa biasa oleh mesin terhingga:
X=(0,1) – set simbol input;
Y=(S,A,B,q k ) – set keadaan dalaman, q k – keadaan akhir, S – keadaan awal.
Kadangkala beberapa keadaan akhir dipertimbangkan dan digabungkan menjadi satu set F. Dalam kes ini, F = (q k ).
j: fungsi peralihan – bukan deterministik:
Graf peralihan bagi automaton tak tentu terhingga ditunjukkan dalam Rajah. 127.
nasi. 127. Graf peralihan bagi automaton bukan penentu terhingga
Tatabahasa generatif yang sepadan ialah:
Bahasa biasa yang sepadan L= 
:
0, 010, 01010,...
Teori tatabahasa formal digunakan dalam pembinaan penyusun. Pengkompil menghuraikan program sumber. Pada masa yang sama, ia ditentukan sama ada rantaian aksara yang diberikan ialah ayat yang dibina dengan betul, dan, jika ya, bentuknya dipulihkan. Penghuraian atau analisis sintaksis dilakukan oleh program khas - penghurai (untuk menghuraikan - menghuraikan). Untuk menyelesaikan masalah ini, program khas telah dibangunkan, contohnya, LEX dan YACC.
Sistem pengendalian UNIX mempunyai program standard LEX dan GREP - ia dibina berdasarkan teori bahasa biasa.
Program LEX menjalankan analisis leksikal teks - memecahkan teks mengikut set ungkapan biasa yang khusus.
Program GREP - memilih corak menggunakan ungkapan biasa - i.e. menjalankan carian kontekstual dalam satu atau lebih fail, sambil membina mesin keadaan terhingga yang mana simbol daripada aliran simbol input disalurkan.
Dalam sistem terjemahan automatik dari satu bahasa ke bahasa lain, subjek, predikat, definisi dan pelengkap dikenal pasti; maka cadangan yang sepadan disediakan mengikut peraturan bahasa yang diperlukan.
Pada masa ini, komputer menggunakan penterjemah seperti Promt, Magic Gooddy, Socrat Personal. Selain itu, kamus mudah digunakan, seperti .Context, Kamus Socrat, MultiLex.
Perwakilan pengetahuan linguistik menggunakan tatabahasa formal adalah salah satu model perwakilan pengetahuan secara umum, digunakan dalam bidang seperti sistem dengan unsur kecerdasan buatan. Perlu diingatkan bahawa pengetahuan berbeza daripada data, contohnya, dalam data itu ditafsirkan secara bermakna hanya oleh program komputer yang sepadan, dan dalam pengetahuan kemungkinan tafsiran bermakna sentiasa ada. Bahagian perisian dan perkakasan sistem yang menyediakan antara muka dengan pengguna dalam bahasa semula jadi atau hampir dengan bahasa semula jadi dilaksanakan pemproses linguistik, yang tugasnya ialah terjemahan langsung dan terbalik teks bahasa semula jadi ke dalam bahasa formal perwakilan dalaman yang digunakan oleh komputer.
Di Jepun, beberapa syarikat telah mula menjual robot "bercakap" isi rumah yang boleh berkomunikasi dengan pemiliknya.
Pemproses linguistik mempunyai bahagian deklaratif dan prosedur. Yang pertama mengandungi penerangan tentang kamus, yang kedua - algoritma untuk analisis dan sintesis teks bahasa semula jadi.
Model logik untuk perwakilan pengetahuan sudah diketahui oleh kita kalkulus proposisi dan predikat.
Asas untuk pemformalan pengetahuan semantik (nosional) tentang bidang subjek tertentu adalah rangkaian semantik yang dipanggil. Rangkaian semantik ialah graf terarah, bucunya dikaitkan dengan objek tertentu, dan lengkok dikaitkan dengan hubungan semantik di antara mereka. Label vertex bersifat rujukan dan mewakili nama tertentu. Peranan nama boleh, sebagai contoh, perkataan bahasa semula jadi. Label arka menandakan unsur-unsur set hubungan. Selain itu, bingkai digunakan untuk mewakili pengetahuan, yang paling kerap ditakrifkan sebagai struktur data untuk mewakili situasi stereotaip.
Teorem Gödel
Dalam logik matematik terbukti bahawa kalkulus predikat adalah konsisten - i.e. adalah mustahil untuk memaparkan secara serentak , dan . Di samping itu, berdasarkan teorem Gödel mengenai kesempurnaan kalkulus predikat, formula yang sah secara amnya boleh disimpulkan dalam kalkulus predikat.
Kalkulus predikat yang dipertimbangkan ialah kalkulus predikat peringkat pertama. Dalam kalkulus tertib kedua, pengkuantiti mengikut predikat adalah mungkin, i.e. ungkapan dalam bentuk "P(P(x)), atau mengikut fungsi.
Jadi, set semua pernyataan logik proposisi yang benar boleh dikira dan boleh diputuskan. Set semua pernyataan benar bagi logik predikat boleh dikira (disebabkan kesempurnaannya), tetapi tidak dapat diputuskan (disebabkan ketakterhinggaan kawasan subjek).
Sebagai satu lagi teori formal dalam logik matematik, apa yang dipanggil aritmetik formal yang dicadangkan oleh ahli matematik Itali Giuseppe Peano (1858-1932) dipertimbangkan. Peano memperkenalkan simbol dan operasi O, U, I dan merupakan yang pertama membentangkan logik sebagai disiplin matematik. Percubaan pertama untuk mengurangkan matematik kepada logik telah dibuat oleh ahli matematik dan logik Jerman Gottlieb Frege (1848-1925). Dialah yang mendefinisikan set sebagai isipadu konsep. Dia menulis: "Aritmetik adalah sebahagian daripada logik dan tidak boleh meminjam daripada pengalaman atau perenungan mana-mana asas pembuktian." Paradoks terkenal tentang set semua set adalah percanggahan dalam sistem Frege yang dikenal pasti oleh Bertrand Russell.
Gödel membuktikan bahawa mana-mana teori formal T yang mengandungi aritmetik formal adalah tidak lengkap: ia mengandungi formula tertutup F sedemikian yang benar, tetapi F mahupun boleh terbitan dalam T. Menurut teorem ketidaklengkapan Gödel yang terkenal, bagi mana-mana teori formal yang konsisten T yang mengandungi aritmetik formal, formula yang menyatakan ketekalan T tidak dapat dibuktikan dalam T.
Oleh itu, teori aritmetik dan nombor adalah teori yang tidak boleh diaksimasi, dan set semua pernyataan sebenar aritmetik tidak boleh dikira.
Teorem Gödel mempunyai kepentingan metodologi yang penting. Ternyata untuk teori matematik yang cukup kaya tidak ada pemformalisasi yang mencukupi. Benar, mana-mana teori T yang tidak lengkap boleh dikembangkan dengan menambahkannya sebagai aksiom formula yang benar tetapi tidak boleh diterbitkan dalam T walau bagaimanapun, teori baharu itu juga tidak lengkap. Di samping itu, adalah mustahil untuk mengkaji sifat meta teori menggunakan cara teori formal itu sendiri, i.e. mana-mana metateori T, untuk dapat membuktikan sekurang-kurangnya konsistensi, mestilah lebih kaya daripada T.
Oleh itu, pendekatan membina matematik sebagai satu set cara tetap tertentu yang boleh diisytiharkan sebagai satu-satunya cara yang sah dan dengan bantuan mereka untuk membina metateori mana-mana teori dipersoalkan. Tetapi ini sama sekali bukan keruntuhan pendekatan formal. Kehadiran masalah yang tidak dapat diselesaikan tidak bermakna pendekatan yang membina tidak sesuai jika ia tidak dapat melakukan sesuatu, ia hanya kerana tiada siapa yang boleh melakukannya.
Kemustahilan untuk memformalkan sepenuhnya teori yang ditakrifkan secara substantif bukanlah kekurangan konsep, tetapi fakta objektif yang tidak boleh dihapuskan oleh mana-mana konsep.
Kemustahilan untuk memformalkan teori yang mencukupi bermakna seseorang mesti mencari serpihan yang boleh diformalkan daripadanya, atau membina teori formal yang lebih kuat, yang, bagaimanapun, sekali lagi tidak lengkap, tetapi, mungkin, akan mengandungi keseluruhan teori asal.
LOGIK BUKAN KLASIK
PENGENALAN………………………………………………………………….4
Bab 1. BAHASA DAN TATABAHASA. SIMBOL, DEFINISI DAN KLASIFIKASI………………………………………………………………………………6
1.1. Konsep tatabahasa bahasa. Jawatan……………………………………………………7
1.2. Klasifikasi tatabahasa mengikut Chomsky………………………..…………………………13
1.3. Teknik membina tatabahasa KS- dan A………………………………………………………………..16
1.4. Pokok inferens sintaksis dalam tatabahasa KS. Prestasi
A-tatabahasa dalam bentuk graf keadaan. Kekaburan tatabahasa………..19
1.5. Analisis sintaksis bahasa-A…………………………………………………………..23
Latihan……………………………………………………………………………….29
Bab 2. PENGIKTIRAF DAN MESIN.……………………………….….…………32
Bab 3. TATABAHASA AUTOMATIN DAN MESIN TERHAD…………….35
3.1. Tatabahasa automatik dan automata terhingga………………………………………….35
3.2.Persamaan tatabahasa A bukan deterministik dan deterministik...... 36
Latihan……………………………………………………………………………… 41
Bab 4. TRANSFORMASI BEBAS KONTEKS SETARAF
DAN TATABAHASA AUTOMATIK………………………………………………..….42
4.2. Menghapuskan peraturan buntu daripada tatabahasa…………………………………………46
4.3. Tatabahasa KS umum dan pengurangan tatabahasa kepada bentuk memanjang…….48
4.4. Penghapusan rekursi kiri dan pemfaktoran kiri…………………………………..…52
Latihan……………………………………………………………………………….53
Bab 5. SIFAT-SIFAT BAHASA AUTOMATIK DAN BEBAS KONTEKS…55
5.1. Pandangan umum rantaian bahasa A dan bahasa KS………………………………………………………………..55
5.2. Operasi pada bahasa……………………………………………………………….59
5.2.1. Operasi pada bahasa CS………………………………………………………………59
5.2.2. Operasi pada bahasa-A………………………………………………………………62
5.2.3. Operasi pada bahasa K………………………………………………………………66
5.3. Kesimpulan untuk latihan……………………………………………………………………………….67
5.4. Kekaburan KS-tatabahasa dan bahasa………………………………………………………………71
Latihan……………………………………………………………………………………74
Bab 6. ANALISIS SINTATIK bahasa CS……………………………...……...75
6.1. Kaedah untuk menganalisis bahasa CS. Keutamaan tatabahasa………………….75
6.2. Tatabahasa keutamaan Wirth…………………………………………………………………………77
Tatabahasa keutamaan Floyd…….………………………………………………………………79
Fungsi keutamaan………………………………………………………81
Latihan………………………………………………………………………………84
Bab 7. PENGENALAN KEPADA SEMANTIK……………………………………………………….85
7.1. Notasi songsang Poland….………………………………………………………………85
7.2. Tafsiran POLIZ………………………………………………………………………..87
7.3. Menjana arahan untuk POLIZ……………………………………………………...89
7.4. Algoritma Zamelson dan Bauer untuk menterjemah ungkapan ke dalam POLIZ………..……….91
7.5. Tatabahasa atribut……………………………………………………………………………………97
Latihan………………………………………………………………………………..100
Bab 8. FASA UTAMA PENYUSUNAN……………………………………...……100
KESIMPULAN
PERMOHONAN…………………………………………………………………………………105
INDEKS PERKARA……………………………………………………….…….…115
pengenalan
Linguistik- ilmu bahasa. Linguistik matematik- sains yang berkaitan dengan kaedah formal membina dan mempelajari bahasa.
Teori tatabahasa formal- bahagian linguistik matematik, termasuk kaedah untuk menerangkan tatabahasa formal bahasa, membina kaedah dan algoritma untuk menganalisis kepunyaan rantai kepada bahasa, serta algoritma untuk menterjemah bahasa algoritma ke dalam bahasa mesin.
Dorongan untuk penciptaan dan penambahbaikan teori ini adalah pembangunan teknologi komputer dan, sebagai akibatnya, keperluan untuk cara komunikasi antara seseorang dan komputer. Dalam semua aplikasi, komputer mesti memahami beberapa bahasa di mana pengguna boleh berkomunikasi dengannya algoritma untuk menyelesaikan masalah dan data awal. Setiap komputer mempunyai bahasa arahan mesinnya sendiri, diwakili dalam kod binari dan mencerminkan operasi pemproses individu. Pada peringkat pertama perkembangan teknologi komputer, pengaturcara berkomunikasi dengan komputer dalam bahasa primitif ini, tetapi manusia tidak dapat berfikir dengan baik dari segi bahasa digital mesin. Automasi pengaturcaraan membawa kepada penciptaan pertama bahasa himpunan, dan kemudian bahasa algoritmik peringkat tinggi, terjemahan daripadanya ke dalam bahasa mesin ibunda diamanahkan kepada komputer itu sendiri. Program terjemahan sedemikian dipanggil penyiar.
Banyak pembangun perisian menghadapi masalah menerangkan bahasa kepada mesin. Sudah menjadi fitrah manusia untuk mencipta bahasa baru. Di sini kita bercakap bukan sahaja tentang penyusun kompleks untuk bahasa pengaturcaraan algoritmik baharu. Mana-mana sistem automatik mesti memahami beberapa bahasa pertanyaan input. Teknologi maklumat baharu melibatkan penglibatan pengguna akhir (saintis, pereka bentuk, ahli teknologi, pengendali) - pakar dalam bidang tertentu, dan bukan dalam bidang teknologi komputer dan teknologi pengaturcaraan, dalam menyelesaikan masalah mereka pada komputer. Untuk penyelesaian yang berkualiti tinggi untuk masalah ini, antara muka pintar mesti wujud antara pengguna dan komputer: pengguna mesti menimbulkan masalah dan mendapatkan keputusan penyelesaian mereka dari segi kawasan subjek yang diketahuinya. Iaitu, adalah perlu untuk membangunkan pelbagai bahasa khusus domain. Pakar perisian mesti tahu cara bahasa dicipta dan sokongan perisian mereka.
Untuk menerangkan bahasa kepada mesin, kita perlu mempunyai pemahaman yang jelas tentang cara ia berfungsi dan cara kita memahaminya. Bila difikirkan, kita nampak tak tahu macam mana kita faham bahasa ibunda. Proses pemahaman ini adalah bawah sedar dan intuitif. Tetapi untuk mencipta penterjemah, adalah perlu untuk mempunyai algoritma untuk menterjemah teks ke dalam tindakan yang diperlukan oleh teks ini untuk dilakukan, dan ini, seterusnya, memerlukan pemformalan bahasa. Masalah pemformalan bahasa diselesaikan dengan linguistik matematik. Bahasa semula jadi terlalu kompleks dan masih belum dapat diformalkan sepenuhnya. Bahasa-bahasa algoritma, sebaliknya, telah dibuat dengan mengambil kira pemformalkan. Teori bahasa formal adalah cabang linguistik matematik yang paling maju, yang pada dasarnya mewakili teknik untuk menerangkan bahasa kepada mesin. Sebelum melihat definisi, model dan kaedah teori ini, mari kita lihat beberapa konsep menggunakan contoh daripada bahasa semula jadi.
Bahasa- satu set ayat (frasa) yang dibina mengikut peraturan tertentu.
Tatabahasa- satu set peraturan yang menentukan sama ada frasa tergolong dalam bahasa.
Mana-mana bahasa mesti memenuhi sifat-sifat kebolehtetapan dan tidak jelas.
Bahasa boleh diselesaikan, jika dalam masa yang terhad adalah mungkin untuk menentukan bahawa frasa atau ayat kepunyaan bahasa. Bahasanya tidak jelas, jika mana-mana frasa difahami dengan cara yang unik.
Bahagian utama tatabahasa ialah sintaksis dan semantik.
Sintaks- satu set peraturan yang menentukan pembinaan ayat yang betul dalam sesuatu bahasa.
Semantik- satu set peraturan yang menentukan ketepatan semantik atau semantik ayat dalam sesuatu bahasa.
Satu ayat boleh betul dari segi sintaksis dan salah secara semantik.
Sintaks biasanya dipermudahkan oleh fakta bahawa tidak semua frasa dalam bahasa perlu masuk akal. Selalunya sukar untuk memahami maksud futuris atau ucapan sesetengah ahli politik. Dalam hal ini, contoh ahli akademik L.V Shcherba adalah menarik: "Glokka kuzdra shteko telah membotakkan bokr dan menggulung bokrenka." Ini adalah frasa dalam bahasa Rusia, kerana ia boleh dihuraikan oleh ahli ayat, tetapi maknanya tidak jelas.
Analisis sintaksis sesuatu frasa boleh ditulis dalam bentuk pokok penghuraian. Nod pokok, seperti subjek, predikat, kumpulan subjek, ayat sesuai dengan konsep sintaksis, dan daun adalah perkataan dari mana ayat itu dibina. Dengan memotong beberapa daun dan dahan dalam pokok, kita memperoleh bentuk ayat (rantai yang boleh disimpulkan).
<предложение>
Sifat kekaburan frasa itu boleh dijelaskan menggunakan contoh pokok penghuraian yang sama untuk frasa "Ibu sayangkan anak perempuannya."
Frasa ini tidak jelas kerana ia mempunyai dua pilihan penghuraian. Kekaburan sintaksis secara langsung melibatkan kekaburan semantik. Tetapi anda juga boleh menawarkan contoh frasa yang tidak jelas secara sintaksis yang mungkin tidak difahami disebabkan oleh maksud perkataan yang samar-samar. Mari kita ingat bahawa bahasa algoritma mestilah jelas.
Bahasa formal ialah abstraksi matematik yang timbul sebagai generalisasi konsep linguistik biasa dalam bahasa semula jadi. Teori bahasa formal mengkaji terutamanya sintaks bahasa dan merupakan asas kepada proses terjemahan yang dikawal secara sintaksis, yang merangkumi terjemahan, perhimpunan dan penyusunan. Asas teori ini telah diletakkan oleh ahli matematik Amerika N. Chomsky pada akhir 50-an dan awal 60-an dan terus berkembang hingga ke hari ini seiring dengan perkembangan teknologi komputer. Marilah kita memikirkan unsur-unsur utama teori ini.