Det finns flera sätt att visa att ett språk är regelbundet. Här är en uppdelning av de vanliga metoderna, tillsammans med förklaringar och exempel:
1. Konstruera en ändlig automat (FA) eller deterministisk finit automat (DFA)
* Förklaring: Om du kan bygga en DFA eller NFA (nondeterministisk ändlig automat) som accepterar * alla * och * bara * strängarna på språket, är språket regelbundet.
* hur man gör det:
* Definiera staterna: Tillståndarna i din FA representerar "minnet" av vad som hittills har sett i ingångssträngen. Tänk på vilken information som är nödvändig att komma ihåg för att avgöra om strängen är på språket.
* Definiera övergångarna: Övergångarna dikterar hur FA rör sig från tillstånd till tillstånd baserat på insatsymbolerna. Se till att dina övergångar korrekt återspeglar språkens regler.
* Definiera starttillståndet: Där automaten börjar bearbeta.
* Definiera de accepterande staterna: De tillstånd som anger strängen är på språket.
* Exempel: Tänk på språket l ={strängar över {a, b} som innehåller "ab" som en underlag}.
`` `
Stater:Q0 (Start), Q1, Q2 (accepterar)
Övergångar:
- Q0, A -> Q1 (sett en 'A' hittills, vilket kan leda till "AB")
- Q0, B -> Q0 (sett en 'B', återställning)
- Q1, A -> Q1 (sett 'AA' hittills, fortfarande letar efter "AB")
- Q1, B -> Q2 (sett 'AB'!)
- Q2, A -> Q2 (redan sett 'AB', så eventuella ytterligare input håller oss att acceptera)
- Q2, B -> Q2 (redan sett 'AB', så att ytterligare input håller oss att acceptera)
Startstatus:Q0
Acceptera tillstånd:Q2
`` `
Du kan rita ett tillståndsdiagram för att visualisera denna FA.
2. Konstruera ett regelbundet uttryck
* Förklaring: Om du kan skriva ett regelbundet uttryck som beskriver * alla * och * bara * strängarna på språket, är språket regelbundet.
* hur man gör det:
* Förstå de grundläggande regelbundna uttrycksoperatörerna:
* CONCATENATION:`AB '(matchar strängen" AB ")
* Union (eller):`a | b` (matchar" a "eller" b ")
* Kleene Star (noll eller fler repetitioner):`a*` (matcher "", "a", "aa", "aaa", ...)
* Kleene Plus (en eller flera repetitioner):`A+` (matchar "a", "aa", "aaa", ...)
* Parentes för gruppering:`(A | B) C` (matcher" AC "eller" BC ")
* Karaktärsklasser:`[ABC]` (matchar 'a', 'b' eller 'c')
* Intervall:`[A-Z]` (matchar alla små bokstäver)
* Dela upp språket i mindre delar och kombinera dem med operatörerna.
* Exempel: Med samma språk l ={strängar över {a, b} som innehåller "ab" som en substring}.
Det regelbundna uttrycket är:`(a | b)*ab (a | b)*`
* `(a | b)*` betyder noll eller fler förekomster av 'a' eller 'b' (vilken sträng av 'a's och' b's).
* `AB 'är den erforderliga underlaget.
* `(A | B)*` Tillåter igen någon sträng av 'A och' B:er* efter* "AB".
3. Använda stängningsegenskaper för vanliga språk
* Förklaring: Regelbundna språk stängs under vissa operationer. Detta innebär att om du tillämpar dessa operationer på vanliga språk är resultatet också ett vanligt språk. Vanliga stängningsegenskaper inkluderar:
*
* Sammankoppling
* Kleene -stjärnan
* Korsning
* Komplementering
* Skillnad
* Vändning
* Homomorfism (substitution)
* hur man gör det:
1. Visa att språket kan konstrueras av enklare, kända vanliga språk med hjälp av stängningsoperationer.
2. Om du till exempel kan visa att ditt språk är föreningen med två vanliga språk har du bevisat att det är regelbundet.
* Exempel: Låt L1 ={strängar över {A, B} börja med 'A'} och L2 ={strängar över {A, B} som slutar med 'B'}. Både L1 och L2 är regelbundna (du kan enkelt skriva regelbundna uttryck för dem:`a (a | b)*` och `(a | b)*b`).
Tänk nu på språket l =l1 ∩ l2 ={strängar över {a, b} börjar med 'a' * och * slut med 'b'}.
Eftersom vanliga språk är stängda under korsningen är L också regelbunden. Dess regelbundna uttryck är `a (a | b)*b`.
4. MyHill-Nerode-teorem
* Förklaring: Myhill-Nerode-teoremet ger ett nödvändigt och tillräckligt villkor för att ett språk ska vara regelbundet. Den säger att ett språk L är regelbundet om och bara om det har ett ändligt antal *urskiljbara suffix *. Två suffix *x *och *y *kan urskiljas med avseende på *l *om det finns en sträng *z *så att exakt en av *xz *eller *yz *är i *l *. I enklare termer:Ett språk L är regelbundet om du kan dela upp alla möjliga prefix i ett ändligt antal ekvivalensklasser.
* hur man gör det (mer avancerat):
1. Definiera en ekvivalensrelation baserad på urskiljbara suffix:`x ≡ y` om och bara om för alla strängar` z`, `xz ∈ L` om och bara om` yz ∈ L`.
2. Visa att antalet ekvivalensklasser under detta förhållande är begränsat. Om det är, är språket regelbundet. Antalet ekvivalensklasser är lika med antalet tillstånd i den minimala DFA för språket.
* Exempel: Låt l ={0
n
1
n
| n ≥ 0}. Detta är ett * icke-regelbundet * språk (används för att demonstrera pumpningslemma). För att intuitivt förstå Myhill-Nerode-applikationen:
Tänk på prefixen 0, 00, 000, .... om jag var regelbundna, så så småningom två prefix, säg 0
i
och 0
j
(där jag
i
till 0
i
, du får 0
i
1
i
, som * är * i L. Men om du lägger till 1
i
till 0
j
, du får 0
j
1
i
, som är * inte * i L (eftersom J> i). Således 0
i
och 0
j
är urskiljbara. Eftersom du kan skapa ett oändligt antal urskiljbara prefix är språket inte regelbundet. Myhill-Nerode-teoremet används ofta för att bevisa att ett språk är * inte * regelbundet.
5. Pumpande lemma för vanliga språk (för att bevisa ett språk är * inte * regelbundet)
* Förklaring: Pumping Lemma är ett verktyg för att bevisa att ett språk är * inte * regelbundet. Den säger att om ett språk L är regelbundet finns det en pumplängd *P *(ett heltal), så att alla strängar *i L med längd större än eller lika med *p *kan delas upp i tre underlag, *x *, *y *och *z *, där *s *=*xyz *, och följande villkor innehåller:
1. För varje i> =0, xy
i
Z är i L. (du kan "pumpa" y -delen valfritt antal gånger och resultatet är fortfarande på språket).
2. | Y |> 0. (Den "pumpade" delen Y måste ha längd minst 1).
3. | XY | <=p. (Den "pumpade" delen Y måste ske inom de första P -tecken).
* Hur man använder det för att bevisa icke-regelbundenhet:
1. Antag att L är regelbunden.
2. Anta att pumplängden är *p *. (Du vet inte vad * P * är, men du antar att det finns).
3. Välj en sträng * S * i L så att | S |> =*p *. Nyckeln här är att välja en sträng * S * som kommer att leda till en motsägelse senare. Detta är ofta den svåraste delen.
4. Tänk på alla möjliga sätt att dela * S * i * xyz * så att | y |> 0 och | XY | <=*p *.
5. För *varje *möjlig uppdelning, hitta ett värde på *i *så att *xy
i
z* är* inte* i l. Detta motsäger pumpens lemma, som säger att * för alla * i, xy
i
Z måste vara i L.
6. Eftersom du hittade en motsägelse måste ditt första antagande att L är regelbundet vara falskt. Därför är l inte regelbunden.
* Exempel: Låt l ={a
n
b
n
| n> =0}. Bevisa att L inte är regelbunden.
1. Antag att L är regelbunden.
2. Låt * p * vara pumplängden.
3. Välj * S * =A
p
B
p
. Lägg märke till att | s | =2p>
=p.
4. Tänk på de möjliga uppdelningarna av * s * till * xyz * med | y |> 0 och | XY | <=*p *. Sedan | XY | <=* p * och * s * börjar med en
p
, * xy * måste endast bestå av 'A. Därför:
* x =a
j
För vissa j> =0
* y =a
k
För vissa k> 0 (eftersom | y |> 0)
* z =a
p-j-k
B
p
5. Välj i =0. Sedan xy
i
z =xz =a
j
a
p-j-k
B
p
=a
p-k
B
p
. Sedan k> 0, p - k
p-k
B
p
är * inte * i L.
6. Motstånd! Pumpande lemma säger att för alla, xy
i
Z måste vara i L. Vi hittade en division och ett värde på jag som det inte är.
7. Därför är l inte regelbunden.
Nyckelöverväganden och bästa praxis:
* Välj rätt metod: Den bästa metoden beror på språket.
* För enkla språk är konstruktion av en DFA/NFA eller regelbundet uttryck ofta det enklaste.
* För språk byggda från andra vanliga språk med standardoperationer, använd stängningsegenskaper.
*För språk som misstänks vara *icke-regelbundna *, använd pumpens lemma eller myhill-nerv-teorem.
* tydlighet och rigoritet: När du bevisar att ett språk är regelbundet definierar du tydligt ditt automat/regelbundna uttryck och förklar varför det accepterar * alla * strängar på språket och * bara * dessa strängar. Med andra ord, bevisa båda riktningarna för implikationen. En vag beskrivning räcker inte.
* minimering: Om du konstruerar en DFA är det användbart (men inte krävs) för att minimera den. En minimerad DFA är unik för ett givet språk.
* övning: Att arbeta igenom många exempel är det bästa sättet att förstå dessa koncept och utveckla den intuition som behövs för att tillämpa dem effektivt.
Sammanfattningsvis innebär bevisning att ett språk är regelbundet vanligtvis att visa dess ekvivalens med en formell definition av regelbundenhet:antingen genom att direkt konstruera en maskin (FA) eller mönster (regelbundet uttryck) som känner igen det, eller genom att visa det är byggt från regelbundna komponenter med kända operationer som bevarar regelbundenhet. Pumpande lemma, däremot, används för att motbevisa regelbundenhet.
