Desain kompiler, algoritma untuk memecahkan masalah. Ekspresi reguler dari dalam

Definisi dasar Ekspresi Reguler dalam alfabet, Σ dan himpunan reguler yang dilambangkannya didefinisikan secara rekursif sebagai berikut: 1) – ekspresi reguler yang menunjukkan himpunan reguler; 2) e – ekspresi reguler yang menunjukkan himpunan reguler (e); 3) jika a , maka a adalah ekspresi reguler yang menyatakan himpunan reguler (a); 4) jika p dan q adalah ekspresi reguler yang menyatakan himpunan reguler P dan Q, maka a) (p+q) adalah ekspresi reguler yang menyatakan P Q; b) pq – ekspresi reguler yang menunjukkan PQ; c) p* – ekspresi reguler yang menunjukkan P*; 5) tidak ada yang lain yang merupakan ekspresi reguler.

Definisi dasar Prioritas: * (iterasi) – prioritas tertinggi; rangkaian; + (persatuan). Jadi 0 + 10* = (0 + (1 (0*))). Contoh: 1. 01 artinya (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – berarti himpunan semua rantai yang terdiri dari 0 dan 1 dan diakhiri dengan rantai 011; 5. (a+b) (a+b+0+1)* berarti himpunan semua rantai (0, 1, a, b)* yang dimulai dengan a atau b.

Definisi dasar Lemma: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α

Hubungan antara RT dan RM RM adalah bahasa yang dihasilkan oleh RT. Contoh: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Penggabungan: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (paus, kucing) atau menurut Lemmas No. 5 dan No. 6 k(u+o)t = paus + kucing (paus, kucing) . Iterasi: x = a, x* X* = (e, a, aaa, …), yaitu x* = e + xxx + …

Hubungan antara RP dan RM Iterasi penggabungan dan penyatuan: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Contoh: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). Penyatuan bersifat komutatif: x + y = y + x Penggabungan tidak: xy ≠ yx

Komunikasi antara RM dan RM Contoh prioritas: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, ...), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …). Lemma baru: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; dll.

Sistem persamaan beraturan Persamaan dengan koefisien beraturan X = a. X + b mempunyai penyelesaian (titik tetap terkecil) a*b: aa*b + b = (aa* + e)b = a*b Sistem persamaan dengan koefisien reguler: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2 n. Xn……………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Tidak Diketahui – Δ = (X 1, X 2, …, Xn).

Sistem persamaan reguler Algoritma penyelesaian (metode Gauss): Langkah 1. Himpunan i = 1. Langkah 2. Jika i = n, lanjutkan ke langkah 4. Jika tidak, tulis persamaan Xi dalam bentuk Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn.Xn). Kemudian, di ruas kanan persamaan Xi+1, ..., Xn, kita ganti Xi dengan persamaan reguler α*β. Langkah 3. Naikkan i sebanyak 1 dan kembali ke langkah 2. Langkah 4. Tulis persamaan Xn sebagai Xn = αXn + β. Lanjutkan ke langkah 5 (dengan i = n). Langkah 5. Persamaan Xi adalah Xi = αXi + β. Tuliskan pada keluaran Xi = α*β, dalam persamaan Xi– 1, …, X 1, substitusikan α*β sebagai ganti Xi. Langkah 6. Jika i = 1, hentikan, jika tidak, kurangi i sebanyak 1 dan kembali ke langkah 5.

Transformasi DFA menjadi RT Untuk DFA M = (Q, Σ, δ, q 0, F) kita buat sistem dengan koefisien reguler dimana Δ = Q: 1. himpunan αij: = ; 2. jika δ(Xi, a) = Xj, a Σ, maka αij: = αij + a; 3. jika Xi F atau δ(Xi,) = HALT, maka αi 0: = e. Setelah diselesaikan, PV yang diinginkan adalah X 1 = q 0.

Konversi DFA ke RV Contoh : untuk bilangan s titik pasti kita memperoleh sistem q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Di sini: s – tanda bilangan, s = "+" + "–"; p – koma desimal, p = "."; d – angka, d = “0” + “1” + … + “9”.

Konversi DFA ke RT Solusi: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q ​​​​2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Dari persamaan ketiga: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Dari persamaan keempat: q 4 = dq 4 + e = d*.

Konversi DFA ke RT Pukulan terbalik: q 3 = d*(pq 4 + e) ​​​​= d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd * + dd *(pd* + e), q 0 = kuadrat 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Jadi, DFA ini sesuai dengan RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Mari kita sederhanakan: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) ​​​​= = spdd* + sdd*(pd* + e) ​​​​+ pdd* + dd*(pd* + e) ​​= (s + e)(pdd* + dd*(pd* + e)) Untuk notasi yang lebih pendek, Anda dapat menggunakan iterasi positif aa* = a*a = a+: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)

Konversi DFA ke RT Memetakan grafik fungsi transisi DFA ke operasi dasar dengan ekspresi reguler: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*

Mengonversi DFA ke RT Kombinasi operasi yang lebih kompleks: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*

Konversi DFA ke RT Untuk RT (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d

Pemrograman RV Ekspresi reguler: Dibangun dalam banyak bahasa pemrograman (PHP, Java. Script, ...); Diimplementasikan sebagai komponen plug-in (misalnya, kelas Regex untuk platform .NET). Perbedaan bentuk notasi: x? = x + e x(1, 3) = x + xxx, dst.

Pemrograman RT Konstruksi kelas Regex (Sistem. Teks. Reguler. Ekspresi): Interpretasi Simbol dari rangkaian Escape b Jika digunakan dalam tanda kurung siku, ini sesuai dengan simbol “←” (u 0008) t, r, n, a, f, v Tab (u 0009), pengangkutan kembali (u 000 D), baris baru (u 000 A), dll. c. X Karakter kontrol (misalnya c. C adalah Ctrl+C, u 0003) e Escape (u 001 B) ooo Karakter ASCII dalam oktal xhh Karakter ASCII dalam heksadesimal uhhhh Karakter Unicode Karakter berikut ini bukan karakter RT khusus. Simbol ini harus digunakan untuk keluar dari semua karakter khusus. Contoh (contoh menunjukkan pola dan string pencarian, kecocokan yang ditemukan digarisbawahi dalam string): @"rnw+" – "rn. Ada dua baris di sini."

Pemrograman RV Subset simbol. Karakter apa pun kecuali akhir baris (n) Karakter apa pun dari himpunan [^xxx] Karakter apa pun kecuali karakter dari himpunan Karakter apa pun dari rentang ] Mengurangi satu himpunan atau rentang dari yang lain p(nama) Karakter apa pun yang ditentukan oleh Unicode kategori bernama nama P (nama) Setiap karakter selain yang ditentukan oleh nama kategori Unicode w Himpunan karakter yang digunakan dalam menentukan pengidentifikasi W Himpunan karakter yang tidak digunakan dalam menentukan pengidentifikasi s Spasi S Semua kecuali spasi d Angka D Non-digit Contoh : @".+" – "rn. Ada ndua baris"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "Lampu Kota"; // Lu – huruf kapital @"P(Lu)" – "Kota"; @"p(Is. Sirilik)" – "ha.OS"; //Adalah. Sirilik – huruf Rusia

Pemrograman PB Anchor ^,A Di awal baris $, Z Di akhir baris atau sebelum karakter "n" di akhir baris z Di akhir baris G Dimana kecocokan sebelumnya berakhir b Batas kata B Posisi apa pun yang tidak berada pada batas kata Contoh: @ "G(d)" – "(1)(3)(5)(9)"; // tiga pertandingan (1), (2) dan (3) @"bnS*ionb" – "donasi negara"; @"Bendw*b" – "akhir mengirimkan pemberi pinjaman yang bertahan".

Pemrograman Operasi RT (quantifier) ​​*, *? Iterasi +, +? Iterasi positif? , ? ? Nol atau satu kecocokan (n), (n)? Tepatnya n cocok dengan (n, ), (n, )? Setidaknya n kecocokan (n, m), (n, m)? Dari n ke m yang cocok Contoh (penghitung pertama serakah, mencari elemen sebanyak mungkin, pembilang kedua malas, mencari elemen sesedikit mungkin): @"d(3, )" – "888 -5555 "; @"^d(3)" – "913 -913"; @"-d(3)$" – "913 -913"; @"5+?5" – "888 -5555"; // tiga pertandingan - 55, 55 dan 55 @"5+5" - "888 -5555".

Pemrograman RV Pengelompokan () Grup yang secara otomatis menerima nomor (? :) Jangan simpan grup (?) atau (? "nama") Jika ditemukan kecocokan, grup bernama akan dibuat (?) atau Hapus grup yang telah ditentukan sebelumnya grup dan (? "nama - nama") menyimpan dalam grup baru substring antara grup yang ditentukan sebelumnya dan grup baru (? imnsx:) Mengaktifkan atau menonaktifkan salah satu dari lima (? –imnsx:) opsi yang memungkinkan dalam grup: i – tidak peka huruf besar-kecil; s – satu baris (maka “.” adalah karakter apa saja); m – mode multi-baris (“^”, “$” – awal dan akhir setiap baris); n – jangan menangkap kelompok yang tidak disebutkan namanya; x – mengecualikan spasi yang tidak lolos dari pola dan menyertakan komentar setelah tanda angka (#) (? =) Pernyataan pandangan ke depan positif yang panjangnya nol

Pemrograman RT (? !) Pernyataan lookahead dengan panjang nol negatif (?) Bagian ekspresi yang tidak dapat dikembalikan (serakah) Contoh: @"(an)+" – "bananas annals"; @"an+" – "annals pisang"; // bandingkan, tiga kecocokan - an, an dan ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – " abc xyz 12 555 w"; @"(?

Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV Pemrograman Nomor Tautan Tautan ke grup k Tautan ke grup bernama Contoh: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}

