Chomsky kalbų hierarchija yra klasifikavimo sistema, kuri suskirsto formalias gramatikas pagal jų generuojamąją galią. 1950-aisiais jį pasiūlė Noamas Chomsky, žinomas kalbininkas ir informatikas. Hierarchija susideda iš keturių lygių, kurių kiekvienas atstovauja skirtingą formalių kalbų klasę. Šie lygiai žinomi kaip 3 tipas (įprastas), 2 tipas (be konteksto), 1 tipas (kontekstas jautrus) ir 0 tipas (neribotas).
Žemiausiame hierarchijos lygyje turime 3 tipo kalbas, dar žinomas kaip įprastos kalbos. Šias kalbas galima atpažinti pagal baigtinius automatus, tokius kaip deterministiniai ir nedeterministiniai baigtiniai automatai. Įprastoms kalboms būdingi reguliarūs posakiai ir taisyklinga gramatika. Reguliarios išraiškos yra algebrinės išraiškos, apibūdinančios eilučių modelius, o įprastos gramatikos susideda iš gamybos taisyklių, generuojančių eilutes įprasta kalba. Įprastos kalbos pavyzdys yra visų eilučių, atitinkančių nurodytą reguliariąją išraišką, rinkinys, pvz., visų dvejetainių eilučių, kurių lyginis skaičius yra 0, kalba.
Kildami aukštyn hierarchijoje susiduriame su 2 tipo kalbomis, dar vadinamomis kalbomis be konteksto. Šias kalbas galima atpažinti pagal nuspaudimo automatus, kurie yra baigtiniai automatai, papildyti kaminu. Kontekstinės kalbos apibūdinamos bekontekstinėmis gramatikomis, kurias sudaro gamybos taisyklės, generuojančios eilutes nekontekstinėje kalboje. Gramatikos be konteksto turi negalinius simbolius, terminalo simbolius ir gamybos taisykles, kurios nurodo, kaip neterminalus galima pakeisti simbolių seka. Nekontekstinės kalbos pavyzdys yra visų gerai suformuotų aritmetinių išraiškų rinkinys, kur skliaustai yra subalansuoti, o operatoriai taikomi teisingai.
Kitas hierarchijos lygis yra 1 tipo kalbos, taip pat žinomos kaip kontekstui jautrios kalbos. Šias kalbas galima atpažinti pagal linijinius automatus, kurie yra baigtiniai automatai su juostele, galinčia judėti abiem kryptimis. Kontekstui jautrios kalbos apibūdinamos kontekstui jautriomis gramatikomis, kurias sudaro gamybos taisyklės, generuojančios eilutes kontekstui jautria kalba. Kontekstui jautrios gramatikos turi papildomą apribojimą, kad dešiniosios gamybos taisyklės pusės ilgis negali būti trumpesnis už kairiosios pusės ilgį. Kontekstui jautrios kalbos pavyzdys yra visų palindromų rinkinys, kur eilutė skaito tą pačią pirmyn ir atgal.
Galiausiai, hierarchijos viršuje, turime 0 tipo kalbas, dar žinomas kaip Neribotos kalbos. Šias kalbas gali atpažinti Tiuringo mašinos, kurios yra abstraktūs skaičiavimo įrenginiai, galintys imituoti bet kurį kompiuterio algoritmą. Neribotos kalbos aprašomos neapribotomis gramatikomis, kurios neturi jokių apribojimų gamybos taisyklėms. Neribotos kalbos pavyzdys yra visų rekursyviai išvardijamų kalbų rinkinys, apimantis visas skaičiuojamas kalbas.
Chomsky kalbų hierarchija suteikia sistemingą pagrindą formalioms gramatikoms klasifikuoti pagal jų generuojamąją galią. Pradedama nuo įprastų kalbų, kurios yra mažiausiai galingos, ir pereina prie be konteksto, kontekstui jautrių ir neribotų kalbų, kurios tampa vis galingesnės. Ši hierarchija yra pagrindinė skaičiavimo sudėtingumo teorijos sąvoka ir turi svarbių pasekmių formalių kalbų ir automatų tyrimams.
Kiti naujausi klausimai ir atsakymai apie Chomsky hierarchija ir kontekstui jautrios kalbos:
- Ką reiškia, kad viena kalba yra galingesnė už kitą?
- Ar yra dabartinių 0 tipo atpažinimo metodų? Ar tikimės, kad kvantiniai kompiuteriai tai padarys įmanoma?
- Apibūdinkite kontekstui jautrios gramatikos kūrimo procesą kalbai, kurią sudaro eilutės, turinčios vienodą skaičių vienetų, dviejų ir trijų.
- Pateikite kontekstui jautrios kalbos pavyzdį ir paaiškinkite, kaip ją galima atpažinti pagal kontekstui jautrią gramatiką.
- Kuo 0 tipo kalbos, taip pat žinomos kaip rekursyviai išvardijamos kalbos, skiriasi nuo kitų kalbų skaičiavimo sudėtingumo požiūriu?
- Paaiškinkite bekontekstinių kalbų ir kontekstui jautrių kalbų skirtumą pagal jų formavimosi taisykles.