För att visa att ett språk L är avgörande måste du visa att det finns en Turing Machine (TM) som:
1. stoppar på alla ingångar: TM måste så småningom nå antingen ett acceptstillstånd eller ett avvisande tillstånd, oavsett ingångssträngen. Det kan inte slingra för alltid.
2. accepterar strängar på språket L: Om en sträng `W` är i L stoppar TM i ett accept.
3. avvisar strängar inte på språket l: Om en sträng `W` inte är i L, stoppar TM i ett avvisande tillstånd.
Med andra ord, ett avgörande språk har en Turing -maskin som fungerar som en perfekt medlemstestare:det ger alltid ett "ja" eller "nej" svar och gör det alltid på en begränsad tid.
Här är en uppdelning av vanliga tekniker och överväganden:
1. Konstruera en Turing Machine (TM) Beskrivning:
* Hög nivå Beskrivning: Börja med en tydlig, mänsklig läsbar beskrivning av TM:s algoritm. Detta bör förklara logiken och de steg som krävs för att bearbeta ingången. Tänk på det som pseudokod.
* Beskrivning på implementeringsnivå (valfritt): Du * kan * tillhandahålla en beskrivning på lägre nivå, specificera tillstånden, övergångsfunktionen, bandalfabetet, etc. Detta är ofta tråkigt och inte krävs om det inte uttryckligen begärs, eller om algoritmen är mycket subtil och kräver exakt definition. Fokusera på den höga beskrivningen först.
* tydlighet är nyckeln: Det viktigaste är att din beskrivning är förståelig och övertygande. En dåligt skriven beskrivning på hög nivå kan vara svårare att förstå än en välskriven formell beskrivning.
2. Allmänna strategier för att utforma deciders:
* Simulera andra maskiner: Om du kan visa att L kan avgöras genom att simulera ett annat avgörande språk (eller flera sådana språk), har du visat att L är avgörande. Avfall är stängd under många operationer (fackförening, korsning, komplement, sammankoppling, Kleene -stjärna).
* Konvertera till ett enklare problem: Försök att omformulera problemet till ett motsvarande men lättare att lösa problem.
* Överväg basfall och rekursion: Om problemet har en rekursiv struktur kan en rekursiv algoritm översättas till en Turing -maskinavgörare. Se till att rekursionen är avgränsad för att garantera uppsägning.
* Uttömmande sökning: Om ingångsutrymmet är begränsat eller kan begränsas kan du ofta använda uttömmande sökning för att kontrollera alla möjligheter. Den avgörande punkten är att sökningen måste garanteras.
* hävstångseffekt Kända avgörande språk: Bygg upp kunskapen om att vissa språk redan är avgörande. Till exempel vanliga språk, kontextfria språk och många andra.
3. Tekniker för att demonstrera uppsägning:
* räkning: Visa att algoritmen involverar en räknare som strikt ökar eller minskar mot en bunden.
* Minskande storlek: Visa att varje steg i algoritmen minskar storleken på problemet tills det når ett trivialt basfall.
* inga oändliga slingor: Övertygande hävdar att algoritmen inte kan komma in i en oändlig slinga. Detta kan innebära att man visar att maskinen alltid flyttar tejphuvudet, eller att staterna som besökts alltid är distinkta inom en viss period.
* Simuleringslängd: Om algoritmen simulerar en annan TM, skapar en övre gräns för antalet steg som simuleringen kommer att ta. Detta beror ofta på ingångsstorleken.
4. Exempel och vanliga scenarier:
* Regelbundna språk: För att visa ett regelbundet språk är avgörande, ge en DFA för språket. En TM kan simulera DFA och stoppa i ett accept eller avvisa tillstånd baserat på DFA:s slutliga tillstånd.
* Kontextfria språk: Använd CYK -algoritmen eller en liknande parsingalgoritm. Dessa algoritmer har en begränsad runtime.
* odecidability: Förstå stoppproblemet. Du * kan inte * bestämma om en godtycklig Turing -maskin stoppar på en godtycklig ingång. Om du kan minska stoppproblemet till ditt problem har du visat att ditt problem är obeslutbart (inte avgörande).
* Emptiness Testing: Att visa ett språk är * tomt * (innehåller inga strängar) är ibland enklare än att visa att det är avgörande. Till exempel är språket för en Turing -maskin * inte * avgörande. Med tanke på en DFA eller CFG är det emellertid tomt * avgörande om språket det representerar är tomt *.
5. Vad man inte ska göra:
* hävdar inte bara att det är avgörande utan motivering. Du måste tillhandahålla ett rimligt argument, vilket vanligtvis innebär att beskriva algoritmen.
* Ge inte en tm som * bara * accepterar strängar på språket. Det måste också * avvisa * strängar * inte * på språket och det måste stoppa.
* Ge inte en algoritm som * kan * stoppa men har potential att slinga för evigt. En avgörare * måste * stoppa.
* Förvirra inte beslutsamhet med igenkännbarhet. Ett igenkännligt språk kräver endast en TM för att stoppa och acceptera om ingången finns på språket. Det kan slinga för evigt om ingången inte finns på språket. Avgörande språk är alltid igenkännliga, men det samtalet är inte sant.
* Försök inte ge ett "bevis med exempel." Att visa att en specifik input accepteras eller avvisas bevisar inte något om språkets beslut.
Exempel 1:A ={0
n
1
n
| n> =0} är avgörande.
* Hög nivå Beskrivning:
1. Skanna ingångssträngen för att säkerställa att den endast består av 0s följt av 1s. Om inte, avvisa.
2. Medan det finns både 0s och 1s kvar:
* Korsa bort vänster 0.
* Korsa av vänster 1.
3. Om inga 0s och inga 1s kvarstår, acceptera.
4. Om bara 0s eller bara 1S kvarstår, avvisa.
* Motivering: Denna algoritm stoppar för alla ingångar. Steg 1 och 3/4 avslutar kontroller. Steg 2 korsar en 0 och en 1 i varje iteration. Antalet 0s och 1s är ändligt, så slingan avslutas. Om antalet 0s och 1s var lika, accepterar vi. Annars avvisar vi.
Exempel 2:Med en DFA D, är dess språk l (d) tomt? A dfa ={ | D är en DFA och L (D) =∅} är avgörande.
* Hög nivå Beskrivning:
1. Markera starttillståndet D.
2. Upprepa tills inga nya stater blir markerade:
* Markera alla tillstånd som kan nås från ett för närvarande markerat tillstånd genom att följa en pil i D.
3. Om något accepterar tillstånd för D är markerat, avvisa.
4. Annars acceptera.
* Motivering: Denna algoritm stoppar. Steg 2 Utforskar alla möjliga nåliga tillstånd. Antalet tillstånd i D är ändligt, så slingan avslutas. Om vi kan nå ett accepterande tillstånd är språket inte tomt och vi avvisar. Annars är det och vi accepterar. Observera att "D" garanteras att vara en DFA genom antagande och därmed har begränsade tillstånd.
Genom att följa dessa strategier och förstå egenskaperna hos Turing -maskiner och avgörande språk kan du effektivt visa att ett språk är avgörande. Kom ihåg att fokusera på en tydlig och övertygande algoritmbeskrivning och ett sund argument för dess uppsägning och korrekthet.
