Hvordan kan vi afgøre, om en given kontekstfri grammatik overhovedet genererer strenge? Kan dette problem afgøres?
At bestemme, om en given kontekstfri grammatik genererer strenge, er et vigtigt problem inden for beregningskompleksitetsteori. Dette problem falder ind under paraplyen af bestemmelighed, som omhandler spørgsmålet om, hvorvidt en algoritme kan bestemme en bestemt egenskab for alle input. I tilfælde af kontekstfri grammatik er problemet med at afgøre, om de genererer strenge, faktisk afgørligt.
For at forstå, hvordan vi kan bestemme, om en given kontekstfri grammatik genererer strenge, lad os først definere, hvad en kontekstfri grammatik er. En kontekstfri grammatik (CFG) består af et sæt produktionsregler, der specificerer, hvordan man genererer strenge i et formelt sprog. Hver produktionsregel består af et ikke-terminalt symbol, som kan erstattes af en sekvens af symboler kaldet terminaler eller ikke-terminaler. Målet er at starte med et startsymbol og anvende produktionsreglerne til at generere strenge på det sprog, der er defineret af grammatikken.
For at afgøre, om en given CFG genererer strenge, skal vi kontrollere, om der findes en afledning fra startsymbolet, der kan generere en streng. En tilgang til at løse dette problem er at konstruere en parsingalgoritme, der systematisk udforsker alle mulige afledninger fra startsymbolet og tjekker, om nogen af dem kan generere en streng. Hvis en sådan afledning findes, så genererer CFG'en mindst én streng; ellers genererer den ingen strenge.
En almindeligt anvendt parsingalgoritme til kontekstfri grammatik er CYK-algoritmen (Cocke–Younger–Kasami-algoritmen). CYK-algoritmen er en dynamisk programmeringsalgoritme, der bygger en parse-tabel for effektivt at kontrollere, om en given streng kan udledes fra grammatikken. Algoritmen starter med at udfylde parse-tabellen med de terminaler, der direkte kan udlede inputstrengen. Derefter udfylder den iterativt tabellen ved at overveje alle mulige kombinationer af ikke-terminaler, der kan udlede understrengene af inputstrengen. Hvis startsymbolet vises i cellen øverst til højre i parsetabellen, genererer CFG'en inputstrengen.
Lad os illustrere dette med et eksempel. Overvej følgende CFG:
S -> AB
A -> aA | ε
B -> bB | ε
I denne grammatik er S startsymbolet, og A og B er ikke-terminaler. Terminalerne er a og b, og ε repræsenterer den tomme streng.
For at afgøre, om denne grammatik genererer strenge, kan vi anvende CYK-algoritmen. Lad os sige, at vi vil kontrollere, om strengen "aabbb" kan genereres. Vi konstruerer parsetabellen som følger:
aabbb
--------
AAA
BBB
SSS
Startende med terminalerne udfylder vi de celler, der svarer til produktionerne A -> aA og B -> bB. Derefter udfylder vi den celle, der svarer til produktionen S -> AB. Til sidst tjekker vi om startsymbolet S vises i cellen øverst til højre i parsetabellen. I dette tilfælde gør den det, hvilket indikerer, at CFG'en genererer strengen "aabbb".
Hvis startsymbolet ikke vises i cellen øverst til højre i parsetabellen, genererer CFG'en ikke inputstrengen. I sådanne tilfælde kan vi konkludere, at den givne CFG ikke genererer nogen strenge.
At afgøre, om en given kontekstfri grammatik genererer strenge, er et problem, der kan afgøres. En tilgang til at løse dette problem er at konstruere en parsing-algoritme, såsom CYK-algoritmen, der systematisk udforsker alle mulige afledninger fra startsymbolet. Ved at kontrollere, om startsymbolet vises i cellen øverst til højre i parsetabellen, kan vi afgøre, om CFG'en genererer strenge.
Andre seneste spørgsmål og svar vedr afgørbarhed:
- Kan et bånd begrænses til størrelsen af inputtet (hvilket svarer til, at turingmaskinens hoved er begrænset til at bevæge sig ud over TM-båndets input)?
- Hvad betyder det, at forskellige varianter af Turing-maskiner er ækvivalente med hensyn til computerkapacitet?
- Kan et genkendeligt sprog danne en delmængde af afgøreligt sprog?
- Er stopproblemet med en Turing-maskine afgøreligt?
- Hvis vi har to TM'er, der beskriver et sprog, der kan afgøres, er ækvivalensspørgsmålet stadig uafgørligt?
- Hvordan adskiller acceptproblemet for lineært afgrænsede automater sig fra det for Turing-maskiner?
- Giv et eksempel på et problem, der kan afgøres af en lineært afgrænset automat.
- Forklar begrebet afgørelighed i sammenhæng med lineært afgrænsede automater.
- Hvordan påvirker størrelsen af båndet i lineært afgrænsede automater antallet af distinkte konfigurationer?
- Hvad er den største forskel mellem lineært afgrænsede automater og Turing-maskiner?
Se flere spørgsmål og svar i Afgørelighed