Kan vi avgjøre om en gitt streng aksepteres av en kontekstfri grammatikk? Er dette problemet avgjørbart?
Å avgjøre om en gitt streng er akseptert av en kontekstfri grammatikk er et grunnleggende problem i beregningskompleksitetsteori. Dette problemet faller inn under den bredere kategorien avgjørbarhet, som omhandler å bestemme om en bestemt egenskap holder for en gitt inngang. Når det gjelder kontekstfrie grammatikker, er problemet med strengaksept avgjort.
En kontekstfri grammatikk er et formelt system som består av et sett med produksjonsregler som beskriver hvordan man genererer strenger i et språk. Det er definert av en tuppel (V, Σ, R, S), der V er et sett med ikke-terminale symboler, Σ er et sett med terminalsymboler, R er et sett med produksjonsregler og S er startsymbolet. Språket som genereres av en kontekstfri grammatikk er settet med alle strenger som kan utledes fra startsymbolet ved å bruke produksjonsreglene.
For å finne ut om en gitt streng aksepteres av en kontekstfri grammatikk, kan vi bruke ulike algoritmer, for eksempel CYK-algoritmen eller Earley-algoritmen. Disse algoritmene bruker dynamiske programmeringsteknikker for å effektivt sjekke om en streng kan utledes fra startsymbolet til grammatikken.
CYK-algoritmen, for eksempel, konstruerer en tabell der hver celle representerer en delstreng av inngangsstrengen og et sett med ikke-terminaler som kan generere den delstrengen. Ved å iterativt fylle tabellen basert på produksjonsreglene til grammatikken, bestemmer algoritmen om startsymbolet kan generere hele inndatastrengen. Hvis startsymbolet vises i cellen øverst til høyre i tabellen, aksepteres strengen av grammatikken; ellers er det ikke det.
Tenk på følgende eksempel: La oss si at vi har en kontekstfri grammatikk med produksjonsreglene:
S -> AB
A -> a
B -> b
Hvis vi ønsker å finne ut om strengen "ab" er akseptert av denne grammatikken, kan vi bruke CYK-algoritmen. Algoritmen konstruerer en tabell med to celler, en for hvert tegn i inndatastrengen. Tabellen ser slik ut:
| 1 | 2 |
—+—+—+
1 | A | S |
—+—+—+
2 | | B |
—+—+—+
Fra den nederste raden kan vi se at cellen (2,2) inneholder den ikke-terminale B, som genereres av produksjonsregelen B -> b. Flytter vi opp til den øverste raden finner vi at cellen (1,2) inneholder den ikke-terminale S, som genereres av produksjonsregelen S -> AB. Til slutt inneholder cellen (1,1) den ikke-terminale A, som genereres av produksjonsregelen A -> a. Siden startsymbolet S vises i cellen øverst til høyre, kan vi konkludere med at strengen "ab" er akseptert av grammatikken.
Problemet med å avgjøre om en gitt streng er akseptert av en kontekstfri grammatikk er avgjørbart. Algoritmer som CYK-algoritmen eller Earley-algoritmen kan brukes til å effektivt sjekke om en streng kan utledes fra startsymbolet til grammatikken. Disse algoritmene bruker dynamiske programmeringsteknikker for å konstruere tabeller og bestemme aksepten av strengen.
Andre nyere spørsmål og svar vedr Avgjørbarhet:
- Kan et bånd begrenses til størrelsen på inngangen (som tilsvarer at hodet på turingmaskinen er begrenset til å bevege seg forbi inngangen til TM-båndet)?
- Hva betyr det at forskjellige varianter av Turing-maskiner er likeverdige når det gjelder databehandling?
- Kan et turing gjenkjennelig språk utgjøre en delmengde av avgjørbart språk?
- Er stoppproblemet til en Turing-maskin avgjørbart?
- Hvis vi har to TM-er som beskriver et avgjørbart språk, er ekvivalensspørsmålet fortsatt uavgjort?
- Hvordan skiller akseptproblemet for lineært avgrensede automater seg fra det for Turing-maskiner?
- Gi et eksempel på et problem som kan avgjøres av en lineært avgrenset automat.
- Forklar begrepet avgjørbarhet i sammenheng med lineært avgrensede automater.
- Hvordan påvirker størrelsen på båndet i lineært avgrensede automater antallet distinkte konfigurasjoner?
- Hva er hovedforskjellen mellom lineære avgrensede automater og Turing-maskiner?
Se flere spørsmål og svar i Avgjørbarhet