| M är en DFA som accepterar w} `. Med andra ord, språket består av par av en deterministisk finit automat (DFA) kodad som en sträng och en sträng `w`, så att DFA accepterar strängen` w`.
Här är därför det är avgörande och hur en Turing -maskin kan bestämma den:
Avgörbarhet: Ett språk är avgörande om det finns en Turing -maskin som stannar på varje ingång och accepterar ingången om det är på språket och avvisar det om det inte är det.
Turing Machine Decider: Vi kan konstruera en Turing Machine `D` som bestämmer` A` enligt följande:
1. Input: `D` tar som input '`, där' m 'är kodningen av en dfa och' w 'är en sträng.
2. simulering: `D` simulerar DFA` m` på ingångssträngen `w`. Detta är möjligt eftersom `d` kan hålla reda på det nuvarande tillståndet för" m "och den nuvarande symbolen som läses från" w ". Simuleringen fortsätter enligt följande:
* Starta `m` i sitt ursprungliga tillstånd.
* För varje symbol i "w", övergång "m" till nästa tillstånd enligt dess övergångsfunktion.
3. Acceptera/avvisa:
* Om `m` slutar i ett accepterat tillstånd efter att ha läst hela strängen` w`, accepterar `d`` `.
* Om `m` slutar i ett icke-accepterat tillstånd efter att ha läst hela strängen` w`, avvisar `d`` `.
Varför detta fungerar:
* dfas stoppar alltid: DFAS, per definition, bearbetar varje ingångssymbol exakt en gång och sedan stoppar. De har inga oändliga slingor eller odefinierat beteende.
* simulering är möjlig: En Turing -maskin kan enkelt simulera det deterministiska beteendet hos en DFA eftersom den har tillräckligt med minne och kontroll för att spåra DFA:s tillstånd och inmatningsposition.
* Stoppning: Turing -maskinen `d` stoppar alltid eftersom DFA -simuleringen alltid stoppar.
* Rätt: `D` accepterar exakt strängarna` `där` m` accepterar `w`, och den avvisar exakt strängarna` `där 'm` inte * accepterar' w '.
Formellt bevis (skiss):
För att noggrant bevisa beslutsamhet, skulle du behöva:
1. Definiera formellt kodningen: Ange hur en DFA `m` och en sträng` w` representeras som strängar i ingångsalfabetet för Turing -maskinen `d`.
2. Definiera formellt Turing Machine `D`: Ge ett tillståndsdiagram eller en formell beskrivning av övergångarna av `d`.
3. Bevisa korrekthet: Visa att om `` är på språket 'a', accepterar `d` det, och om '` är * inte * på språket' a ', så avvisar du det.
4. Bevisa att stänga: Visa att `d` alltid stoppar på alla ingångar.
Sammanfattningsvis: Eftersom vi kan bygga en Turing -maskin som alltid stoppar och korrekt accepterar eller avvisar baserat på om en given DFA accepterar en given sträng, är språket "A" avgörande. Detta är ett grundläggande och viktigt exempel i teorin om beräkning.
