Entydighetssatser

Entydighetssatser er formelle resultater som handler om når en representasjon har en entydig betydning eller tolkning innenfor et gitt formelt system. Begrepet brukes i logikk, formell språkteori og informatikk, samt i teoretisk lingvistikk og prosessering av naturlig språk. Hovedideen er at for en gitt streng eller et gitt symbolsett gir satsene en entydig tolkning eller et entydig parse-tre.

I formell språkteori gjelder entydighet ofte for grammatikker: en grammatikk er entydig hvis hver streng som kan avledes fra grammatikken har høyst ett parse-tre. Hvis en streng kan ha flere parse, er grammatikken tvetydig. Entydighet har praktiske konsekvenser for parsere: en entydig grammatikk (og ofte de som er LL(1) eller LR(k)) gjør at en deterministisk parser kan bestemme en unik parse. Mange kompilatorer og verktøy bygger på slike resultater.

I naturlig språk er full entydighet sjelden, siden språk ofte er tvetydig. Entydighetssatser brukes i teoretiske modeller og i design av disambigueringregler, der kontekst, semantikk eller verdenskunnskap hjelper å velge riktig tolkning. I praksis kombineres regler, statistikk og kontekst for å oppnå entydige utfall i NLP-systemer.

Eksempel: uttrykket "1 + 2 * 3" kan være tvetydig uten prioritetregler; ved å innføre operasjonsprioritet og assosiativitet i grammatikken blir tolkningen entydig som 1 + (2 * 3).

Se også: tvetydighet, entydig grammatikk, parse-tre, LR-parsing.