Kontekst-senzitivni jezik

U teorijskom računarstvu, kontekst-senzitivan jezik je formalni jezik koji može da se definiše kontekst-senzitivnom gramatikom. To je jedna od četiri tipa gramatika u Hijerarhiji Čomskog. Od njih četiri, ova gramatika se najređe koristi, i u teoriji i u praksi.

Računska svojstva

Računski, kontekstno-senzitivni jezici su ekvivalentni sa linerno ograničenim nedeterminističkim Tjuringovim mašinama, koje se nazivaju još i linearno ograničenim automatima. To je nedeterministička Tjuringova mašina sa trakom koja ima samo kn ćelija, gde je n veličina ulaza, a k je konstanta vezana za mašinu. Ovo znači da je svaki formalni jeziik koji može da bude odlučen takvom mašinom kontekstno-senzitivan, i da je svaki kontekstno-senzitivan jezik odlučiv takvom mašinom.

Ovaj skup jezika je takođe poznat kao NLIN-SPACE, jer može da ih prepozna nedeterministička Tjuringova mašina koristeći linearni prostor. Klasa LIN-SPACE se definiše na isti način, osim što se koristi deterministička Tjuringova mašina. Jasno, LIN-SPACE je podskup od NLIN-SPACE, ali nije poznato da li je LIN-SPACE=NLIN-SPACE. Rasprostranjeno je mišljenje da ove dve klase nisu jednake.

Primeri

Primer kontekst-senzitivnog jezika koji nije kontekst-slobodan je L = { a^p : p je prost broj}. Za L se može pokazati da je kontekst-senzitivan konstruisanjem linearno ograničenog automata koji prihvata L. Lako se može pokazati da ovaj jezik nije ni regularan, niti kontekstno-slobodan primenjivanjem odgovarajuće pamping leme za obe klase jezika na L.

Primer rekurzivnog jezika koji nije kontekstno-senzitivan je bilo koji rekurzivan jezik čije je odlučivanje EXPSPACE-težak problem, na primer, skup parova ekvivalentnih regularnih izraza sa eksponentom.

Svojstva kontekstno-senzitivnih jezika

• Unija, presek i konkatenacija dva kontekst-senzitivna jezika je kontekst-senzitivna.
• Komplement kontekstno-senzitivnog jezika je kontekstno-senzitivan.
• Svaki kontekstno-slobodan jezik je kontekstno-senzitivan.
• Pripadnost neke niske jeziku definisanom proizvoljnom kontekstno-senzitivnom gramatikom, ili proizvoljnom determinističkom kontekstno-senzitivnom gramatikom, je PSPACE-комплетан проблем.

Vidi još

• Linearno ograničen automat
• Hijerarhija Čomskog
• Nesažimajuća gramatika
• Indeksirani jezici – strogi podskup kontekstno-senzitivnih jezika

Literatura

• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.

• Immerman, Neil (1988). „Nondeterministic space is closed under complementation” (PDF). SIAM J. Comput. 17 (5): 935—938. doi:10.1137/0217058.