| Beslisbare talen worden gesloten onder de volgende bewerkingen:
1. Unie: Als L1 en L2 beslisbare talen zijn, dan is L1 ∪ L2 ook beslisbaar.
* Uitleg: We kunnen een Turing Machine (TM) construeren die beslist over L1 ∪ L2. De TM simuleert op ingang 'w' achtereenvolgens de TM's voor L1 en L2.
* Simuleer eerst de TM voor L1. Als het accepteert, accepteer dan 'w'.
* Als het TM voor L1 afwijst, simuleer dan het TM voor L2. Als het accepteert, accepteer dan 'w'.
* Als het TM voor L2 afwijst, wijs dan 'w' af.
* Belangrijkste punt: Omdat L1 en L2 beslisbaar zijn, stoppen hun respectievelijke TM's *altijd* (accepteren of afwijzen). Dit zorgt ervoor dat ook ons vakbondsbepalende TM altijd stil komt te staan.
2. Kruising: Als L1 en L2 beslisbare talen zijn, dan is L1 ∩ L2 ook beslisbaar.
* Uitleg: Net als bij unie kunnen we een TM bouwen die beslist over L1 ∩ L2.
* Simuleer de TM voor L1. Als het afwijst, wijs dan 'w' af.
* Als het TM voor L1 dit accepteert, simuleer dan het TM voor L2. Als het accepteert, accepteer dan 'w'.
* Als het TM voor L2 afwijst, wijs dan 'w' af.
3. Aanvulling: Als L een beslisbare taal is, dan is L' (het complement van L) ook beslisbaar.
* Uitleg: We kunnen een TM voor L' construeren door eenvoudigweg de acceptatie- en afwijzingstoestanden van de TM die over L beslist, om te wisselen.
* Gegeven het TM voor L, maak een nieuw TM dat identiek is, behalve:als het oorspronkelijke TM accepteert, wijst het nieuwe TM af. Als het oorspronkelijke TM afwijst, accepteert het nieuwe TM.
* Cruciaal aspect: Dit werkt *alleen* omdat het originele TM een beslisser is en altijd stopt. Als de originele TM een lus zou kunnen maken, zou deze operatie niet resulteren in een beslisser voor het complement.
4. Aaneenschakeling: Als L1 en L2 beslisbare talen zijn, dan is L1L2 (de aaneenschakeling van L1 en L2) ook beslisbaar.
* Uitleg:
* Probeer bij invoer van `w` alle mogelijke manieren om `w` in twee delen te splitsen, `x` en `y`, zodat `w =xy`.
* Simuleer voor elke splitsing de TM voor L1 op `x` en de TM voor L2 op `y`.
* Als het TM voor L1 `x` * accepteert en* het TM voor L2 `y` accepteert, accepteer dan `w`.
* Als alle mogelijke splitsingen zijn geprobeerd en geen enkele voldoet aan de bovenstaande voorwaarde, wijs dan `w` af.
* Belangrijk: Omdat L1 en L2 beslisbaar zijn, stoppen deze simulaties altijd. Omdat we alle mogelijke splitsingen proberen, stopt de algehele TM ook altijd.
5. Kleene Star: Als L een beslisbare taal is, dan is L* (de Kleene-ster van L) ook beslisbaar.
* Uitleg: Dit is vergelijkbaar met aaneenschakeling, maar we staan meerdere aaneenschakelingen toe (inclusief nul).
* Bij invoer `w`, voor `i =0` tot `|w|`:(waar `|w|` de lengte van `w` is)
* Probeer alle mogelijke manieren om `w` op te splitsen in `i` delen, `x1, x2, ..., xi`, zodat `w =x1x2...xi`.
* Simuleer voor elke splitsing de TM voor L op elke `xj`.
* Als de TM voor L elke `xj` accepteert (voor alle `j` van 1 tot `i`), accepteer dan `w`.
* Als alle mogelijke waarden van `i` en alle mogelijke splitsingen zijn geprobeerd en geen enkele voldoet aan de bovenstaande voorwaarde, wijs dan `w` af.
* Belangrijkste inzicht: Omdat de lengte van elke string in L* niet groter kan zijn dan de lengte van de invoer `w`, kunnen we het aantal splitsingen beperken dat we moeten proberen. De simulatie stopt nadat alle mogelijke splitsingen zijn overwogen.
6. Omkering: Als L een beslisbare taal is, dan is L
R
(de omkering van L) is ook beslisbaar.
* Uitleg: Construeer een TM dat het volgende doet:
* Keer de invoerreeks `w` om om `w
R
te krijgen `.
* Simuleer de TM voor L op `w
R
`.
* Als het TM voor L `w
R
accepteert ', accepteer vervolgens 'w'. Anders verwerp je `w`.
7. Verschil: Als L1 en L2 beslisbare talen zijn, dan zijn L1 - L2 ook beslisbaar. (L1 - L2 bevat alle strings in L1 die *niet* voorkomen in L2).
* Uitleg: L1 - L2 =L1 ∩ L2'. Omdat beslisbare talen gesloten zijn onder complement en intersectie, zijn ze ook gesloten onder verschil.
8. Voorvoegsel: Als L een beslisbare taal is, dan is Prefix(L) ={x | voor sommige y is xy ∈ L} beslisbaar.
* Uitleg:
* Op invoer `x`, voor alle mogelijke `y` zodat `|xy| <=|x| + some_constant`, (waarbij `some_constant` de maximale lengte is van de te testen strings),
* Simuleer de TM voor L op `xy`
* Als het TM dit accepteert, accepteer dan `x`
* Weigeren als geen van de bovenstaande simulaties accepteert.
Waarom is afsluiting belangrijk?
Sluitingseigenschappen zijn van fundamenteel belang voor het begrijpen van de kracht en beperkingen van formele taallessen. Wetende dat een klasse talen onder bepaalde bewerkingen gesloten is, stelt ons in staat om:
* Complexere talen bouwen: Met deze bewerkingen kunnen we eenvoudiger beslisbare talen combineren en er zeker van zijn dat de resulterende taal ook beslisbaar is.
* Bewijs taaleigenschappen: Sluitingseigenschappen kunnen in inductieve bewijzen worden gebruikt om aan te tonen dat een bepaalde taal tot een specifieke klasse behoort.
* Ontwerpalgoritmen: De algoritmen die afsluiting demonstreren, dienen als blauwdrukken voor het implementeren van parsers en herkenners voor complexe talen.
* Begrijp de beslisbaarheidshiërarchie: Ze helpen de relatie tussen verschillende taalklassen te verduidelijken (bijvoorbeeld regulier, contextvrij, beslisbaar, Turing-herkenbaar).
Samenvattend vormen de afsluitingseigenschappen van beslisbare talen een hoeksteen van de berekenbaarheidstheorie. Ze tonen aan dat beslisbare talen een robuuste en goed gedragende klasse van talen zijn. |
