Kontekstno ovisna gramatika: razlika između inačica

Pokazano je da se gotovo svi [[prirodni jezik|prirodni jezici]] mogu općenito opisati kontekstno ovisnim gramatikama, iako međutim izgleda da je cijela klasa kontekstno ovisnih gramatika mnogo veća od klase prirodnih jezika. Još je gora posljedica već spomenute činjenice da jer problem odluke za kontekstno ovisne gramatike PSPACE-potpun, ta da ih to čini potpuno nepraktičnim za uporabu, pošto bi općeniti algoritam zahtijevao eksponencijalno vrijeme. Trenutni istraživački rad u području računalne lingvisitke je fokusiran na formuliranje klasa jezika koje su "umjereno kontekstno ovisne" i čiji su problemi odluke praktično izvodljivi, poput npr. ''tree-adjoining'' gramatike, ''coupled'' kontekstno slobodnih jezika i tzv. ''linear context-free rewriting systems''. Jezici koje ovi formalizmi generiraju leže između kontekstno neovisnih i kontekstno ovisnih jezika.

 

 

{{Reference}}