Pemrograman RV Substitusi $number Mengganti bagian dari string yang sesuai dengan grup dengan nomor yang ditentukan $(nama) Mengganti bagian dari string yang sesuai dengan grup dengan nama yang ditentukan $$ Mengganti $ $& Mengganti dengan salinan lengkap cocokkan $` Menggantikan teks dari string masukan hingga cocok $" Menggantikan teks dari baris masukan setelah cocok $+ Ganti grup yang terakhir diambil $_ Ganti seluruh baris Komentar (? #) Komentar sebaris # Komentar di akhir baris

Pemrograman Hasil RT dari Regex: Regex Matches() Cocok. Grup Pencocokan Koleksi() Grup. Tangkapan Grup Koleksi() Tangkapan. Tangkapan Koleksi()

Contoh Pemrograman RV di C++ CLI (Aplikasi Konsol Visual C++/CLR/CLR): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Cocok ^m = r-> Cocok (L"123 456"); int match.Count = 0; while (m->Success) ( Console: : Write.Line(L"Match (0)", ++match.Count); for (int i = 1; i Grup->Hitung; i++) ( Grup ^g = m->Grup[i]; Konsol: : Tulis. Baris(L" Grup (0) = "(1)"", i, g-> Nilai ); for (int j = 0; j Captures->Count; j++) ( Capture ^c = g->Captures[j]; Console: : Write.Line(L" Capture (0) = "(1)" , posisi = (2), panjang = (3)", j, c, c->Indeks, c->Panjang); ) ) m = m->Berikutnya. Cocok(); ) kembali 0; ) Sistem: : Teks : : Reguler. Ekspresi

Mengaktifkan tindakan dan menemukan kesalahan Membatasi jumlahnya sosok penting dalam bilangan: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (.d+|d+(.d*)?)" atau @"^(+|-)? (.d+|d+(.d*)?)$" Regex r = Regex baru (@"^(+|-)? (. (? "digit"d)+|(? "digit"d)+(.(? "digit"d)*)?)$"); Cocokkan m = r. Cocok("+1.23456789"); if (m. Sukses) ( Grup g = m. Grup["digit"]; if (g. Tangkapan. Hitung

Mengaktifkan tindakan dan menemukan kesalahan Menentukan posisi kesalahan: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(.(? "digit" D )*)?)"); string str = "+1.2345!678"; Cocokkan m = r. Cocok(str); if (m. Sukses) ( Grup g = m. Grup["digit"]; if (g. Menangkap. Hitung 0) Konsol. Tulis. Baris("Kesalahan pada posisi 1: karakter tak terduga "(0)"", str ); else if (m. Panjang

Mengaktifkan tindakan dan mencari kesalahan Menentukan posisi kesalahan: 1. posisi pertama rantai masukan (1), jika kecocokan pertama tidak dimulai dari posisi Indeks = 0; 2. posisi setelah kecocokan terakhir (panjang kecocokan + 1), jika tidak cocok dengan posisi terakhir rantai masukan; 3. posisi jarak pertama antar kecocokan (match[i]. Index + match[i]. Panjang + 1), jika karakter yang mengikuti match sebelumnya bukan karakter pertama pada match berikutnya.

Indeks) istirahat; indeks = m[i]. Indeks + m[i]. Panjang; ) Konsol. Menulis. Line("Kesalahan pada posisi (0)"(1)"",indeks+1,str); ) "abc. xyz. pqr" – benar; "+abc. xyz. pqr” – kesalahan pada posisi 1 (“+”); "abc. xyz. pqr! – kesalahan pada posisi 12 (“!”); "abc. xyz!. pqr" – kesalahan pada posisi 8 (“!”).

Mengaktifkan tindakan dan mencari kesalahan Tapi! "abc. xyz. +pqr” – kesalahan pada posisi 8 (“.”). Pilihan baru templat: @"w+(.w+)*(.(? !$))?" Validasi: "abc. xyz. +pqr” – kesalahan pada posisi 9 (“+”); "abc. xyz. pqr. " – kesalahan pada posisi 12 (".").

Definisi Seimbang: "(? "x")" menambahkan satu elemen ke koleksi bernama "x"; “(? “-x”)” menghapus satu elemen dari koleksi “x”; "(? (x)(? !))" memeriksa apakah tidak ada elemen tersisa di koleksi "x". Bahasa L yang menggambarkan operator bersarang Pascal “mulai akhir; ": @"^s*((? "mulai+)+(? "-mulai"berakhir*; s*)+)*(? (mulai)(? !))$".

Mari kita pertimbangkan algoritme untuk membuat otomat terbatas non-deterministik menggunakan ekspresi reguler yang menerima bahasa yang sama.

Algoritma 3.1. Konstruksi robot terbatas non-deterministik menggunakan ekspresi reguler.

Pintu masuk. Ekspresi reguler r dalam alfabet T.

KELUAR. NKA M sedemikian rupa sehingga L(M) = L(r) .

metode.Otomat untuk suatu ekspresi dibangun oleh komposisi automata yang sesuai dengan subekspresi. Pada setiap langkah konstruksi, otomat yang sedang dibangun mempunyai tepat satu keadaan akhir; tidak ada transisi ke keadaan awal dari keadaan lain dan tidak ada transisi dari keadaan akhir ke keadaan lain.

Konstruksi otomat terbatas deterministik dari otomat non-deterministik

Mari kita pertimbangkan algoritma untuk membangun, dari otomat terbatas nondeterministik, otomat terbatas deterministik yang menerima bahasa yang sama.

Algoritma 3.2. Konstruksi otomat terbatas deterministik dari otomat non-deterministik.

Pintu masuk. NKA M = (Q, T, D, q 0 , F) .

KELUAR. DKA.

metode. Setiap status DFA yang dihasilkan adalah kumpulan status tertentu dari NFA asli.

Fungsi-fungsi berikut akan digunakan dalam algoritma: - himpunan keadaan NKA, yang dapat dijangkau dari keadaan-keadaan yang termasuk dalam R, hanya melalui transisi sepanjang e, yaitu himpunan

Himpunan keadaan NFA yang mengalami transisi pada masukan a untuk keadaan dari R, yaitu himpunan

Pada awalnya, Q" dan D" kosong. Ikuti langkah 1-4:

(1) Tentukan.

(2) Tambahkan ke Q" sebagai status tidak diberi tag

(3) Lakukan prosedur berikut:

(4) Tentukan.

Contoh 3.6. Hasil penerapan algoritma 3.2 ditunjukkan pada Gambar. 3.10.

Beras. 3.10.

Membangun mesin keadaan terbatas deterministik menggunakan ekspresi reguler

Sekarang mari kita sajikan algoritma untuk membangun otomat terbatas deterministik menggunakan ekspresi reguler yang menerima bahasa yang sama [?].

Biarkan ekspresi reguler r diberikan dalam alfabet T. Tambahkan penanda akhir ke ekspresi reguler r: (r)# . Kami akan menyebut ekspresi reguler tersebut selesai. Selama operasinya, algoritma akan menggunakan ekspresi reguler yang lengkap.

Algoritme akan beroperasi pada pohon sintaksis untuk ekspresi reguler (r)# yang telah selesai, yang setiap daunnya ditandai dengan simbol , dan masing-masing simpul bagian dalam ditandai dengan salah satu operasi: (penggabungan), | (penyatuan), * (iterasi).

Kita memberi nomor unik pada setiap daun pohon (kecuali daun e), yang disebut posisi, dan menggunakannya, di satu sisi, untuk merujuk ke daun di pohon, dan, di sisi lain, untuk merujuk ke daun tersebut. simbol yang sesuai dengan daun ini. Perhatikan bahwa jika karakter digunakan beberapa kali dalam ekspresi reguler, karakter tersebut memiliki beberapa posisi.

Mari kita melintasi pohon T dari bawah ke atas dari kiri ke kanan dan menghitung empat fungsi: nullable, firstpos, lastpos, dan followpos. Tiga fungsi pertama - nullable, firstpos dan lastpos - didefinisikan pada node pohon, dan followpos - pada serangkaian posisi. Nilai semua fungsi kecuali nullable adalah sekumpulan posisi. Fungsi followpos dihitung melalui tiga fungsi lainnya.

Fungsi firstpos(n), untuk setiap node n dari pohon sintaksis ekspresi reguler, memberikan himpunan posisi yang sesuai dengan karakter pertama dalam substring yang dihasilkan oleh subekspresi yang berada di puncak n. Demikian pula, lastpos(n) memberikan himpunan posisi yang sesuai dengan karakter terakhir di

Pada bagian ini, kami akan merumuskan isu-isu penting terkait bahasa reguler. Pertama, Anda perlu memahami apa artinya mengajukan pertanyaan tentang bahasa tertentu. Bahasa pada umumnya tidak terbatas, jadi tidak masuk akal untuk menyajikan string bahasa tersebut kepada seseorang dan mengajukan pertanyaan yang memerlukan pengujian string dalam jumlah tak terbatas. Jauh lebih masuk akal untuk menggunakan salah satu representasi bahasa yang terbatas, yaitu: DFA, NFA, ε-NFA atau ekspresi reguler.

Jelas sekali, bahasa yang direpresentasikan dengan cara ini akan menjadi bahasa biasa. Benar-benar tidak ada cara untuk merepresentasikan bahasa yang sepenuhnya arbitrer. Bab-bab berikut mengusulkan metode terbatas untuk mendeskripsikan kelas yang lebih luas daripada kelas bahasa biasa, dan dari sana dimungkinkan untuk mempertimbangkan pertanyaan tentang bahasa. Namun, algoritma untuk menyelesaikan banyak pertanyaan tentang bahasa hanya ada untuk kelas bahasa biasa. Pertanyaan-pertanyaan yang sama menjadi “tidak dapat diputuskan” (tidak ada algoritma untuk menjawab pertanyaan-pertanyaan ini) jika pertanyaan-pertanyaan tersebut diajukan menggunakan notasi yang lebih “ekspresif” (digunakan untuk mengekspresikan variasi bahasa yang lebih luas) dibandingkan representasi yang dikembangkan untuk bahasa biasa.

Mari kita mulai mempelajari algoritme untuk pertanyaan tentang bahasa biasa dengan melihat cara satu representasi bahasa diubah ke bahasa lain. Secara khusus, mari kita pertimbangkan kompleksitas waktu dari algoritma yang melakukan transformasi. Kemudian kita akan melihat tiga pertanyaan dasar tentang bahasa.

1. Apakah bahasa yang dideskripsikan merupakan himpunan kosong?

2. Apakah beberapa string w termasuk dalam bahasa yang diwakili?

3. Apakah dua deskripsi berbeda benar-benar mewakili bahasa yang sama? (Masalah ini sering disebut “kesetaraan” bahasa.)

2.1 Konversi antara representasi bahasa yang berbeda

Masing-masing dari empat representasi bahasa reguler dapat dikonversi ke salah satu dari tiga representasi lainnya. Pada Gambar. 3.1 menunjukkan transisi dari satu representasi ke representasi lainnya. Meskipun ada algoritma untuk transformasi ini, terkadang kita tertarik tidak hanya pada kelayakan transformasi tertentu, tetapi juga pada waktu yang dibutuhkan untuk menyelesaikannya. Secara khusus, penting untuk membedakan algoritme yang memerlukan waktu eksponensial (waktu sebagai fungsi dari ukuran data masukan) dan oleh karena itu hanya dapat dieksekusi untuk data masukan berukuran relatif kecil, dari algoritme yang waktu eksekusinya linier, kuadratik. , atau derajat polinomial rendah sebagai fungsi dari ukuran data masukan. Algoritme yang terakhir ini “realistis” karena dapat dieksekusi untuk kelas contoh masalah yang lebih luas. Mari kita lihat kompleksitas waktu dari setiap transformasi yang dibahas.

Konversi NKA ke DKA

Waktu eksekusi untuk mengubah NFA atau ε-NFA menjadi DFA dapat berupa fungsi eksponensial dari jumlah status NFA. Untuk memulainya, menghitung penutupan ε dari n keadaan memerlukan waktu O(n3). Hal ini diperlukan untuk menemukan semua busur dengan label ε yang mengarah dari masing-masing n negara bagian. Jika terdapat n negara bagian, maka paling banyak terdapat n2 busur. Penggunaan yang wajar sumber daya sistem dan struktur data yang dirancang dengan baik memastikan bahwa waktu untuk menjelajahi setiap negara bagian tidak melebihi O(n2). Faktanya, untuk mengevaluasi seluruh penutupan ε satu kali, seseorang dapat menggunakan algoritma penutupan transitif seperti algoritma Warshall5.

Setelah menghitung ε-closure, kita dapat melanjutkan ke sintesis DFA menggunakan konstruksi himpunan bagian. Pengaruh utama pada konsumsi waktu diberikan oleh jumlah status DFA, yang bisa sama dengan 2n. Untuk setiap keadaan, transisi dapat dihitung dalam waktu O(n3) menggunakan ε-closure dan tabel transisi NFA untuk setiap simbol masukan. Misalkan kita perlu menghitung δ((q1, q2, …, qk), a) untuk DFA. Dari masing-masing keadaan qi seseorang dapat mencapai paling banyak n keadaan sepanjang jalur berlabel ε, dan masing-masing keadaan ini dapat mempunyai paling banyak n busur berlabel a. Dengan membuat array yang diindeks berdasarkan negara bagian, kita dapat menghitung gabungan paling banyak n himpunan dari paling banyak n negara bagian dalam waktu yang sebanding dengan n2.

Dengan cara ini, untuk setiap keadaan qi, seseorang dapat menghitung himpunan keadaan yang dapat dicapai dari qi sepanjang jalur berlabel a (mungkin termasuk busur berlabel ε). Karena k ≤ n, terdapat paling banyak n keadaan qi, dan untuk masing-masing keadaan tersebut, menghitung keadaan yang dapat dijangkau membutuhkan waktu O(n2). Dengan demikian, waktu keseluruhan menghitung status yang dapat dijangkau adalah O(n3). Menggabungkan kumpulan status yang dapat dijangkau hanya memerlukan O(n2) waktu tambahan, sehingga menghitung satu transisi DFA memerlukan waktu O(n3).

Perhatikan bahwa jumlah simbol masukan dianggap konstan dan tidak bergantung pada n. Jadi, baik dalam perkiraan waktu berjalan ini maupun lainnya, jumlah simbol masukan tidak dipertimbangkan. Ukuran alfabet masukan hanya mempengaruhi faktor konstanta yang tersembunyi dalam notasi “O Besar”.

Jadi, waktu untuk mengubah NKA menjadi DKA, termasuk situasi ketika NKA mengandung transisi ε, adalah O(n32n). Tentu saja, dalam praktiknya, biasanya jumlah negara bagian yang dibangun jauh lebih sedikit dari 2n. Terkadang hanya ada n dari mereka. Oleh karena itu, kita dapat mengatur perkiraan waktu berjalan ke O(n3s), dengan s adalah jumlah status yang sebenarnya dimiliki DFA.

Konversi DKA ke NKA

Ini adalah transformasi sederhana yang memerlukan waktu O(n) untuk DFA dengan n status. Yang perlu dilakukan hanyalah mengubah tabel transisi untuk DFA dengan mengapit status dalam tanda kurung () dan juga menambahkan kolom untuk ε jika ingin mendapatkan ε-NFA. Karena jumlah simbol masukan (yaitu lebar tabel lompat) diasumsikan konstan, penyalinan dan pemrosesan tabel memerlukan waktu O(n).

Mengubah automaton menjadi ekspresi reguler

Di setiap n tahapan (di mana n adalah jumlah status DFA), ukuran ekspresi reguler yang dibuat dapat meningkat empat kali lipat, karena setiap ekspresi dibuat dari empat ekspresi dari siklus sebelumnya. Jadi, menulis n3 ekspresi saja bisa memakan waktu O(n34n). Desain yang ditingkatkan dari Bagian 3.2.2 mengurangi faktor konstanta namun tidak mempengaruhi eksponensial masalah ini (dalam kasus terburuk).

Konstruksi serupa memerlukan waktu berjalan yang sama jika NFA, atau bahkan ε-NFA, dikonversi, tetapi hal ini tidak dibuktikan di sini. Namun, penggunaan desain untuk satelit telah sangat penting. Jika Anda terlebih dahulu mengubah NFA menjadi DFA, lalu DFA menjadi ekspresi reguler, maka diperlukan waktu O(n34n32n), yaitu eksponensial ganda.

Mengubah ekspresi reguler menjadi robot

Mengonversi ekspresi reguler menjadi ε-NFA akan memerlukan waktu linier. Anda perlu mengurai ekspresi reguler secara efisien menggunakan metode yang membutuhkan waktu O(n) untuk ekspresi reguler dengan panjang n6. Hasilnya adalah sebuah pohon dengan satu simpul untuk setiap karakter ekspresi reguler (walaupun tanda kurung tidak muncul di pohon ini, karena tanda kurung hanya mengontrol penguraian ekspresi).

Pohon yang dihasilkan dari ekspresi reguler tertentu dapat diproses dengan membuat ε-NFA untuk setiap node. Aturan transformasi ekspresi reguler yang disajikan di Bagian 3.2.3 tidak pernah menambahkan lebih dari dua status dan empat busur ke setiap simpul pohon ekspresi. Akibatnya, jumlah negara bagian dan jumlah busur dari ε-NFA yang dihasilkan sama dengan O(n). Selain itu, pekerjaan pembuatan elemen-elemen ini pada setiap node pohon analisis adalah konstan, asalkan fungsi yang memproses setiap subpohon mengembalikan pointer ke status awal dan status penerimaan robot tersebut.

Kami sampai pada kesimpulan bahwa membangun ε-NFA menggunakan ekspresi reguler membutuhkan waktu, bergantung secara linear pada ukuran ekspresi. Transisi ε dapat dihilangkan dari ε-NFA dengan n status dengan mengubahnya menjadi NFA reguler dalam waktu O(n3) dan tanpa menambah jumlah status. Namun, konversi ke DKA memerlukan waktu yang sangat lama.

Untuk studi lebih lanjut tentang sifat-sifat automata terbatas dan, khususnya, untuk memecahkan masalah sintesis penting mempunyai teorema berikut.

Teorema 7.7 (teorema determinisasi). Untuk robot berhingga apa pun, robot berhingga deterministik ekuivalen dapat dibuat.

Untuk membuktikan teorema tersebut, pertama-tama perlu dijelaskan algoritma untuk membangun otomat terbatas deterministik dari otomat asli; kedua, untuk membenarkan algoritma ini dengan membuktikan secara teliti bahwa algoritma ini memang menghasilkan mesin negara yang deterministik dan setara dengan yang asli. Di sini kami hanya menyajikan algoritma untuk membangun robot deterministik.

Transformasi robot berhingga sembarang menjadi robot deterministik ekuivalen dilakukan dalam dua tahap: pertama, busur berlabel \lambda dihilangkan, kemudian dilakukan determinisasi itu sendiri.

1. Menghapus transisi λ (busur berlabel \lambda).

Untuk berpindah dari mesin keadaan semula M=(V,Q,q_0,F,\delta) ke mesin negara yang setara M"=(V,Q",q_0,F",\delta") tanpa transisi λ, cukup melakukan transformasi berikut pada grafik asli M.

A. Semua keadaan, kecuali keadaan awal, yang hanya memasukkan busur dengan label \lambda, akan dihapus; dengan demikian mendefinisikan himpunan Q" dari robot terbatas M". Jelas bahwa Q"\subseteq Q. Pada saat yang sama, kita berasumsi bahwa keadaan awal tetap sama.

B. Himpunan busur robot terbatas M" dan labelnya (dengan demikian fungsi transisi M") didefinisikan sebagai berikut: untuk dua keadaan p,r\dalam Q",~ p\ke_(a)r berlaku jika dan hanya jika a\dalam V dan pada grafik M salah satu dari dua hal berlaku: ada busur dari p ke r yang labelnya berisi simbol a, atau ada keadaan q sedemikian rupa sehingga p\Panah Kanan_(\lambda)^(+)q dan q\to_(a)r . Dalam hal ini, simpul q, secara umum, mungkin bukan milik himpunan Q", yaitu mungkin hilang selama transisi ke otomat M" (Gbr. 7.11). Jika q\in Q" , maka, tentu saja, busur (q,r) akan dipertahankan di M" dan simbol a akan menjadi salah satu simbol yang termasuk dalam label busur ini (Gbr. 7.12).

Jadi, di M" semua busur M disimpan yang labelnya berbeda dari \lambda dan yang menghubungkan sepasang (simpul) keadaan dari himpunan Q" (tidak dihapus menurut bagian a). Selain itu, untuk triple apa pun menyatakan p,q,r(belum tentu berbeda!), sehingga p,r\in Q" dan terdapat jalur dengan panjang bukan nol dari p ke q yang labelnya sama dengan \lambda (yaitu jalur sepanjang transisi λ), dan dari q ke r mengarah busur, yang labelnya berisi simbol a dari alfabet masukan, di M" sebuah busur dibuat dari p ke r, yang labelnya berisi simbol a (lihat Gambar 7.11).

V. Himpunan keadaan akhir F" dari otomat terbatas M" berisi semua keadaan q\in Q", yaitu keadaan otomat terbatas M, tidak dihapus sesuai dengan paragraf a, yang mana q\Panah Kanan_(\lambda)^(\ast)q_f untuk beberapa q_f\in F (yaitu keadaan q itu sendiri merupakan keadaan akhir dari otomat terbatas M, atau jalur yang panjangnya bukan nol mengarah dari sana sepanjang busur berlabel \lambda ke salah satu keadaan akhir dari otomat terbatas M) (Gbr. 7.13).

2. Tekad itu sendiri.

Membiarkan M=(Q,V,q_0,F,\delta)- robot terbatas tanpa transisi λ. Mari kita membuat otomat terbatas deterministik M_1 yang setara dengan M.

Otomat berhingga ini didefinisikan sedemikian rupa sehingga himpunan keadaannya adalah himpunan semua himpunan bagian dari himpunan keadaan otomat terbatas M. Ini berarti bahwa setiap keadaan otomat terbatas M_1 didefinisikan sebagai himpunan bagian tertentu dari himpunan keadaan otomat terbatas M. Dalam hal ini, keadaan awal dari mesin keadaan terbatas yang baru (yaitu M_1) adalah himpunan bagian tunggal yang berisi keadaan awal dari mesin keadaan terbatas yang lama (yaitu M), dan keadaan akhir dari mesin keadaan terbatas yang baru semuanya merupakan himpunan bagian tersebut Q yang mengandung setidaknya satu titik akhir dari robot terbatas asli M.

Untuk selanjutnya, dengan memberikan kebebasan berpendapat, terkadang kita menyebut status himpunan status otomat terbatas M_1. Namun, penting untuk dipahami dengan jelas bahwa masing-masing himpunan keadaan tersebut merupakan keadaan terpisah dari otomat terbatas baru, namun bukan himpunan keadaannya. Pada saat yang sama, untuk otomat terbatas M yang asli ("lama") inilah tepatnya himpunan keadaannya. Secara kiasan, setiap subset keadaan dari finite automaton yang lama “diciutkan” menjadi satu keadaan dari finite automaton* yang baru.

*Secara formal, kita harus mendefinisikan himpunan Q_1 sebagai himpunan yang berkorespondensi satu-satu dengan himpunan 2^Q, namun akan lebih mudah bagi kita untuk berasumsi bahwa Q_1 berimpit dengan 2^Q - lagipula, himpunan tersebut himpunan keadaan suatu robot berhingga dapat berupa himpunan berhingga tak kosong apa pun.

Fungsi transisi otomat terbatas baru didefinisikan sedemikian rupa sehingga dari himpunan keadaan S dengan simbol masukan a, otomat terbatas M_1 menuju ke himpunan keadaan, yang merupakan gabungan semua himpunan keadaan otomat terbatas lama yang menjadi tempat masuknya robot terbatas lama ini menggunakan simbol a dari setiap himpunan keadaan S. Jadi, robot terbatas M_1 bersifat deterministik berdasarkan konstruksi.

Uraian verbal di atas dapat diterjemahkan ke dalam rumus sebagai berikut: kita membangun mesin berhingga M_1 sehingga

M_1=(Q_1,V,\(q_0\),F_1,\delta_1), Di mana

\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\untuk semua a\di V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Lebih Besar). \end(kasus)

Mari kita perhatikan fakta bahwa di antara keadaan otomat terbatas baru terdapat keadaan \varnothing , dan, menurut (7.8), \delta_1(\varnothing,a)=\varnothing untuk karakter masukan apa pun a . Artinya, sekali dalam keadaan seperti itu, mesin negara M_1 tidak akan meninggalkannya. Secara umum, keadaan apa pun q dari otomat berhingga sedemikian rupa sehingga untuk setiap simbol masukan a yang kita miliki \delta(q,a)=q disebut keadaan penyerap dari otomat berhingga. Dengan demikian, keadaan \vartidak ada yang diserap oleh mesin keadaan terbatas deterministik M_1. Hal ini juga berguna untuk dicatat \delta_1(S,a)=\vartidak ada jika dan hanya jika untuk setiap q\in S (keadaan otomat terbatas lama dari himpunan keadaan S) \delta(q,a)=\vartidak ada, yaitu. pada grafik M, tidak ada busur keluar dari setiap keadaan q, ditandai dengan simbol a.

Dapat dibuktikan bahwa finite automaton yang diperoleh dengan menggunakan algoritma tersebut ekuivalen dengan algoritma aslinya.

Contoh 7.9. Mari kita tentukan otomat terbatas yang ditunjukkan pada Gambar. 7.14.

Sebuah robot terbatas yang setara tanpa transisi λ ditunjukkan pada Gambar. 7.15. Perhatikan bahwa simpul q_2 menghilang, karena hanya busur “kosong” yang memasukinya.

Untuk menentukan automaton yang dihasilkan, sama sekali tidak perlu menuliskan semua 2^3=8 statusnya, banyak di antaranya mungkin tidak dapat dijangkau dari status awal \(q_0\) . Untuk mendapatkan status yang dapat dijangkau dari \(q_0\), dan hanya dari \(q_0\), kita akan menggunakan apa yang disebut metode penarikan.

Cara ini secara umum dapat dijelaskan sebagai berikut.

Dalam otomat terbatas awal (tanpa busur kosong) kita mendefinisikan semua himpunan keadaan yang dapat dijangkau dari keadaan awal, yaitu. untuk setiap simbol masukan a kita menemukan himpunan \delta(q_0,a) . Setiap himpunan dalam otomat baru adalah keadaan yang dapat diakses langsung dari himpunan awal.

Untuk setiap himpunan keadaan S yang ditentukan dan setiap simbol masukan a, kita temukan himpunan tersebut \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). Semua keadaan yang diperoleh pada langkah ini akan menjadi keadaan otomat baru (deterministik), yang dapat dijangkau dari titik awal sepanjang jalur dengan panjang 2. Kita ulangi prosedur yang dijelaskan sampai tidak ada keadaan himpunan baru (termasuk keadaan kosong!) yang muncul. Dapat ditunjukkan bahwa ini menghasilkan semua keadaan otomat terbatas M_1 yang dapat dijangkau dari keadaan awal \(q_0\) .

Untuk mesin keadaan terbatas pada Gambar. 7.15 kita punya:

\mulai(sejajar)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\cup \delta(q_3,b)= \(q_1\)\cup\(q_1\)=\(q_1\). \end(sejajar)

Karena tidak ada himpunan keadaan baru yang muncul, prosedur “penarikan” berakhir di sini, dan kita mendapatkan grafik yang ditunjukkan pada Gambar. 7.16.

Penambahan bahasa reguler

Salah satu konsekuensi teoritis penting dari teorema determinisasi adalah teorema berikut.

Teorema 7.8. Pelengkap bahasa reguler adalah bahasa reguler.

Misalkan L adalah bahasa biasa dalam alfabet V. Maka pelengkap bahasa L (sebagai kumpulan kata) adalah bahasa \overline(L)=V^(\ast)\setminus L.

Menurut Teorema 7.7, untuk bahasa biasa L, otomat terbatas deterministik M dapat dibangun yang menerima L. Karena dalam robot deterministik dari setiap titik untuk setiap simbol masukan, transisi ke satu titik ditentukan, maka apa pun rantai x dalam alfabet V, terdapat jalur unik untuknya di M, dimulai dari keadaan awal di mana rantai x dibaca. Jelas bahwa rantai x diperbolehkan oleh robot M , yaitu x\in L(M) , jika dan hanya jika keadaan terakhir dari jalur yang ditentukan adalah final. Oleh karena itu rantai x\notin L(M) jika dan hanya jika keadaan terakhir dari jalur yang ditentukan bukan final. Namun kita hanya memerlukan otomat berhingga M" yang menerima rantai x jika dan hanya jika hal tersebut tidak diperbolehkan oleh otomat berhingga asli M. Akibatnya, dengan mengubah setiap keadaan akhir M menjadi keadaan non-final dan sebaliknya, kita memperoleh a robot deterministik yang menerima penambahan bahasa L .

Teorema yang telah terbukti memungkinkan kita untuk membuat otomat berhingga yang tidak menerima himpunan rantai tertentu, dengan menggunakan metode berikut: pertama-tama kita membuat otomat yang menerima himpunan rantai tertentu, kemudian kita menentukannya dan menuju ke otomat tersebut untuk penjumlahan sebagai ditunjukkan dalam pembuktian Teorema 7.8.

Contoh 7.10. A. Mari kita membangun robot terbatas yang menerima semua rantai dalam alfabet \(0;1\) kecuali rantai 101.

Pertama, mari kita membangun robot terbatas yang memungkinkan rantai tunggal 101. Robot ini ditunjukkan pada Gambar. 7.17.

Otomat ini bersifat kuasi-deterministik, namun tidak deterministik, karena ia tidak sepenuhnya terdefinisi. Mari kita tentukan dan dapatkan otomat terbatas ekivalen deterministik yang ditunjukkan pada Gambar. 7.18.

Dan akhirnya, berpindah ke penjumlahan (dan mengganti nama negara bagian), kita mendapatkan robot yang ditunjukkan pada Gambar. 7.19.

Perhatikan bahwa pada automaton yang dihasilkan semua simpul, kecuali simpul s_3, adalah final.

Perhatikan juga bahwa transisi ke komplemen, yang dibahas dalam pembuktian Teorema 7.8, hanya dapat dilakukan dalam robot deterministik. Jika kita menukar peran simpul final dan non-final dalam robot yang ditunjukkan pada Gambar. 7.17, maka kita akan mendapatkan robot yang menerima bahasa \(\lambda,1,10\) , yang bukan - seperti yang bisa dibayangkan dengan mudah - himpunan semua rantai selain rantai 101.

Perhatikan juga bahwa mesin keadaan terbatas pada Gambar. 7.19 mengizinkan semua string yang berisi kemunculan string 101 tetapi tidak cocok dengan string itu sendiri. Di sini, misalnya, adalah jalur yang membawa rantai 1011: s_0,s_1,s_2,s_3,t.

B. Mari kita membangun finite automaton yang menerima semua rantai dalam alfabet \(0;1\) kecuali yang mengandung kemunculan rantai 101. Misalkan sebuah bahasa L, setiap rantai berisi kemunculan rantai 101. Dapat berupa didefinisikan sebagai berikut:

L=(0+1)^(\ast)101(0+1)^(\ast).

Kita perlu membuat robot untuk melengkapi bahasa L.

Dalam hal ini, dengan menggunakan ekspresi reguler secara langsung, mudah untuk membuat robot terbatas yang menerima bahasa L (Gbr. 7.20).

Kemudian kita akan melakukan determinasi dengan menggunakan metode “pull”. Hasil penentuan disajikan pada Gambar. 7.21.

Untuk menyelesaikan masalah sepenuhnya, yang tersisa hanyalah pada Gambar. 7.21 menukar peran simpul final dan non-final (Gbr. 7.22).

V. Mari kita bahas gagasan membangun otomat terbatas yang memungkinkan rantai tersebut dan hanya rantai dalam alfabet \(0;1\) yang tidak dimulai dengan rantai 01 dan tidak diakhiri dengan rantai 11 (yaitu, rantai dari bentuk 01x dan rantai tipe y11 tidak diperbolehkan, tidak peduli apa pun rantainya x,y\in\(0;1\) ).

Dalam hal ini, komplemen bahasa yang diperlukan untuk membangun otomat terbatas adalah himpunan semua rantai nol dan rantai yang dimulai dengan rantai 01 atau diakhiri dengan rantai 11. Sebuah otomat yang memungkinkan himpunan ini rantai dibangun sebagai robot untuk menggabungkan 01(0+1)^(\ast)+(0+1)^(\ast)11 dengan cara yang sama seperti yang dijelaskan dalam pembuktian teorema Kleene (lihat Teorema 7.6).

Dari sifat bahwa kelas bahasa biasa tertutup terhadap komplemen (lihat Teorema 7.8), maka kelas ini tertutup terhadap perpotongan, teori himpunan, dan perbedaan simetris.

Akibat wajar 7.3. Untuk dua bahasa reguler L_1 dan L_2 pernyataan berikut ini benar:

1) perpotongan L_1\cap L_2 beraturan;
2) selisih L_1\setminus L_2 adalah reguler;
3) perbedaan simetris L_1\variatsegitiga L_2 reguler.

Validitas pernyataan berikut dari identitas:

\begin(selaras) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\triangle\ ,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end(sejajar)

Pertama, hasil yang diperoleh memungkinkan kita untuk menegaskan bahwa kelas bahasa reguler sehubungan dengan operasi penyatuan, perpotongan, dan penjumlahan adalah aljabar Boolean, yang satuannya adalah bahasa universal, dan nol adalah bahasa kosong. Kedua, sifat-sifat aljabar dari keluarga bahasa biasa ini memungkinkan kita untuk menyelesaikannya masalah penting mengenali kesetaraan dua automata terbatas yang berubah-ubah.

Menurut Definisi 7.10, mesin keadaan terbatas adalah setara jika bahasa yang diterimanya sama. Oleh karena itu, untuk memverifikasi kesetaraan automata M_1 dan M_2, cukup dibuktikan bahwa perbedaan simetris antara bahasa L(M_1) dan L(M_2) adalah kosong. Untuk melakukan hal ini, pada gilirannya, cukup dengan membuat sebuah robot yang mengakui perbedaan ini dan memastikan bahwa bahasa yang diterimanya kosong. Secara umum, masalah mengenali bahasa mesin negara kosong disebut masalah kekosongan mesin negara. Untuk mengatasi masalah ini, cukup mencari himpunan keadaan akhir robot yang dapat dicapai dari keadaan awal. Karena mesin keadaan berhingga adalah graf berarah, masalah ini dapat diselesaikan, misalnya dengan menggunakan penelusuran luas pertama. Suatu bahasa yang diperbolehkan oleh mesin keadaan terbatas adalah kosong jika dan hanya jika himpunan keadaan akhir yang dapat dijangkau dari keadaan awal kosong. Dalam praktiknya, lebih baik mengenali kesetaraan automata terbatas menggunakan algoritma minimalisasi, tetapi sekarang penting bagi kita untuk menekankan bahwa kemungkinan mendasar untuk memecahkan masalah kesetaraan mengikuti Teorema 7.7 dan konsekuensi aljabarnya.

Diperlukan oleh mesin keadaan terbatas non-deterministik M = (Q, T, D, Q 0 , F) membangun robot terbatas deterministik M = (Q", T, D", Q" 0 , F"). Keadaan awal otomat yang sedang dibangun adalah penutupan ε dari keadaan awal otomat asli. ε-closure adalah sekumpulan keadaan yang dapat dicapai dari keadaan tertentu melalui transisi sepanjang ε. Lebih jauh lagi, meskipun terdapat keadaan-keadaan yang transisinya belum dibangun (transisi dibuat sepanjang simbol-simbol yang transisinya ada pada otomat aslinya), untuk setiap simbol, penutupan ε dari himpunan keadaan-keadaan yang dapat dijangkau dari keadaan yang dipertimbangkan melalui transisi sepanjang simbol yang dipertimbangkan dihitung. Jika keadaan yang sesuai dengan himpunan yang ditemukan sudah ada, maka transisi ditambahkan di sana. Jika tidak, maka status baru yang diterima akan ditambahkan.

Contoh

Inisialisasi

Keadaan yang berhubungan dengan penutupan ε dari keadaan awal ditandai. Negara-negara bagian ini akan sesuai dengan negara bagian A DKA masa depan.

Iterasi pertama

Dari penutupan ε terdapat transisi ke keadaan NKA 3 dan 10 (menurut A Dan C, masing-masing). Untuk keadaan 3, penutupan ε adalah himpunan keadaan (3, 4, 6), untuk keadaan 10 - (10). Mari kita nyatakan status DFA baru yang sesuai dengan himpunan ini sebagai B Dan C.

kondisi DKA	Banyak negara bagian NKA
		A	B	C
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

Iterasi kedua

Dari kumpulan status NFA (3, 4, 6), sesuai dengan status DFA B ada dua transisi - ke keadaan 5 (oleh B) dan 7 (oleh C). Penutupan ε-nya berpotongan, tetapi himpunannya sendiri berbeda, sehingga dikaitkan dengan dua status DFA baru - D Dan E. Dari negara bagian NKA yang sesuai dengan negara bagian DKA C, tidak ada transisi.

kondisi DKA	Banyak negara bagian NKA	Simbol yang digunakan untuk bernavigasi
		A	B	C
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	-	-	-
E	{2, 7, 8, 9}	-	-	-

Iterasi ketiga

Dari kumpulan status NFA yang sesuai dengan status DFA D Dan E transisi dilakukan ke himpunan keadaan yang sesuai dengan keadaan yang ada (dari himpunan (2, 5, 8, 9) yang sesuai dengan keadaan tersebut D, Oleh A transisi ke keadaan 3, milik himpunan (3, 4, 6), sesuai dengan keadaan DFA B, Oleh C- transisi ke negara bagian 10, sesuai dengan negara bagian C; demikian pula untuk himpunan yang sesuai dengan status DFA E). Proses pembuatan tabel negara bagian dan transisi DKA telah selesai.

kondisi DKA	Banyak negara bagian NKA	Simbol yang digunakan untuk bernavigasi
		A	B	C
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	B	-	C
E	{2, 7, 8, 9}	B	-	C

Hasil:

Konstruksi tata bahasa linier kanan menggunakan finite automaton

Kami menetapkan nonterminal untuk setiap negara bagian. Jika terjadi peralihan dari negara X dalam sebuah keadaan Y Oleh A, tambahkan aturan X → ay. Tambahkan aturan untuk keadaan akhir X→ ε. Untuk transisi ε - X → Y.

Contoh 1 (mesin keadaan terbatas deterministik)

• SEBUAH → A B | C C
• B → B D | C E
• C → ε
• D → A B | C C
• E → A B | C C

Contoh 2 (mesin keadaan terbatas non-deterministik)

• 1 → 2 | 9
• 2 → A 3
• 3 → 4 | 6
• 4 → B 5
• 5 → 8
• 6 → C 7
• 7 → 8
• 8 → 2 | 9
• 9 → C 10
• 10→ε

Pembangunan DFA dari RT

Biarkan ada ekspresi reguler R. Dengan menggunakan ekspresi reguler ini, perlu untuk membangun robot terbatas deterministik D seperti yang L(D) = L(R).

Modifikasi Ekspresi Reguler

Mari kita tambahkan simbol yang menunjukkan akhir RT - “#”. Hasilnya, kami mendapatkan ekspresi reguler ( R)#.

Membangun pohon

Mari kita bayangkan ekspresi reguler sebagai pohon, yang daunnya merupakan simbol terminal, dan simpul internal adalah operasi penggabungan ".", gabungan "∪" dan iterasi "*". Kami akan menetapkan nomor unik untuk setiap daun pohon (kecuali daun ε) dan merujuknya, di satu sisi, sebagai posisi di pohon dan, di sisi lain, sebagai posisi simbol yang sesuai dengan daun.

Evaluasi fungsi nullable, firstpos, lastpos

Sekarang, melintasi pohon T dari bawah ke atas dari kiri ke kanan, kita menghitung tiga fungsi: dapat dibatalkan, pos pertama, Dan pos terakhir. Fungsi dapat dibatalkan, pos pertama Dan pos terakhir didefinisikan pada simpul pohon. Arti dari semua fungsi kecuali dapat dibatalkan, adalah sekumpulan posisi. Fungsi pos pertama(N) untuk setiap node n dari pohon sintaksis ekspresi reguler memberikan himpunan posisi yang sesuai dengan karakter pertama dalam substring yang dihasilkan oleh subekspresi dengan titik di N. Juga, pos terakhir(N) memberikan himpunan posisi yang sesuai dengan karakter terakhir dalam substring yang dihasilkan oleh subekspresi dengan titik puncak N. Untuk node N, yang subpohonnya (yaitu pohon yang simpulnya N adalah root) dapat menghasilkan kata kosong, kita definisikan dapat dibatalkan(N) = BENAR, dan untuk node yang tersisa PALSU. Tabel perhitungan dapat dibatalkan, pos pertama, pos terakhir:

simpul N	dapat dibatalkan(N)	pos pertama(N)	pos terakhir(N)
ε	BENAR	∅	∅
Saya ≠ ε	PALSU	{Saya}	{Saya}
u∪v	dapat dibatalkan(kamu) atau dapat dibatalkan(ay)	pos pertama(kamu) ∪ pos pertama(ay)	pos terakhir(kamu) ∪ pos terakhir(ay)
kamu. ay	dapat dibatalkan(kamu) Dan dapat dibatalkan(ay)	jika dapat dibatalkan(kamu) Kemudian pos pertama(kamu) ∪ pos pertama(ay) kalau tidak pos pertama(kamu)	jika dapat dibatalkan(ay) Kemudian pos terakhir(kamu) ∪ pos terakhir(ay) kalau tidak pos terakhir(ay)
v*	BENAR	pos pertama(ay)	pos terakhir(ay)

Membangun pos tindak lanjut

Fungsi pos tindak lanjut dihitung melalui dapat dibatalkan, pos pertama Dan pos terakhir. Fungsi pos tindak lanjut didefinisikan dalam banyak posisi. Arti pos tindak lanjut adalah sekumpulan posisi. Jika Saya- posisi, kalau begitu pos tindak lanjut(Saya) ada banyak posisi J sedemikian rupa sehingga ada string tertentu... CD..., termasuk dalam bahasa yang dijelaskan oleh RT, sedemikian rupa Saya cocok dengan kejadian ini C, A J- kejadian D. Fungsi pos tindak lanjut juga dapat dihitung dalam satu traversal pohon menggunakan dua aturan berikut

1. Membiarkan N- simpul internal dengan operasi "." (rangkaian); A, B- keturunannya. Kemudian untuk setiap posisi Saya termasuk dalam pos terakhir(A pos tindak lanjut(Saya) sekelompok pos pertama(B).
2. Membiarkan N- simpul internal dengan operasi “*” (iterasi), A- keturunannya. Kemudian untuk setiap posisi Saya termasuk dalam pos terakhir(A), ditambahkan ke kumpulan nilai pos tindak lanjut(Saya) sekelompok pos pertama(A).

Contoh

Hitung nilai fungsi pos tindak lanjut untuk ekspresi reguler ( A(B|C))*C.

Posisi	Arti pos tindak lanjut
1: (A (B|C))*C	{2, 3}
2: (A(B |C))*C	{1, 4}
3: (A(B|C ))*C	{1, 4}
4: (A(B|C))*C	{5}

Konstruksi DFA

DFA mewakili sekumpulan status dan serangkaian transisi di antara status tersebut. Negara bagian DKA mewakili banyak posisi. Pembangunan DFA terdiri dari penambahan negara-negara yang diperlukan secara bertahap dan membangun transisi untuk negara-negara tersebut. Awalnya ada satu negara bagian, pos pertama(akar) (akar- akar pohon) yang transisinya belum dibuat. Transisi dilakukan menggunakan karakter dari ekspresi reguler. Setiap karakter berhubungan dengan serangkaian posisi ( P Saya). Menyatukan semua orang pos tindak lanjut(x) adalah negara bagian yang perlu dipindahkan, di mana x adalah posisi yang ada di antara posisi negara bagian dan di antara posisi simbol dari RF yang dilalui transisi tersebut. Kalau tidak ada keadaan seperti itu, maka harus ditambah. Proses ini harus diulang sampai semua transisi untuk semua negara bagian telah selesai dibangun. Semua negara bagian yang memuat posisi simbol # yang ditambahkan di akhir PB dinyatakan final.

DKA diperoleh dari RV ( A(B|C))*C

Contoh

Buat DFA menggunakan ekspresi reguler ( A(B|C))*C.

kondisi DKA	Simbol
	sebuah (1)	b (2)	c (3, 4)
SEBUAH (1, 4)	B (2, 3)	-	C (5)
B (2, 3)	-	SEBUAH (1, 4)	SEBUAH (1, 4)
C (5)	-	-	-

Pembangunan DFA dengan jumlah negara bagian minimum

DFA dengan jumlah negara bagian minimum dibuat untuk DFA yang ditentukan di mana pun, yaitu. seperti yang . Untuk DFA apa pun, ada DFA yang setara di mana pun.

Konstruksi DFA yang ditentukan di mana-mana

Mari kita perkenalkan negara bagian baru dan tentukan kumpulan negara bagian baru .

Mari kita definisikan fungsi transisi baru seperti ini:

Konstruksi partisi (formal)

Mari kita buat partisi awal P kumpulan negara bagian menjadi dua kelompok: negara bagian akhir F dan sisanya S\F, yaitu. P = {F, Tanya Jawab}.

Terapkan ke setiap kelompok G ∈ P prosedur berikut. Menghancurkan G menjadi subkelompok sehingga menyatakan S Dan T dari G berada dalam grup yang sama jika dan hanya jika untuk setiap simbol masukan A negara S Dan T mengalami transisi A menjadi negara bagian dari kelompok yang sama menjadi P.

Kami menambahkan subgrup yang dihasilkan ke partisi baru P baru.

Kami menerima P = P baru dan ulangi konstruksi partisi hingga stabil, yaitu hingga partisi berhenti berubah.

Konstruksi partisi (algoritma)

Untuk membangun partisi, ada algoritma berikut. Kami membuat tabel transisi untuk automaton asli, kami membangun partisi awal.

Kami menetapkan pengidentifikasi untuk setiap grup dari partisi (untuk partisi awal, misalnya, 0 dan 1).

Untuk setiap negara bagian (setiap baris tabel) kami menetapkan string dalam bentuk "a.bcd...xyz", di mana adalah pengidentifikasi grup tempat negara bagian tersebut berasal [kolom pertama (dari mana kita pergi) , kolom kedua (di mana kita menggunakan karakter pertama), ..., kolom terakhir (di mana kita menggunakan karakter terakhir)].

Kami membangun grup baru berdasarkan kebetulan string, yaitu, sehingga negara bagian dengan string identik dimasukkan ke dalam satu grup.

Kemudian, iterasi baru. Kami menetapkan pengidentifikasi baru ke grup yang dihasilkan, misalnya (0, 1, ..., n). Dan kami ulangi pembangunan partisi hingga stabil.

Perhatikan bahwa ketika hanya ada satu negara bagian yang tersisa dalam grup, pada tahap selanjutnya dalam membangun partisi, tidak perlu menuliskan string pengidentifikasi untuk negara ini, karena string ini bagaimanapun juga akan menjadi unik karena karakter pertama dari talinya. Dengan kata lain, ketika dipecah, tidak akan terjadi apa-apa pada grup dari satu negara bagian - grup tersebut ditransfer ke pemisahan baru apa adanya.

Konstruksi robot tereduksi

Masing-masing grup yang dihasilkan menjadi status DFA baru. Jika suatu grup berisi keadaan awal (final) dari robot asli, maka grup ini menjadi keadaan awal (final) dari DFA baru. Transisi dibangun dengan cara yang jelas: transisi ke suatu keadaan dari suatu kelompok dianggap sebagai transisi ke suatu kelompok.

Kami membawa senapan mesin. Pertama-tama kita membuang yang tidak menghasilkan (steril, “mati”), Kemudian keadaan yang tidak dapat dijangkau (definisi diberikan untuk simbol, tetapi jelas ditransfer ke keadaan robot).

Secara umum, menghapus negara-negara mati mengubah DFA menjadi NFA, karena dalam DFA semua transisi harus didefinisikan. Namun, dalam Buku Naga, penyimpangan dari definisi formal masih dianggap dapat diterima.

Contoh

Untuk membuat DFA dengan nomor negara bagian minimum untuk DFA dengan bentuk berikut:

• Partisi awal: (C) ( keadaan akhir), (A, B, D, E) ( semua negara bagian lainnya).
• (C) ( tanpa perubahan), (A, D, E), (B), ( karena dari A, D, E kita masing-masing melewati a, c ke B dan C).
• Kita tidak bisa membuat perpecahan lagi.

Misalkan grup (C) berkorespondensi dengan negara bagian C, grup (A, D, E) berkorespondensi dengan negara bagian A, dan grup (B) berkorespondensi dengan negara bagian B. Kemudian kita memperoleh DFA dengan jumlah negara bagian minimum:

Contoh (algoritma untuk membangun partisi)

Tabel transisi untuk DFA yang ditentukan di mana pun (keadaan Z ditambahkan) yang sesuai dengan RT (ab|ε)a*|abb|b*a. Dari tugas ujian tahun 2012.

	A	B	saya 0	saya 1
→SEBUAH*	B	C	0.01	0.12
B*	D	E	0.00	1.01
C	F	C	1.01
D*	D	Z	0.01	0.04
E*	D	Z	0.00	1.03
F*	Z	Z	0.11
Z	Z	Z	1.11

Iterasi:

• Saya 0: ABCDEF(0), CZ(1).
• Saya 1: IKLAN(0), MENJADI(1), C(2), F(3), Z(4).
• Saya 2: A, B, C, D, E, F, Z.

Hasilnya: mesin sudah memiliki jumlah minimum status :-)

DKA memungkinkan penambahan lidah

Algoritme untuk membuat DFA yang menerima komplemen bahasa L(L̅) terdiri dari dua langkah:

• Konstruksi DFA lengkap
• Membangun robot yang diinginkan darinya

Faktanya, tidak ada DKA yang lengkap. Di bawah DKA penuh beberapa guru memahami robot yang tabel transisinya tidak memiliki sel kosong. Namun, sesuai dengan definisi DFA - δ: Q × Σ → Q - dalam hal apa pun tidak boleh ada sel kosong. Namun, robot “dengan sel kosong” memenuhi definisi NFA. Selama penyelesaian, kita sering kali hanya mendapatkan NFA yang tidak memiliki transisi ke DFA.

Untuk mengisinya kembali, cukup menambahkan negara bagian baru X, dan “alih-alih” transisi yang tidak ada menambahkan transisi ke keadaan baru ini. Pada saat yang sama, Anda harus ingat untuk menambahkan transisi dari X V X. Sangat mudah untuk melihat bahwa ketika otomat asli tidak menerima rantai tertentu karena tidak adanya transisi, otomat baru akan masuk ke keadaan X dan terjebak di dalamnya. Karena negara bagian baru tidak menerima (final), mesin baru juga tidak akan menerima rantai ini.

Sekarang, untuk membangun robot yang diperlukan, yang diperlukan hanyalah mengubah peran negara penerima dan non-penerima. Dengan kata lain, F" = Q\F.

Konstruksi penganalisis LL(k).

Konversi Tata Bahasa

Tidak semua tata bahasa dapat dianalisis LL(k). Tata bahasa bebas konteks termasuk dalam kelas LL(1) jika tidak mengandung konflik tipe FIRST-FIRST (rekursi kiri - kasus spesial konflik seperti itu) dan IKUTI PERTAMA.

Terkadang tata bahasa non-LL(1) dapat diubah sehingga menjadi LL(1). Beberapa transformasi (lebih tepatnya, yang dibahas dalam kursus) diberikan di bawah ini.

Menghapus rekursi kiri

Mari kita punya aturan bentuk (selanjutnya di bagian ini, huruf kapital - simbol non-terminal, huruf kecil - rantai karakter apa pun):

• SEBUAH → SEBUAH A| A B| ... | A k | M | N | … | z

Hal ini tidak memungkinkan analisis yang jelas, sehingga harus diubah.

Mudah untuk menunjukkan bahwa aturan ini ekuivalen dengan pasangan aturan berikut:

• SEBUAH → M B | N B | ... | z B
• B → A B | B B | ... | k B | ε

Faktorisasi kiri

Inti dari prosedur ini adalah menghilangkan ambiguitas dalam pemilihan aturan berdasarkan simbol kiri. Untuk melakukan ini, awalan kiri yang umum ditemukan dan apa yang mengikutinya dimasukkan ke dalam aturan baru (huruf kecil - rantai karakter apa pun)

Contoh

• SEBUAH → A C | A df | A dg | B

Mengonversi menjadi

• SEBUAH → A B | B
• B → C | D F | D G

Yang pada gilirannya akan berubah menjadi

• SEBUAH → A B | B
• B → C | D DENGAN
• C → F | G

Contoh Konversi Tata Bahasa

G= ((S, A, B), (a, b, c), P, S)

• S → SAbB | A
• SEBUAH → ab | aa | ε
• B → c | ε

Menghapus rekursi kiri untuk S:

• S → sebagai 1
• S 1 → AbBS 1 | ε

Faktorisasi kiri untuk A:

• SEBUAH → aA 1 | ε
• A 1 → b | A

Tata bahasa terakhir:

• S → sebagai 1
• S 1 → AbBS 1 | ε
• SEBUAH → aA 1 | ε
• A 1 → b | A
• B → c | ε

Konstruksi PERTAMA dan IKUTI

PERTAMA(α), dimana α ∈ (N ∪ T)* adalah himpunan terminal dimana α dapat dimulai. Jika α ⇒ ε, maka ε ∈ PERTAMA(α). Oleh karena itu, nilai FOLLOW( A) untuk nonterminal A- banyak terminal yang dapat muncul segera setelahnya A dalam bentuk kalimat apa pun. Jika A mungkin karakter paling kanan dalam beberapa bentuk kalimat, maka penanda akhir $ juga milik FOLLOW( A)

Perhitungan PERTAMA

Untuk terminal

• Untuk terminal mana pun X, X ∈ T,PERTAMA( X) = {X}

Untuk non-terminal

• Jika X adalah nonterminal, maka kita masukkan FIRST( X) = {∅}
• Jika ada aturan dalam tata bahasa X→ ε, lalu tambahkan ε ke PERTAMA( X)
• Untuk setiap non-terminal X dan untuk setiap aturan inferensi X → Y 1 …Y k akan ditambahkan ke FIRST( X) himpunan PERTAMA dari semua simbol di sisi kanan aturan sampai simbol pertama yang tidak menurunkan ε, termasuk simbol tersebut

Untuk rantai

• Untuk serangkaian karakter X 1 …X k FIRST adalah gabungan simbol-simbol FIRST yang termasuk dalam rantai sampai dengan simbol pertama yang ε ∉ FIRST.

Contoh

• S → sebagai 1
• S 1 → AbBS 1 | ε
• SEBUAH → aA 1 | ε
• A 1 → b | A
• B → c | ε

Non-terminal PERTAMA dalam urutan resolusi ketergantungan:

• PERTAMA(S) = (a)
• PERTAMA(A) = (a, ε)
• PERTAMA(A 1) = (b, a)
• PERTAMA(B) = (c, ε)
• PERTAMA(S 1) = (a, b, ε)

PERTAMA untuk aturan inferensi:

• PERTAMA(aS 1) = (a)
• PERTAMA(AbBS 1) = (a, b)
• PERTAMA(ε) = (ε)
• PERTAMA(aA 1) = (a)
• PERTAMA(a) = (a)
• PERTAMA(b) = (b)
• PERTAMA(c) = (c)

IKUTI perhitungan

Mengevaluasi fungsi FOLLOW untuk karakter X:

• Misalkan IKUTI(X) = (∅)
• Jika X adalah aksioma tata bahasa, tambahkan penanda $ ke FOLLOW
• Untuk semua aturan bentuk A → αXβ, tambahkan FIRST(β)\(ε) ke FOLLOW(X) (X dapat diikuti oleh karakter yang dimulai dengan β)
• Untuk semua aturan berbentuk A → αX dan A → αXβ, ε ∈ FIRST(β), tambahkan FOLLOW(A) ke FOLLOW(X) (yaitu, X dapat diikuti oleh semua simbol yang mengikuti A, jika dalam In aturan inferensi, simbol X mungkin yang paling kanan)
• Ulangi dua langkah sebelumnya hingga dimungkinkan untuk menambahkan karakter ke kumpulan

Contoh

• S → sebagai 1
• S 1 → AbBS 1 | ε
• SEBUAH → aA 1 | ε
• A 1 → b | A
• B → c | ε

Hasil:

• IKUTI(S) = ($)
• IKUTI(S 1) = ($) (S 1 adalah karakter paling kanan dalam aturan S → aS 1)
• IKUTI(A) = (b) (setelah A pada aturan S 1 → AbBS 1 muncul b)
• FOLLOW(A 1) = (b) (A 1 adalah karakter paling kanan dalam aturan A → aA 1, oleh karena itu, tambahkan FOLLOW(A) ke FOLLOW(A 1))
• IKUTI(B) = (a, b, $) (tambahkan FIRST(S 1)\(ε) (mengikuti aturan S 1 → AbBS 1), IKUTI(S 1) (karena ada S 1 → ε))

Menyusun tabel

Di meja M untuk pasangan non-terminal-terminal (dalam sel M[A, A]) menunjukkan aturan yang diperlukan untuk menggabungkan kata masukan. Tabel diisi sebagai berikut: untuk setiap aturan inferensi dari tata bahasa tertentu A → α (di mana α adalah rantai di sisi kanan aturan), tindakan berikut dilakukan:

1. Untuk setiap terminal A∈ PERTAMA(α) tambahkan aturan A → α Ke M[A, A]
2. Jika ε ∈ PERTAMA(α), maka untuk masing-masing B∈IKUTI( A) menambahkan A → α Ke M[A, B]
3. ε ∈ PERTAMA(α) dan $ ∈ IKUTI( A), menambahkan A → α Ke M[A, $]
4. Semua sel kosong - kesalahan pada kata masukan

Contoh

Buatlah tabel untuk tata bahasa

• S → sebagai 1
• S 1 → AbBS 1 | ε
• SEBUAH → aA 1 | ε
• A 1 → b | A
• B → c | ε

Hasil:

	A	B	C	$
S	S → sebagai 1 (Aturan pertama, kesimpulan S → aS 1 , a ∈ FIRST(aS 1))	Kesalahan (Aturan keempat)	Kesalahan (Aturan keempat)	Kesalahan (Aturan keempat)
S 1	S 1 → AbBS 1 (Aturan pertama, keluaran S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S 1 → AbBS 1 (Aturan pertama, keluaran S 1 → AbBS 1 , b ∈ FIRST(AbBS 1))	Kesalahan (Aturan keempat)	S 1 → ε (Aturan ketiga, kesimpulan S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1))
A	SEBUAH → aA 1 (Aturan pertama, keluaran A → aA 1 , a ∈ FIRST(aA 1))	SEBUAH → ε (Aturan kedua, keluaran A 1 → ε, b ∈ IKUTI(A 1))	Kesalahan (Aturan keempat)	Kesalahan (Aturan keempat)
Sebuah 1	SEBUAH 1 → sebuah (Aturan pertama, kesimpulan A 1 → a, a ∈ PERTAMA(a))	SEBUAH 1 → b (Aturan pertama, keluaran A 1 → b, b ∈ PERTAMA(b))	Kesalahan (Aturan keempat)	Kesalahan (Aturan keempat)
B	B → ε	B → ε (Aturan kedua, kesimpulan B → ε, a ∈ IKUTI(B))	B → c (Aturan pertama, kesimpulan B → c, c ∈ PERTAMA(c))	B → ε (Aturan ketiga, kesimpulan B → ε, $ ∈ IKUTI(B))

Mengurai string

Proses parsing string cukup sederhana. Esensinya adalah sebagai berikut: pada setiap langkah karakter teratas dibaca ay C rantai masukan.

• Jika ay- karakter terminal
  • Jika ay bertepatan dengan Dengan, lalu keduanya musnah, terjadilah pergeseran
  • Jika ay tidak cocok Dengan, maka kesalahan parse ditandai
• Jika ay- simbol non-terminal, C kembali ke awal baris sebagai gantinya ay sisi kanan aturan, yang diambil dari sel tabel, dikembalikan ke tumpukan M[ay, C]

Proses berakhir ketika garis dan tumpukan telah mencapai penanda akhir (#).

Contoh

Mari kita parsing string "aabbaabcb":

tumpukan	garis	tindakan
S#	A abbabcb$	S → sebagai 1
A S 1#	A abbabcb$	menggeser
S 1#	A bbaabcb$	S 1 → AbBS 1
A bBS 1#	A bbaabcb$	SEBUAH → aA 1
A A 1 bBS 1#	A bbaabcb$	menggeser
Sebuah 1 bBS 1#	B baabcb$	SEBUAH 1 → b
B bBS 1#	B baabcb$	menggeser
B BS 1#	B aabcb$	menggeser
B S 1#	A abcb$	B → ε
S 1#	A abcb$	S 1 → AbBS 1
A bBS 1#	A abcb$	SEBUAH → aA 1
A bBS 1#	A abcb$	SEBUAH → aA 1
A A 1 bBS 1#	A abcb$	menggeser
Sebuah 1 bBS 1#	A bcb$	SEBUAH 1 → sebuah
A bBS 1#	A bcb$	menggeser
B BS 1#	B cb$	menggeser
B S 1#	C menjadi$	B → c
C S 1#	C menjadi$	menggeser
S 1#	B$	S 1 → AbBS 1
A bBS 1#	B$	SEBUAH → ε
B BS 1#	B$	menggeser
B S 1#	$	B → ε
S 1#	$	S 1 → ε
#	$	siap

Membangun penganalisis LR(k).

Perhitungan k dalam LR(k)

Tidak ada algoritme yang memungkinkan seseorang menghitung k dalam kasus umum untuk tata bahasa arbitrer. Biasanya ada baiknya mencoba membuat parser LR(1). Jika tidak lebih dari satu operasi untuk setiap set (Shift, Reduce atau Accept), maka tata bahasanya adalah LR(0). Jika konflik dan benturan muncul saat membuat penganalisis LR(1), maka tata bahasa ini bukan LR(1) dan patut dicoba untuk membuat LR(2). Jika tidak memungkinkan untuk membangunnya, maka LR(3) dan seterusnya.

Pengisian ulang tata bahasa

Mari tambahkan aturan baru S" → S, dan jadikan S" sebagai aksioma tata bahasa. Aturan tambahan ini diperlukan untuk menentukan kapan penganalisis dihentikan dan kapan string input diizinkan. Toleransi terjadi jika dan hanya jika dimungkinkan untuk melakukan konvolusi menurut aturan S → S."

Konstruksi sistem kanonik dari kumpulan situasi LR(1) yang dapat diterima

Pada awalnya ada himpunan I 0 dengan konfigurasi penganalisis S" → .S, $. Selanjutnya, operasi penutupan diterapkan pada konfigurasi ini hingga, sebagai hasil penerapannya, tidak ada lagi konfigurasi baru yang ditambahkan. Selanjutnya, transisi ke himpunan baru dibangun dengan menggeser titik sebanyak satu karakter ke kanan (transisi dilakukan sepanjang karakter yang berdiri setelah titik sebelum transisi dan sebelum setelah transisi), dan konfigurasi yang diperoleh dari yang sudah ada di ini cara ditambahkan ke himpunan ini. Bagi mereka, operasi penutupan juga diterapkan, dan seluruh proses diulang sampai tidak ada lagi himpunan baru yang muncul.

Contoh

Buatlah sistem kanonik dari kumpulan situasi LR(1) yang dapat diterima untuk tata bahasa tertentu:

• S" → S
• S → ABA
• SEBUAH → Aa | ε
• B → cBc | D

Larutan:

• Kami membuat penutupan untuk konfigurasi S" → .S, $:
  • S → .ABA, $
• Untuk konfigurasi yang dihasilkan (S → .ABA, $) kami juga membuat penutupan:
  • SEBUAH → .Aa, c
  • A → .Aa, d
  • SEBUAH → ., c
  • SEBUAH → ., d
• Untuk konfigurasi yang dihasilkan (A → .Aa, c; A → .Aa, d) kami juga membuat penutupan:
  • SEBUAH → .Aa, a
  • SEBUAH → ., sEBUAH
• Tidak mungkin untuk membuat lebih banyak konfigurasi di status I 0 - penutupan telah dibuat

• Dari I 0 Anda dapat melakukan transisi sepanjang S dan A dan mendapatkan sekumpulan konfigurasi I 1 dan I 2, yang terdiri dari elemen-elemen berikut:
  • Saya 1 = (S" → S., $)
  • Saya 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 tidak memerlukan penutupan
• Mari kita buat penutupan I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B→.d, a
  • B → .d, $
• Semua set lainnya dibuat dengan cara yang sama.

Membangun tabel penganalisis

Tahap terakhir dalam membangun penganalisis LR(1) adalah membuat tabel Tindakan Dan Pergi ke. Meja Tindakan dibuat untuk karakter jalur masukan, yaitu untuk terminal dan penanda akhir jalur $, tabel Pergi ke dibangun untuk simbol tata bahasa, yaitu untuk terminal dan non-terminal.

Membangun Tabel Goto

Tabel Goto menunjukkan keadaan yang harus dituju ketika menemukan simbol tata bahasa berikutnya. Oleh karena itu, jika dalam sistem himpunan kanonik terjadi transisi dari saya saya V aku j dengan simbol A, lalu di Goto( SAYA Saya, A) kami menempatkan negara bagian SAYA J. Setelah mengisi tabel, kami berasumsi bahwa di semua sel kosong Goto( SAYA Saya, A) = Kesalahan

Membangun tabel Tindakan

• Jika terjadi peralihan melalui terminal a dari keadaan I i ke keadaan I j, maka Aksi(I i, a) = Shift(I j)
• Jika A ≠ S" dan terdapat konfigurasi A → α., a, maka Aksi(I i , a) = Kurangi(A → α)
• Untuk keadaan I i yang didalamnya terdapat konfigurasi S" → S., $, Action(I i, $) = Accept
• Untuk semua sel kosong Tindakan(I i , a) = Error

Contoh

Buat tabel Action dan Goto untuk tata bahasa

• S" → S
• S → ABA
• SEBUAH → Aa | ε
• B → cBc | D

Larutan:

	Tindakan				Pergi ke
	A	C	D	$	S	S"	A	B	A	C	D
saya 0	Kurangi (A → ε)	Kurangi (A → ε)	Kurangi (A → ε)		saya 1		saya 2
saya 1				Menerima
saya 2	Pergeseran(I 6)	Pergeseran(I 4)	Pergeseran(I 5)					saya 3	saya 6	saya 4	saya 5
saya 3	Kurangi (A → ε)			Kurangi (A → ε)			saya 13
saya 4		Pergeseran(I 8)	Pergeseran(I 9)					saya 7		saya 8	saya 9
saya 5	Kurangi (B → d)			Kurangi (B → d)
saya 6	Kurangi (A → Aa)	Kurangi (A → Aa)	Kurangi (A → Aa)
saya 7		Pergeseran(I 10)								saya 10
saya 8		Pergeseran(I 8)	Pergeseran(I 9)					saya 11		saya 8	saya 9
saya 9		Kurangi (B → d)
saya 10	Kurangi (B → cBc)			Kurangi (B → cBc)
saya 11		Pergeseran(I 12)								saya 12
saya 12		Kurangi (B → cBc)
saya 13	Pergeseran(I 14)			Kurangi (S → ABA)					saya 14
saya 14	Kurangi (A → Aa)			Kurangi (A → Aa)

Mengurai rantai

Pada setiap langkah, karakter teratas dibaca ay dari tumpukan penganalisis dan mengambil karakter terakhir C rantai masukan.

Jika dalam tabel tindakan di persimpangan ay Dan C terletak:

• Menggeser( saya k), kemudian dimasukkan ke dalam tumpukan Dengan kemudian saya k. Di mana C dihapus dari garis.
• mengurangi( A → kamu), lalu semua simbol terminal dan non-terminal yang membentuk rantai dibersihkan dari atas tumpukan kamu, setelah itu negara bagian melihat Aku, tetap di atas. Menurut tabel transisi di persimpangan Aku Dan A keadaan berikut ditemukan Adalah. Setelah itu A didorong ke tumpukan, dan kemudian Adalah. Garisnya tetap tidak berubah.
• Terima, maka analisis selesai
• kekosongan - kesalahan

Contoh

Mari kita parsing string aaaccdcc:

Tumpukan	Garis	Tindakan
saya 0	A aaccdcc$	Kurangi (A → ε), lanjutkan ke I 2
saya 0 A saya 2	A aaccdcc$	Pergeseran(I 6)
Saya 0 A Saya 2 a saya 6	A accdcc$	Kurangi (A → Aa), lanjutkan ke I 2
saya 0 A saya 2	A accdcc$	Pergeseran(I 6)
Saya 0 A Saya 2 a saya 6	A ccdcc$	Kurangi (A → Aa), lanjutkan ke I 2
saya 0 A saya 2	A ccdcc$	Pergeseran(I 6)
Saya 0 A Saya 2 a saya 6	C cdcc$	Kurangi (A → Aa), lanjutkan ke I 2
saya 0 A saya 2	C cdcc$	Pergeseran(I 4)
saya 0 A saya 2c saya 4	C dcc$	Pergeseran(I 8)
Saya 0 A Saya 2 c Saya 4 c saya 8	D cc$	Pergeseran(I 9)
saya 0 A saya 2 c saya 4 c saya 8 d saya 9	C c$	Kurangi(B → d), pergi ke I 11
Saya 0 A Saya 2 c Saya 4 c Saya 8 B saya 11	C c$	Pergeseran(I 12)
Saya 0 A Saya 2 detik Saya 4 detik Saya 8 B Saya 11 detik saya 12	C$	Kurangi (B → cBc), ke I 7
Saya 0 A Saya 2 c Saya 4 B saya 7	C$	Pergeseran(I 10)
Saya 0 A Saya 2 detik dan 4 B Saya 7 detik saya 10	$	Kurangi (B → cBc), lanjutkan ke I 3
Saya 0 A Saya 2 B saya 3	$	Kurangi (A → ε), lanjutkan ke I 13
Saya 0 A Saya 2 B Saya 3 A saya 13	$	Kurangi (S → ABA), masuk ke I 1
saya 0 S saya 1	$	Menerima

Terjemahan ekspresi aritmatika (algoritma Set-Ullman)

Catatan. Kode tersebut dihasilkan oleh doggy style seperti Motorola

Op Arg1, Arg2

berdiri untuk

Arg2 = Arg1 Op Arg2

Membangun pohon

Pohon dibangun seperti biasa untuk ekspresi aritmatika: Di akar adalah operasi dengan prioritas terendah, diikuti oleh operasi dengan prioritas sedikit lebih tinggi, dan seterusnya. Tanda kurung memiliki prioritas tertinggi. Jika ada beberapa operasi dengan prioritas yang sama - a op b op c, maka pohon dibangun untuk ekspresi (a op b) op c.

Contoh

Buatlah pohon untuk ekspresi a + b / (d + a − b × c / d − e) + c × d

Larutan: Mari kita tuliskan ekspresi dalam bentuk

((a) + ((b) / ((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × ( D))

Kemudian akan ada operasi pada akar setiap subpohon, dan ekspresi dalam tanda kurung di kiri dan kanannya akan menjadi subpohonnya. Misalnya, untuk subekspresi ((b) × (c)) / (d), akar dari subpohon yang bersangkutan akan memiliki operasi “/”, dan subpohonnya akan menjadi subekspresi ((b) × (c)) dan (d).

Tata letak pohon (menghitung jumlah register)

• Jika simpulnya adalah daun kiri (yaitu variabel), maka kita tandai dengan nol.
• Jika titik puncaknya adalah daun sebelah kanan, maka kita tandai dengan satu
• Jika kita sudah menandai kedua subpohonnya untuk sebuah simpul, maka kita menandainya sebagai berikut:
  • Jika subpohon kiri dan kanan ditandai dengan angka yang berbeda, maka pilihlah yang terbesar
  • Jika subpohon kiri dan kanan diberi label dengan angka yang sama, maka kita mengasosiasikan dengan subpohon tersebut suatu angka yang satu lebih besar dari angka yang diberi label pada subpohon tersebut.

Penandaan daun	Menandai pohon dengan subpohon yang identik	Subpohon kiri ditandai dengan angka besar	Subpohon sebelah kanan ditandai dengan angka besar

Kanan - sama, seperti nenek moyang.

Jika labelnya kiri keturunan lagi tag Kanan, Itu Kanan anak itu diberi register satu lagi dari nenek moyang, dan kiri - sama, seperti nenek moyang.

Kode dihasilkan dengan menelusuri pohon dari bawah ke atas sebagai berikut:

1. Untuk simpul dengan label 0, kode tidak dihasilkan

2. Jika simpulnya adalah lembar X dengan label 1 dan register R Saya, lalu kode tersebut dicocokkan dengannya

PINDAHKAN X, Ri

3. Jika simpulnya internal dengan register R Saya dan anak kirinya adalah sheet X dengan label 0, maka kodenya sesuai

<Код правого поддерева>Op X, Ri

4. Jika subpohon dari simpul dengan register R Saya- tidak daun dan label simpul kanan lebih besar atau sama dengan label simpul kiri (yang mempunyai register Rj, j = i + 1), maka kode tersebut sesuai dengan simpul tersebut

<Код Kanan subpohon><Код kiri subpohon>Op Rj, Ri

5. Jika subpohon dari simpul dengan register R Saya- tidak daun dan label simpul sebelah kanan (yang register Rj, j = i + 1) lebih kecil dari label simpul kiri, maka kode tersebut sesuai dengan simpul tersebut

Distribusi register ditunjukkan pada grafik di sebelah kanan. Kode yang dihasilkan:

PINDAHKAN d, R0 ;R0 = d PINDAH c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d PINDAHKAN a, R1 ;R1 = a TAMBAHKAN d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) PINDAHKAN e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + d) − ((b × c) / d)) − e PINDAHKAN R1, R0;R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − ((b × c) / d)) − e) TAMBAHKAN a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) PINDAHKAN d, R1 ;R1 = d MUL c, R1 ;R1 = c × d TAMBAHKAN R0, R1 ;R1 = (a + (b / (((a + d) − ((b × c ) / d)) − e))) + (c × d) PINDAHKAN R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e) )) + (c×d)

Terjemahan ekspresi logis

Bagian ini menunjukkan cara membuat kode untuk mengevaluasi ekspresi Boolean dengan malas. Hasil dari algoritma ini adalah sepotong kode yang, menggunakan operasi TST, BNE, BEQ, menghitung ekspresi logika dengan masuk ke salah satu label: TRUELAB atau FALSELAB.

Membangun pohon

Pohon ekspresi logis mencerminkan urutan evaluasinya sesuai dengan prioritas operasi, yaitu untuk mengevaluasi nilai dari node pohon tertentu (yang merupakan operasi pada dua operan yang merupakan subpohon dari node), kita harus pertama-tama evaluasi nilai subpohonnya.

Prioritas operasi: Operasi NOT mempunyai prioritas tertinggi, diikuti oleh AND, dan kemudian OR. Jika ekspresi menggunakan yang lain operasi logis maka ketiganya harus diekspresikan melalui ketiganya dengan cara tertentu (biasanya, tidak ada operasi lain dan tidak diperlukan transformasi ekspresi). Asosiatif untuk operasi dengan prioritas yang sama adalah dari kiri ke kanan, yaitu A dan B dan C dianggap sebagai (A dan B) dan C

Contoh

Buatlah pohon untuk ekspresi logika bukan A atau B dan C dan (B atau bukan C).

Larutan: lihat diagram di sebelah kanan.

Untuk setiap simpul pohon, 4 atribut dihitung:

• Nomor simpul
• Beri label ke mana harus pergi jika ekspresi dalam node salah (label salah, fl)
• Beri label ke mana harus pergi jika ekspresi di node benar (label benar, tl)
• Tanda tangan (lihat di bawah untuk lebih jelasnya)

Node diberi nomor dalam urutan apa pun; satu-satunya syarat adalah nomor nodenya unik.

Pohon itu ditandai sebagai berikut:

• fl menunjukkan nomor simpul tempat transisi dilakukan, atau falselab jika simpul ini salah
• tl menunjukkan nomor simpul tempat transisi dilakukan atau truelab jika simpul ini benar

Tanda menunjukkan kapan harus berhenti menghitung subpohon saat ini.

Untuk akar pohon fl=falselab, tl=truelab, tanda=false.

Dengan demikian:

Contoh

Beri label pohon yang dibuat untuk ekspresi logika bukan A atau B dan C dan (B atau bukan C).

Pembuatan kode

Perintah mesin yang digunakan dalam kode yang dihasilkan:

• TST - memeriksa kebenaran argumen dan memasang tanda jika argumen salah
• BNE - transisi berdasarkan label jika flag tidak disetel, yaitu kondisi diperiksa menggunakan TST BENAR
• BEQ - transisi berdasarkan label jika flag disetel, yaitu kondisi yang diperiksa menggunakan TST PALSU

Kode ini dibuat sebagai berikut:

• pohon dilintasi dari akar, untuk AND dan OR subpohon kiri dilintasi terlebih dahulu, kemudian subpohon kanan
• Untuk setiap simpul yang dilewati, nomornya (label) dicetak
• untuk lembar A(nomor, tl, fl, tanda) TST A dicetak
  • jika tanda == benar, BNE tl dicetak
  • jika tanda == salah, BEQ fl dicetak

Contoh

Untuk ekspresi yang dibahas di atas, kode berikut akan dihasilkan:

1:2:4 : TST A BEQ TRUELAB 3:5:7 : TST B BEQ FALSELAB 8 : TST C BEQ FALSELAB 6:9 : TST B BNE TRUELAB 10:11 : TST C BNE FALSELAB BENAR : FALSELAB :

Metode pencocokan pola

Ide dari metode ini adalah bahwa untuk bagian program yang sama, kode dapat dihasilkan dengan cara yang berbeda, dan sebagai hasilnya, optimasi dapat dicapai untuk parameter tertentu.

Rumusan masalah

Ada banyak sampel, yang masing-masing merupakan bagian dari representasi perantara yang dapat diterapkan, bobot, dan kode yang dihasilkan ditentukan. Ada pohon representasi perantara, yang merupakan bagian dari program yang kodenya perlu dibuat. Tujuannya adalah untuk membuat penutup pohon representasi perantara dengan sampel sedemikian rupa sehingga bobot total sampel menjadi minimal.

Sampel adalah instruksi perakitan dan penguraian pohon yang sesuai dengannya. Untuk setiap sampel, waktu eksekusi (dalam siklus jam) diketahui. Dengan bantuan mereka, kami akan menghasilkan kode yang optimal (dalam hal waktu eksekusi).

Contoh sampel

Membangun representasi perantara

Pertama, kita membuat pohon parse untuk keseluruhan ekspresi.

Konstruksi cakupan

Sekarang untuk setiap simpul (kita mengurutkannya dari daun hingga akar) kita akan menghasilkan kode optimal untuk subpohonnya. Untuk melakukan ini, kita cukup memeriksa semua sampel yang berlaku di titik ini. Waktu eksekusi saat menggunakan sampel tertentu akan menjadi jumlah waktu penghitungan argumennya (dan kita sudah mengetahui kode optimal untuk menghitungnya berkat urutan traversal pohon) dan waktu eksekusi sampel itu sendiri. Dari semua opsi yang diterima, kami memilih yang terbaik - ini akan menjadi kode optimal untuk subpohon node ini. Di akar pohon kita mendapatkan kode optimal untuk keseluruhan ekspresi.

Pembuatan kode

Tidak perlu menuliskan kode untuk semua simpul - cukup menuliskan waktu minimum yang diperlukan dan sampel yang perlu digunakan. Segala sesuatu yang lain dari ini dapat dengan mudah dipulihkan.

Dalam tugas ini kami memiliki jumlah register yang tidak terbatas, sehingga Anda dapat menggunakan register baru setiap saat.

Pembangunan RT menggunakan DKA

Konstruksi NFA menggunakan tata bahasa linier kanan

Membawa tata bahasa

Untuk mengonversi tata bahasa KS arbitrer ke bentuk tertentu, Anda harus melakukan langkah-langkah berikut:

• hapus semua karakter yang tidak membuahkan hasil;
• hapus semua karakter yang tidak dapat dijangkau;

Menghapus karakter yang tidak berguna

Pintu masuk: Tata bahasa KS G = (T, N, P, S).

KELUAR: Tata bahasa KS G’ = (T, N’, P’, S), tidak mengandung simbol steril, sehingga L(G) = L(G’).

Metode:

Kami secara rekursif membangun himpunan N 0, N 1, ...

1. N 0 = ∅, saya = 1.
2. N i = (A | (A → α) ∈ P dan α ∈ (N i - 1 ∪ T)*) ∪ N i-1 .
3. Jika N i ≠ N i - 1, maka i = i + 1 dan lanjutkan ke langkah 2, jika tidak, N’ = N i; P' terdiri dari aturan-aturan himpunan P yang hanya berisi simbol-simbol dari N' ∪ T; G' = (T, N', P', S).

Definisi: suatu simbol x ∈ (T ∪ N) dikatakan tidak terjangkau dalam tata bahasa G = (T, N, P, S) jika tidak muncul dalam bentuk kalimat apa pun dari tata bahasa tersebut.

Contoh

Hapus karakter yang tidak berguna dari tata bahasa G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

• S → AcDe | CaDbCe | SaCa | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb | aAc | lih
• D → fCE | ac | dEdAS | ε
• E → ESacD | aec | eFf

Larutan

• N0 = ∅
• N 1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
• N 2 = (B, D, E, C (C → Ebd) )
• N 3 = (B, D, E, C, S (S → aCb) )
• N 4 = (B, D, E, C, S) = N 3

G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | SaCa | aCb
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Menghapus karakter yang tidak dapat dijangkau

Pintu masuk: Tata bahasa KS G = (T, N, P, S)

KELUAR: Tata bahasa KS G’ = (T’, N’, P’, S), tidak mengandung simbol-simbol yang tidak dapat dijangkau, sehingga L(G) = L(G’).

Metode:

1. V 0 = (S); saya = 1.
2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P dan A ∈ V i - 1 ) ∪ V i-1 .
3. Jika V i ≠ V i - 1, maka i = i + 1 dan lanjutkan ke langkah 2, jika tidak, N’ = V i ∩ N; T’ = V i ∩ T; P' terdiri dari aturan-aturan himpunan P yang hanya berisi simbol-simbol dari V i ; G' = (T', N', P', S).

Definisi: Suatu KS-tata bahasa G dikatakan tereduksi apabila tidak mengandung simbol-simbol yang tidak terjangkau dan steril.

Contoh

Hapus karakter yang tidak dapat dijangkau dari tata bahasa G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | SaCa | aCb
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Larutan

• V 0 = (S)
• V 1 = (S, C (S → CaDbCe), D (S → CaDbCe), a (S → CaDbCe), b (S → CaDbCe), e (S → CaDbCe) )
• V 2 = (S, C, D, a, b, e, E (C → Ebd), d (C → Ebd), f (D → fCE) )
• V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
• V 4 = (S, C, D, E, a, b, d, e, f, c) = V 3

G""((C, D, E, S), (a, b, c, d, e, f), P"", S)

• S → CaDbCe | SaCa | aCb
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Kembali