| Er zijn verschillende manieren om aan te tonen dat een taal regelmatig is. Hier volgt een overzicht van de gebruikelijke methoden, samen met uitleg en voorbeelden:
1. Een eindige automaat (FA) of een deterministische eindige automaat (DFA) construeren
* Uitleg: Als je een DFA of NFA (Nondeterministic Finite Automaton) kunt bouwen die *alle* en *alleen* de tekenreeksen in de taal accepteert, dan is de taal regulier.
* Hoe je het doet:
* Definieer de statussen: De statussen van uw FA vertegenwoordigen het "geheugen" van wat tot nu toe in de invoerreeks is gezien. Bedenk welke informatie essentieel is om te onthouden om te bepalen of de tekenreeks in de taal staat.
* Definieer de overgangen: De overgangen bepalen hoe de FA van staat naar staat beweegt op basis van de invoersymbolen. Zorg ervoor dat uw overgangen de regels van de taal correct weerspiegelen.
* Definieer de startstatus: Waar de automaat begint met verwerken.
* Definieer de acceptatiestatussen: De statussen die aangeven dat de tekenreeks zich in de taal bevindt.
* Voorbeeld: Beschouw de taal L ={strings over {a, b} die "ab" als substring bevatten}.
```
Staten:q0 (start), q1, q2 (accepterend)
Overgangen:
- q0, a -> q1 (tot nu toe een 'a' gezien, mogelijk leidend tot 'ab')
- q0, b -> q0 (gezien een 'b', reset)
- q1, a -> q1 (tot nu toe 'aa' gezien, nog steeds op zoek naar "ab")
- q1, b -> q2 (gezien 'ab'!)
- q2, a -> q2 (al gezien als 'ab', dus elke verdere invoer zorgt ervoor dat we blijven accepteren)
- q2, b -> q2 (al 'ab' gezien, dus elke verdere invoer zorgt ervoor dat we blijven accepteren)
Startstatus:q0
Accepterende staat:q2
```
U kunt een toestandsdiagram tekenen om deze FA te visualiseren.
2. Een reguliere expressie construeren
* Uitleg: Als je een reguliere expressie kunt schrijven die *alle* en *alleen* de tekenreeksen in de taal beschrijft, dan is de taal regulier.
* Hoe je het doet:
* Begrijp de basisoperatoren voor reguliere expressies:
* Aaneenschakeling:`ab` (komt overeen met de tekenreeks "ab")
* Union (of):`a|b` (komt overeen met "a" of "b")
* Kleene-ster (nul of meer herhalingen):`a*` (komt overeen met "", "a", "aa", "aaa", ...)
* Kleene plus (een of meer herhalingen):`a+` (komt overeen met "a", "aa", "aaa", ...)
* Haakjes voor groepering:`(a|b)c` (komt overeen met "ac" of "bc")
* Karakterklassen:`[abc]` (komt overeen met 'a', 'b' of 'c')
* Bereiken:`[a-z]` (komt overeen met elke kleine letter)
* Splits de taal op in kleinere delen en combineer ze met behulp van de operators.
* Voorbeeld: Dezelfde taal gebruiken L ={strings over {a, b} die "ab" als substring bevatten}.
De reguliere expressie is:`(a|b)*ab(a|b)*`
* `(a|b)*` betekent nul of meer exemplaren van 'a' of 'b' (elke reeks van 'a's en 'b's).
* `ab` is de vereiste subtekenreeks.
* `(a|b)*` staat opnieuw elke reeks 'a's en 'b's *na* "ab" toe.
3. Sluitingseigenschappen van reguliere talen gebruiken
* Uitleg: Reguliere talen zijn bij bepaalde bewerkingen gesloten. Dit betekent dat als u deze bewerkingen op reguliere talen toepast, het resultaat ook een reguliere taal is. Gemeenschappelijke sluitingseigenschappen zijn onder meer:
* Unie
* Aaneenschakeling
* Kleene-ster
* Kruispunt
* Aanvulling
* Verschil
* Omkering
* Homomorfisme (substitutie)
* Hoe je het doet:
1. Laat zien dat de taal kan worden opgebouwd uit eenvoudigere, bekende reguliere talen met behulp van afsluitingsoperaties.
2. Als je bijvoorbeeld kunt aantonen dat jouw taal de vereniging is van twee reguliere talen, heb je bewezen dat deze regulier is.
* Voorbeeld: Stel dat L1 ={strings over {a, b} beginnend met 'a'} en L2 ={strings over {a, b} eindigend met 'b'}. Zowel L1 als L2 zijn regulier (je kunt er eenvoudig reguliere expressies voor schrijven:`a(a|b)*` en `(a|b)*b`).
Beschouw nu de taal L =L1 ∩ L2 ={strings over {a, b} beginnend met 'a' *en* eindigend met 'b'}.
Omdat reguliere talen gesloten zijn onder intersectie, is L ook regulier. De reguliere expressie ervan is `a(a|b)*b`.
4. Stelling van Myhill-Nerode
* Uitleg: De stelling van Myhill-Nerode biedt een noodzakelijke en voldoende voorwaarde voor een taal om regelmatig te zijn. Het stelt dat een taal L regulier is als en slechts als deze een eindig aantal *onderscheidbare achtervoegsels* heeft. Twee achtervoegsels *x* en *y* zijn te onderscheiden met betrekking tot *L* als er een string *z* bestaat, zodat precies één van *xz* of *yz* in *L* staat. In eenvoudiger bewoordingen:een taal L is regulier als je alle mogelijke voorvoegsels kunt verdelen in een eindig aantal equivalentieklassen.
* Hoe je het doet (gevorderder):
1. Definieer een equivalentierelatie op basis van te onderscheiden achtervoegsels:`x ≡ y` dan en slechts dan als voor alle strings `z`, `xz ∈ L` dan en slechts dan als `yz ∈ L`.
2. Laat zien dat het aantal equivalentieklassen onder deze relatie eindig is. Als dat zo is, dan is de taal regulier. Het aantal equivalentieklassen is gelijk aan het aantal toestanden in de minimale DFA voor de taal.
* Voorbeeld: Stel L ={0
n
1
n
| n ≥ 0}. Dit is een *niet-reguliere* taal (gebruikt om het Pumping Lemma te demonstreren). Om de Myhill-Nerode-applicatie intuïtief te begrijpen:
Beschouw de voorvoegsels 0, 00, 000, .... Als L regulier zou zijn, dan zouden er uiteindelijk twee voorvoegsels zijn, bijvoorbeeld 0
i
en 0
j
(waarbij i
i
tot 0
i
, krijg je 0
i
1
i
, wat *is* in L. Als u echter 1
i
tot 0
j
, krijg je 0
j
1
i
, wat *niet* is in L (omdat j> i). Dus 0
i
en 0
j
zijn te onderscheiden. Omdat je een oneindig aantal te onderscheiden voorvoegsels kunt maken, is de taal niet regulier. De stelling van Myhill-Nerode wordt vaak gebruikt om te bewijzen dat een taal *niet* regulier is.
5. Het Pumping Lemma voor reguliere talen (om te bewijzen dat een taal *NIET* regulier is)
* Uitleg: Het Pumping Lemma is een hulpmiddel om te bewijzen dat een taal *niet* regulier is. Er wordt gesteld dat als een taal L regulier is, er een pomplengte *p* (een geheel getal) bestaat, zodat elke string *s* in L met een lengte groter dan of gelijk aan *p* kan worden verdeeld in drie substrings, *x*, *y* en *z*, waarbij *s* =*xyz*, en de volgende voorwaarden gelden:
1. Voor elke i>=0, xy
i
z is in L. (Je kunt het y-gedeelte een willekeurig aantal keren "pompen" en het resultaat is nog steeds in de taal).
2. |y|> 0. (Het "gepompte" deel y moet een lengte van minimaal 1 hebben).
3. |xy| <=blz. (Het "gepompte" deel y moet binnen de eerste p-tekens voorkomen).
* Hoe u dit kunt gebruiken om niet-regelmatigheid te bewijzen:
1. Stel dat L regulier is.
2. Stel dat de pomplengte *p* is. (Je weet niet wat *p* is, maar je gaat ervan uit dat het bestaat).
3. Kies een string *s* in L zodat |s|>=*p*. De sleutel hier is om een string *s* te kiezen die later tot een tegenspraak zal leiden. Dit is vaak het lastigste deel.
4. Overweeg alle mogelijke manieren om *s* in *xyz* te verdelen, zodat |y|> 0 en |xy| <=*p*.
5. Zoek voor *elke* mogelijke deling een waarde van *i* zodat *xy
i
z* is *niet* in L. Dit is in tegenspraak met het Pumping Lemma, dat zegt dat *voor iedereen* i, xy
i
z moet in L liggen.
6. Aangezien je een tegenstrijdigheid hebt gevonden, moet je aanvankelijke aanname dat L regulier is, onjuist zijn. Daarom is L niet regulier.
* Voorbeeld: Zij L ={a
n
b
n
| n>=0}. Bewijs dat L niet regulier is.
1. Stel dat L regulier is.
2. Laat *p* de pomplengte zijn.
3. Kies *s* =a
p
b
p
. Merk op dat |s| =2p>
=p.
4. Denk na over de mogelijke verdelingen van *s* in *xyz* met |y|> 0 en |xy| <=*p*. Sinds |xy| <=*p* en *s* beginnen met a
p
, *xy* mag alleen uit 'a's bestaan. Daarom:
* x =a
j
voor sommige j>=0
* y =a
k
voor sommige k> 0 (omdat |y|> 0)
* z =a
p-j-k
b
p
5. Kies i =0. Dan xy
i
z =xz =a
j
a
p-j-k
b
p
=a
p-k
b
p
. Omdat k> 0, p - k
p-k
b
p
is *niet* in L.
6. Tegenspraak! Het Pumping Lemma zegt dat voor alle i, xy
i
z moet in L liggen. We hebben een deling en een waarde van i gevonden waarvoor dit niet het geval is.
7. Daarom is L niet regulier.
Belangrijke overwegingen en praktische tips:
* Kies de juiste methode: De beste methode is afhankelijk van de taal.
* Voor eenvoudige talen is het construeren van een DFA/NFA of reguliere expressie vaak het gemakkelijkst.
* Gebruik sluitingseigenschappen voor talen die zijn opgebouwd uit andere reguliere talen met behulp van standaardbewerkingen.
* Voor talen waarvan wordt vermoed dat ze *niet-regulier* zijn, gebruikt u het Pumping Lemma of de stelling van Myhill-Nerode.
* Duidelijkheid en nauwkeurigheid: Wanneer u bewijst dat een taal regulier is, definieer dan duidelijk uw automaat/reguliere expressie en leg uit waarom deze *alle* strings in de taal accepteert en *alleen* die strings. Met andere woorden:bewijs beide richtingen van de implicatie. Een vage omschrijving is niet genoeg.
* Minimalisatie: Als u een DFA samenstelt, is het nuttig (maar niet verplicht) om deze te minimaliseren. Een geminimaliseerde DFA is uniek voor een bepaalde taal.
* Oefenen: Het doornemen van veel voorbeelden is de beste manier om deze concepten te begrijpen en de intuïtie te ontwikkelen die nodig is om ze effectief toe te passen.
Samenvattend betekent het bewijzen dat een taal regulier is doorgaans het aantonen van de gelijkwaardigheid ervan met een formele definitie van regelmaat:ofwel door rechtstreeks een machine (FA) of patroon (reguliere expressie) te construeren die de taal herkent, ofwel door aan te tonen dat de taal is opgebouwd uit reguliere componenten met behulp van bekende bewerkingen die de regelmaat behouden. Het Pumping Lemma wordt daarentegen gebruikt om regelmaat te weerleggen. |
