Avgörbara språk stängs under följande operationer:
1. Union: Om L1 och L2 är avgörande språk, är L1 ∪ L2 också avgörande.
* Förklaring: Vi kan konstruera en Turing Machine (TM) som bestämmer L1 ∪ L2. TM, på ingången 'W', simulerar TMS för L1 och L2 i sekvens.
* Simulera först TM för L1. Om det accepterar, acceptera 'W'.
* Om TM för L1 avvisar, simulera TM för L2. Om det accepterar, acceptera 'W'.
* Om TM för L2 avvisar, avvisa 'W'.
* Nyckelpunkt: Eftersom L1 och L2 är avgörande stoppar deras respektive TMS * alltid * (antingen att acceptera eller avvisa). Detta säkerställer att vår fackliga avgörande TM också alltid stoppar.
2. Korsning: Om L1 och L2 är avgörande språk, är L1 ∩ L2 också avgörande.
* Förklaring: I likhet med Union kan vi bygga en TM som bestämmer L1 ∩ L2.
* Simulera TM för L1. Om den avvisar, avvisa 'W'.
* Om TM för L1 accepterar, simulera sedan TM för L2. Om det accepterar, acceptera 'W'.
* Om TM för L2 avvisar, avvisa 'W'.
3. Komplement: Om L är ett avgörande språk, är L '(komplementet för L) också avgörande.
* Förklaring: Vi kan konstruera en TM för L 'genom att helt enkelt byte Accept och avvisa tillstånd i TM som avgör L.
* Med tanke på TM för L, skapa en ny TM som är identisk utom:om den ursprungliga TM accepterar, avvisar den nya TM. Om den ursprungliga TM avvisar accepterar den nya TM.
* avgörande aspekt: Detta fungerar * bara * eftersom den ursprungliga TM är en avgörare och alltid stoppar. Om den ursprungliga TM kunde slinga, skulle denna operation inte resultera i en avgörare för komplementet.
4. Sammankoppling: Om L1 och L2 är avgörande språk, är L1L2 (sammankopplingen av L1 och L2) också avgörande.
* Förklaring:
* På input `w`, prova alla möjliga sätt att dela upp" w "i två delar,` x` och `y`, så att` w =xy`.
* För varje splittring, simulera TM för L1 på `X` och TM för L2 på` Y`.
* Om TM för L1 accepterar `X` * och * TM för L2 accepterar` Y`, acceptera, acceptera 'W'.
* Om alla möjliga splittringar har prövats och ingen uppfyller ovanstående villkor, avvisa sedan `w '.
* Viktigt: Eftersom L1 och L2 är avgörande stoppar dessa simuleringar alltid. Eftersom vi försöker alla möjliga delningar stoppar den totala TM också alltid.
5. Kleene Star: Om L är ett avgörande språk, är L* (Kleene -stjärnan i L) också avgörande.
* Förklaring: Detta liknar sammankoppling, men vi tillåter flera sammankopplingar (inklusive noll).
* På input `w`, för` i =0` till `| w |`:(där `| w |` är längden på `w ')
* Prova alla möjliga sätt att dela upp "w" i "i" delar, "x1, x2, ..., xi", så att "w =x1x2 ... xi".
* För varje splittring, simulera TM för L på varje `xj`.
* Om tm för L accepterar varje `xj` (för alla` j` från 1 till `i '), acceptera' w '.
* Om alla möjliga värden på `i 'och alla möjliga delningar har testats och ingen uppfyller ovanstående villkor, avvisa sedan` w'.
* Nyckelinsikt: Eftersom längden på någon sträng i l* inte kan vara större än längden på ingången "w", kan vi begränsa antalet splittringar vi behöver prova. Simuleringen stoppar efter att ha övervägt alla möjliga splittringar.
6. Reversering: Om L är ett avgörande språk, så l
r
(Vändningen av L) är också avgörande.
* Förklaring: Konstruera en TM som gör följande:
* Vänd ingångssträngen `w` för att få` w
r
`
* Simulera TM för L på `w
r
`
* Om TM för L accepterar `w
r
`, Acceptera sedan 'W'. Annars avvisa `w`.
7. Skillnad: Om L1 och L2 är avgörande språk, är L1 - L2 också avgörande. (L1 - L2 innehåller alla strängar i L1 som är * inte * i L2).
* Förklaring: L1 - L2 =L1 ∩ L2 '. Eftersom avgörande språk stängs under komplement och skärning är de också stängda under skillnad.
8. Prefix: Om L är ett avgörande språk, då prefix (l) ={x | För vissa y är xy ∈ L} avgörande.
* Förklaring:
* På input `x`, för alla möjliga` y` så att `| xy | <=| x | + någon_constant`, (där `någon_constant` är den maximala längden på strängarna att testa),
* Simulera TM för L på `xy`
* Om TM accepterar, acceptera `x`
* Avvisa om ingen av simuleringarna ovan accepterar.
Varför är stängning viktig?
Stängningsegenskaper är grundläggande för att förstå kraften och begränsningarna i formella språkklasser. Att veta att en klass av språk är stängd under vissa operationer gör det möjligt för oss att:
* Konstruera mer komplexa språk: Vi kan kombinera enklare avgörande språk med hjälp av dessa operationer och vara säkra på att det resulterande språket också är avgörande.
* Bevisa språkegenskaper: Stängningsegenskaper kan användas i induktiva bevis för att visa att ett givet språk tillhör en specifik klass.
* Designalgoritmer: Algoritmerna som visar stängning fungerar som ritningar för att implementera parsers och igenkännare för komplexa språk.
* Förstå avgörande hierarkin: De hjälper till att klargöra förhållandet mellan olika språkklasser (t.ex. regelbundna, kontextfria, avgörande, turing-igenkännande).
Sammanfattningsvis är stängningsegenskaperna för avgörande språk en hörnsten i beräkningsteorin. De visar att avgörande språk är en robust och väl uppförd klass av språk.
