Jezici bez konteksta i jezici osjetljivi na kontekst dvije su kategorije formalnih jezika u teoriji računalne složenosti. Ti su jezici definirani pravilima koja upravljaju njihovim oblikovanjem, a razumijevanje razlika među njima važno je za proučavanje njihovih svojstava i primjena u raznim područjima kao što je kibernetička sigurnost.
Jezik bez konteksta je vrsta formalnog jezika koji se može generirati pomoću gramatike bez konteksta. Gramatika bez konteksta sastoji se od skupa proizvodnih pravila, gdje svako pravilo specificira kako se neterminalni simbol može zamijeniti nizom simbola. Ključna karakteristika gramatike bez konteksta je da se lijeva strana svakog produkcijskog pravila sastoji od samo jednog neterminalnog simbola. To znači da se zamjena neterminalnog simbola može dogoditi u bilo kojem kontekstu, bez ikakvih ograničenja nametnutih okolnim simbolima.
Na primjer, razmotrite gramatiku G bez konteksta s pravilima proizvodnje:
S -> aSb
S -> ε
Ova gramatika generira jezik bez konteksta L(G) = {anbn | n >= 0}, koji predstavlja skup svih nizova koji se sastoje od 'a' iza kojeg slijedi isti broj 'b'. U ovom slučaju, neterminalni simbol S može se zamijeniti s 'aSb' ili praznim nizom ε, bez obzira na kontekst u kojem se pojavljuje.
S druge strane, kontekstno osjetljiv jezik je izražajniji tip formalnog jezika koji se može generirati kontekstno osjetljivom gramatikom. Kontekstno osjetljiva gramatika sastoji se od skupa proizvodnih pravila, gdje svako pravilo navodi kako se niz simbola može zamijeniti drugim nizom simbola, ovisno o određenim uvjetima konteksta. Kontekstni uvjeti definirani su prisutnošću specifičnih simbola ili nizova simbola u okolnom kontekstu.
Formalno, kontekstno osjetljiva gramatika ima pravila oblika αXβ -> αγβ, gdje su α i β nizovi simbola, X je neterminalni simbol, a γ je niz simbola koji može zamijeniti X u kontekstu navedenom s α i β. Uvjeti konteksta mogu biti proizvoljni, sve dok se mogu izraziti simbolima u α i β.
Na primjer, razmotrite kontekstno osjetljivu gramatiku G' s pravilima proizvodnje:
S -> aSb
Sa -> aS
bS -> Sb
ε -> ε
Ova gramatika generira kontekstno osjetljiv jezik L(G') = {anbn | n >= 0}, što je isti jezik kao i prije. Međutim, u ovom slučaju pravila proizvodnje imaju dodatne uvjete konteksta. Na primjer, pravilo Sa -> aS navodi da se neterminalni simbol S može zamijeniti s 'aS' samo ako mu prethodi 'S'. Slično, pravilo bS -> Sb specificira da se neterminalni simbol S može zamijeniti sa 'Sb' samo ako iza njega slijedi 'S'. Ovi uvjeti konteksta ograničavaju moguće zamjene za neterminalni simbol S, čineći jezik osjetljivim na kontekst.
Glavna razlika između kontekstno slobodnih jezika i kontekstno osjetljivih jezika leži u pravilima koja upravljaju njihovim oblikovanjem. Kontekstno slobodni jezici mogu se generirati kontekstno slobodnim gramatikama, gdje zamjena neterminalnih simbola nije ograničena okolnim kontekstom. S druge strane, jezici osjetljivi na kontekst zahtijevaju gramatike osjetljive na kontekst, gdje zamjena neterminalnih simbola podliježe određenim uvjetima konteksta.
Ostala nedavna pitanja i odgovori u vezi Chomsky hijerarhija i jezici osjetljivi na kontekst:
- Što znači da je jedan jezik moćniji od drugog?
- Postoje li trenutačne metode za prepoznavanje tipa 0? Očekujemo li da će kvantna računala to učiniti izvedivim?
- Opišite proces dizajniranja kontekstno osjetljive gramatike za jezik koji se sastoji od nizova s jednakim brojem jedinica, dvojki i trica.
- Navedite primjer kontekstno osjetljivog jezika i objasnite kako ga kontekstno osjetljiva gramatika može prepoznati.
- Kako se jezici tipa 0, također poznati kao rekurzivno prebrojivi jezici, razlikuju od drugih vrsta jezika u smislu računske složenosti?
- Što je Chomskyjeva hijerarhija jezika i kako klasificira formalne gramatike na temelju njihove generativne moći?