Apa hierarki basa Chomsky lan kepiye klasifikasi gramatika formal adhedhasar kekuwatan generatif?

/ / Published in Cybersecurity, EITC/IS/CCTF Computational Complexity Theory Fundamentals, Konteks Basa Sensitif, Hierarki Chomsky lan Basa Sensitif Konteks, Review ujian

Hierarki basa Chomsky minangka sistem klasifikasi sing nggolongake tata basa formal adhedhasar kekuwatan generatif. Iki diusulake dening Noam Chomsky, ahli linguistik lan ilmuwan komputer sing misuwur, ing taun 1950-an. Hierarki kasusun saka patang tingkat, saben makili kelas basa formal sing beda. Tingkat kasebut dikenal minangka Tipe-3 (Reguler), Tipe-2 (Bebas Konteks), Tipe-1 (Sensitif Konteks), lan Tipe-0 (Tanpa Watesan).

Ing tingkat paling ngisor saka hirarki, kita duwe basa Tipe-3, uga dikenal minangka basa Reguler. Basa-basa kasebut bisa diakoni kanthi otomatis winates, kayata automata winates deterministik lan non-deterministik. Basa reguler ditondoi kanthi ekspresi reguler lan gramatika reguler. Ekspresi reguler yaiku ekspresi aljabar sing nggambarake pola senar, dene tata basa reguler kalebu aturan produksi sing ngasilake senar ing basa biasa. Conto basa reguler yaiku kumpulan kabeh senar sing cocog karo ekspresi reguler sing diwenehake, kayata basa kabeh senar biner kanthi nomer genap 0s.

Ngalih munggah hirarki, kita nemoni basa Tipe-2, uga dikenal minangka basa Konteks-Bebas. Basa kasebut bisa dikenali kanthi otomatis pushdown, yaiku otomatis otomatis sing ditambah karo tumpukan. Basa Konteks-Free diterangake dening grammar konteks-free, kang kasusun saka aturan produksi sing generate strings ing basa konteks-free. Tata basa Konteks-Free duwe simbol non-terminal, simbol terminal, lan aturan produksi sing nemtokake carane non-terminal bisa diganti dening urutan simbol. Conto basa tanpa konteks yaiku kumpulan kabeh ekspresi aritmetika sing kawangun kanthi apik, ing ngendi tanda kurung diimbangi lan operator ditrapake kanthi bener.

Tingkat hirarki sabanjure yaiku basa Tipe-1, uga dikenal minangka basa Konteks-Sensitif. Basa-basa kasebut bisa diakoni kanthi automata sing diwatesi linier, yaiku automata sing winates kanthi tape sing bisa pindhah ing loro arah. Basa Sensitif Konteks diterangake kanthi grammar sing sensitif konteks, sing kalebu aturan produksi sing ngasilake string ing basa sensitif konteks. Grammar Konteks-Sensitif duwe watesan tambahan yen dawa sisih tengen aturan produksi ora bisa luwih cendhek tinimbang dawa sisih kiwa. Conto basa sing sensitif konteks yaiku kumpulan kabeh palindrom, ing ngendi senar maca maju lan mundur sing padha.

Pungkasan, ing ndhuwur hirarki, kita duwe basa Tipe-0, uga dikenal minangka basa sing ora diwatesi. Basa kasebut bisa diakoni dening mesin Turing, yaiku piranti komputasi abstrak sing bisa nyimulake algoritma komputer apa wae. Basa sing ora diwatesi diterangake dening tata basa sing ora diwatesi, sing ora ana watesan babagan aturan produksi. Conto basa sing ora diwatesi yaiku kumpulan kabeh basa sing bisa dietung kanthi rekursif, sing kalebu kabeh basa sing bisa diitung.

Hirarki basa Chomsky nyedhiyakake kerangka sistematis kanggo nggolongake tata basa formal adhedhasar kekuwatan generatif. Diwiwiti nganggo basa reguler, sing paling ora kuat, lan maju menyang basa sing bebas konteks, sensitif konteks, lan ora diwatesi, sing tambah kuat. Hierarki iki minangka konsep dhasar ing babagan teori kompleksitas komputasi lan nduweni implikasi penting kanggo sinau basa formal lan automata.

Pitakonan lan jawaban anyar liyane babagan Hierarki Chomsky lan Basa Sensitif Konteks:

Pitakon lan jawaban liyane:

Diwenehi miturut: , , , , , , , , , , ,