För att bevisa att ett språk L är avgörande måste du visa att det finns en Turing -maskin (eller en motsvarande beräkningsmodell) som stannar och accepterar strängar i L och avvisar strängar som inte är i L. Det finns flera sätt att visa detta:
1. Konstruera en Turing -maskin (eller algoritm):
Detta är den mest direkta metoden. Du beskriver uttryckligen en Turing-maskin (eller en algoritm på hög nivå som enkelt kan översättas till en Turing-maskin) som bestämmer språket. Denna beskrivning måste täcka:
* Input: Hur Turing -maskinen tar emot ingångssträngen.
* stater: De olika staterna som maskinen kan vara i.
* Övergångar: Hur maskinen rör sig mellan tillstånd baserat på det aktuella tillståndet och symbolen som läses från bandet.
* Acceptans/avslag: Hur maskinen signalerar acceptans (t.ex. att ange ett "acceptera" tillstånd) eller avslag (t.ex. ange ett "avvisande" tillstånd).
* Stoppning: Av avgörande betydelse måste du visa att maskinen * alltid * stoppar, oavsett om ingångssträngen är i L eller inte. Detta är den mest utmanande delen.
Exempel: Tänk på språket l ={w | W är en palindrome}. Vi kan beskriva en Turing -maskin som:
1. Skannar ingångstejpen från vänster till höger och markerar de första och sista symbolerna.
2. Flyttar markörerna ett steg inåt från båda ändarna.
3. Upprepar steg 2 tills antingen markörerna möts (strängen är en palindrom) eller markörerna korsar (strängen är inte en palindrome).
4. Accepterar om markörerna möts och avvisar om de korsar.
Den här maskinen stannar alltid, vilket bevisar att L är avgörande.
2. Minskning till ett känt avgörande språk:
Om du kan visa att ditt språk L kan reduceras till ett känt avgörande språk l ', bevisar detta att L också är avgörande. En reduktion är en beräkningsbar funktion f så att:
* x ∈ L om och bara om f (x) ∈ L '
Om du har en algoritm för att bestämma L 'kan du använda den för att bestämma L genom att först tillämpa reduktionen f. Eftersom både f och algoritmen för l 'är beräkningsbara är den kombinerade processen också beräkningsbar, vilket beslutar L.
Exempel: Låt L vara språket för strängar som representerar giltiga aritmetiska uttryck. Vi kan reducera L till ett sammanhangsfri grammatik (CFG) -språk L 'som är avgörande (parsingalgoritmer för CFG:er finns). Reduktionen skulle innebära att transformera den aritmetiska expressionssträngen till ett parse -träd enligt grammatiken. Om transformationen lyckas och ett giltigt parse -träd genereras, är strängen i L; Annars är det inte.
3. Använda stängningsegenskaper för avgörande språk:
Avgörbara språk stängs under vissa operationer som union, korsning, sammankoppling, Kleene -stjärna och komplement. Om du kan uttrycka ditt språk L med hjälp av dessa operationer på kända avgörande språk, är L också avgörande.
Exempel: Om L1 och L2 är avgörande är L1 ∪ L2 också avgörande. Du kan bestämma L1 ∪ L2 genom att köra beslutsalgoritmer för L1 och L2 på ingångssträngen; Om antingen accepterar accepterar unionen.
Sammanfattningsvis: Att bevisa att beslutet kommer att visa att en deterministisk algoritm (eller Turing -maskin) finns som alltid kommer att stoppa och korrekt klassificera varje ingångssträng som tillhör språket eller inte. Metoden du väljer beror på det specifika språket och din intuition om dess egenskaper. Det vanligaste tillvägagångssättet är att direkt konstruera en Turing -maskin eller algoritm, men minskningar och stängningsegenskaper är kraftfulla verktyg för mer komplexa språk.
