Chomsky hijerarhija jezika je klasifikacioni sistem koji kategoriše formalne gramatike na osnovu njihove generativne moći. Predložio ga je Noam Chomsky, poznati lingvista i informatičar, 1950-ih. Hijerarhija se sastoji od četiri nivoa, od kojih svaki predstavlja različitu klasu formalnih jezika. Ovi nivoi su poznati kao Tip-3 (običan), Tip-2 (bez konteksta), Tip-1 (osetljiv na kontekst) i Tip-0 (neograničen).
Na najnižem nivou hijerarhije imamo jezike tipa 3, takođe poznate kao regularni jezici. Ovi jezici se mogu prepoznati pomoću konačnih automata, kao što su deterministički i nedeterministički konačni automati. Regularne jezike karakterišu regularni izrazi i regularne gramatike. Regularni izrazi su algebarski izrazi koji opisuju obrasce nizova, dok se regularne gramatike sastoje od pravila proizvodnje koja generiraju nizove u regularnom jeziku. Primjer regularnog jezika je skup svih stringova koji odgovaraju datom regularnom izrazu, kao što je jezik svih binarnih stringova s parnim brojem 0.
Krećući se gore po hijerarhiji, susrećemo se sa jezicima tipa 2, takođe poznatim kao jezici bez konteksta. Ovi jezici se mogu prepoznati pomoću automata za spuštanje, koji su konačni automati uvećani stekom. Jezici bez konteksta su opisani gramatikama bez konteksta, koje se sastoje od pravila proizvodnje koja generiraju nizove na jeziku bez konteksta. Gramatike bez konteksta imaju neterminalne simbole, terminalne simbole i pravila proizvodnje koja određuju kako se neterminalni elementi mogu zamijeniti nizom simbola. Primjer jezika bez konteksta je skup svih dobro oblikovanih aritmetičkih izraza, gdje su zagrade izbalansirane i operatori se pravilno primjenjuju.
Sledeći nivo hijerarhije su jezici tipa 1, takođe poznati kao jezici osetljivi na kontekst. Ovi jezici se mogu prepoznati po linearno ograničenim automatima, koji su konačni automati sa trakom koja se može kretati u oba smjera. Kontekstno osjetljivi jezici opisuju se gramatikama osjetljivim na kontekst, koje se sastoje od pravila proizvodnje koja generiraju nizove na kontekstualno osjetljivom jeziku. Gramatike osetljive na kontekst imaju dodatno ograničenje da dužina desne strane pravila proizvodnje ne može biti kraća od dužine leve strane. Primjer kontekstno osjetljivog jezika je skup svih palindroma, gdje niz čita isto naprijed i nazad.
Konačno, na vrhu hijerarhije imamo jezike tipa 0, takođe poznate kao neograničeni jezici. Ove jezike mogu prepoznati Turingove mašine, koje su apstraktni računarski uređaji sposobni da simuliraju bilo koji kompjuterski algoritam. Neograničeni jezici su opisani neograničenim gramatikama, koje nemaju ograničenja na pravila proizvodnje. Primjer neograničenog jezika je skup svih rekurzivno nabrojivih jezika, koji uključuje sve izračunljive jezike.
Chomsky hijerarhija jezika pruža sistematski okvir za klasifikaciju formalnih gramatika na osnovu njihove generativne moći. Počinje s regularnim jezicima, koji su najmanje moćni, i napreduje do kontekstno slobodnih, kontekstualno osjetljivih i neograničenih jezika, koji su sve moćniji. Ova hijerarhija je fundamentalni koncept u polju teorije računske složenosti i ima važne implikacije za proučavanje formalnih jezika i automata.
Ostala nedavna pitanja i odgovori u vezi Chomsky hijerarhija i jezici osjetljivi na kontekst:
- Šta znači da je jedan jezik moćniji od drugog?
- Postoje li trenutne metode za prepoznavanje tipa-0? Očekujemo li da će kvantni kompjuteri to učiniti izvodljivim?
- Opišite proces dizajniranja kontekstualno osjetljive gramatike za jezik koji se sastoji od nizova s jednakim brojem jedinica, dvojki i trojki.
- Navedite primjer kontekstno osjetljivog jezika i objasnite kako ga može prepoznati kontekstualno osjetljiva gramatika.
- Kako se jezici tipa 0, poznati i kao jezici s rekurzivnim nabrajanjem, razlikuju od drugih tipova jezika u smislu računske složenosti?
- Objasnite razliku između jezika bez konteksta i jezika osjetljivih na kontekst u smislu pravila koja regulišu njihovo formiranje.