Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Konštrukcia konečného automatu (FA) alebo deterministického konečného automatu (DFA)
* Vysvetlenie: Ak dokážete postaviť DFA alebo NFA (nedeterministické konečné automaty), ktorý akceptuje * všetky * a * iba * reťazce v jazyku, potom je jazyk pravidelný.
* Ako na to:
* Definujte stavy: Stavy vášho FA predstavujú „pamäť“ toho, čo bolo doteraz videné vo vstupnom reťazci. Zamyslite sa nad tým, aké informácie sú nevyhnutné, aby ste si uvedomili, či je reťazec v jazyku.
* Definujte prechody: Prechody určujú, ako sa FA presúva zo stavu do stavu na základe vstupných symbolov. Uistite sa, že vaše prechody správne odrážajú pravidlá jazyka.
* Definujte stav štart: Kde sa automaty začína spracovať.
* Definujte prijímajúce stavy: Štáty, ktoré označujú reťazec, sú v jazyku.
* Príklad: Zoberme si jazyk l ={reťazce cez {a, b}, ktorý obsahuje „ab“ ako podrestčku}.
`` `
Štáty:Q0 (Štart), Q1, Q2 (prijímanie)
Prechody:
- Q0, A -> Q1 (doteraz videl 'a', čo potenciálne vedie k „AB“)
- Q0, B -> Q0 (videné „b“, reset)
- Q1, A -> Q1 (zatiaľ videné 'aa', stále hľadanie „ab“)
- Q1, B -> Q2 (videné „ab“!)
- Q2, A -> Q2 (už videné „AB“, takže akýkoľvek ďalší vstup si udržuje prijímanie)
- Q2, B -> Q2 (už videné „AB“, takže akýkoľvek ďalší vstup nás udržuje v akceptovaní)
Štart State:Q0
Prijímajúci stav:Q2
`` `
Môžete nakresliť stavový diagram, aby ste si vizualizovali tento FA.
2. Konštrukcia regulárneho výrazu
* Vysvetlenie: Ak dokážete napísať regulárny výraz, ktorý popisuje * všetky * a * iba * reťazce v jazyku, potom je jazyk pravidelný.
* Ako na to:
* Pochopte základných operátorov regulárneho výrazu:
* Zreťazenie:`ab` (zhoduje sa s reťazcom„ ab “)
* Únia (alebo):`a | b` (zhoduje sa„ a “alebo„ b “)
* Kleene Star (nula alebo viac opakovaní):`a*` (zhoduje sa „“, „a“, „aa“, „aaa“, ...)
* Kleene Plus (jedno alebo viac opakovaní):`a+` (zhoduje sa „a“, „aa“, „aaa“, ...)
* Zátvorky na zoskupenie:`(a | b) c` (zhoduje sa s„ ac “alebo„ bc “)
* Triedy znakov:`[ABC]` (zhoduje sa 'a', 'b' alebo 'c')
* Rozsahy:`[a-z]` (zodpovedá akémukoľvek malému písmenu)
* Rozdeľte jazyk na menšie časti a kombinujte ich pomocou operátorov.
* Príklad: Použitím rovnakého jazyka l ={reťazce nad {a, b}, ktoré obsahujú „ab“ ako podrestčku}.
Regulárny výraz je:`(a | b)*ab (a | b)*`
* `(a | b)*` znamená nula alebo viac výskytov „a“ alebo „b“ (akýkoľvek reťazec 'A a' B).
* `AB` je požadovaný podrestík.
* `(a | b)*` Opäť umožňuje akýkoľvek reťazec 'a a' b's* po* "ab".
3. Pomocou vlastností uzatvárania pravidelných jazykov
* Vysvetlenie: Pravidelné jazyky sú uzavreté pri určitých operáciách. To znamená, že ak tieto operácie uplatňujete na bežné jazyky, výsledkom je aj pravidelný jazyk. Bežné vlastnosti uzavretia zahŕňajú:
* Únia
* Zreťazenie
* Kleene hviezda
* Križovatka
* Doplnok
* Rozdiel
* Zvrátenie
* Homomorfizmus (substitúcia)
* Ako na to:
1. Ukážte, že jazyk je možné zostaviť z jednoduchších, známych pravidelných jazykov pomocou uzáverov.
2. Napríklad, ak dokážete ukázať, že váš jazyk je spojením dvoch bežných jazykov, dokázali ste, že je pravidelný.
* Príklad: Nech l1 ={reťazce cez {a, b} počnúc 'a'} a l2 ={reťazce cez {a, b} končí 'b'}. L1 aj L2 sú pravidelné (môžete pre nich ľahko písať regulárne výrazy:`a (a | b)*` a `(a | b)*b`).
Teraz zvážte jazyk L =L1 ∩ L2 ={Strings Over {a, b}, počnúc 'a' * a * koncom 'b'}.
Pretože pravidelné jazyky sú uzavreté v križovatke, L je tiež pravidelný. Jeho regulárny výraz je `a (a | b)*b`.
4. Myhill-nervová veta
* Vysvetlenie: Veta Myhill-Neverode poskytuje nevyhnutnú a dostatočnú podmienku na pravidelný jazyk. Uvádza sa v ňom, že jazyk L je pravidelný, iba ak má konečný počet rozlíšiteľných prípon *. Dve prípony *x *a *y *sú rozlíšiteľné s ohľadom na *l *, ak existuje reťazec *z *tak, že presne jeden z *xz *alebo *yz *je v *l *. Zjednodušene povedané:Jazyk L je pravidelný, ak môžete rozdeliť všetky možné predpony do konečného počtu tried rovnocennosti.
* Ako to urobiť (pokročilejšie):
1. Definujte vzťah ekvivalencie založený na rozlíšiteľných príponách:`x ≡ y` iba vtedy, ak pre všetky reťazce` z`, `xz ∈ L`, ak a iba v prípade` yz ∈ L`.
2. Ukážte, že počet tried rovnocennosti podľa tohto vzťahu je konečný. Ak je, potom je jazyk pravidelný. Počet tried rovnocennosti sa rovná počtu stavov v minimálnom DFA pre jazyk.
* Príklad: Nech l ={0
Zoberme si predpony 0, 00, 000, .... ak boli pravidelné, potom nakoniec dve predpony, povedzme 0
i
na 05. Čerpacia lemma pre bežné jazyky (dokázať jazyk je * nie * pravidelný)
* Vysvetlenie: Pumping Lemma je nástroj na preukázanie toho, že jazyk nie je * pravidelný. Uvádza sa v ňom, že ak je jazyk L pravidelným, potom existuje dĺžka čerpania *p *(celé číslo), takže akýkoľvek reťazec *s *v l s dĺžkou väčšou alebo rovnajúcou sa *p *sa dá rozdeliť do troch podretier, *x *, *y *a *z *, kde *s *=*xyz *a nasledujúce podmienky, ktoré platia:
1. Pre každú i> =0, xy
i
Z je v L. (môžete „pumpovať“ časť y ľubovoľne niekoľkokrát a výsledok je stále v jazyku).2. | Y |> 0. („Čerpaná“ časť y musí mať dĺžku najmenej 1).
3. | Xy | <=s. („Pumpovaná“ časť y sa musí vyskytnúť v rámci prvých znakov P).
* Ako ho používať na preukázanie neregulovania:
1. Predpokladajme, že l je pravidelný.
2. Predpokladajme, že dĺžka čerpania je *p *. (Nevieš, čo je * p *, ale predpokladáte, že existuje).
3. Vyberte reťazec * s * v L tak, že | s |> =*p *. Kľúčom je zvoliť reťazec * s *, ktorý povedie k rozporu neskôr. Toto je často najzložitejšia časť.
4. Zvážte všetky možné spôsoby rozdelenia * s * do * xyz * tak, že | y |> 0 a | xy | <=*p *.
5. Pre každé *možné rozdelenie, nájdite hodnotu *i *tak, že *xy
i
z* nie je* v l. To je v rozpore s čerpacou lemmou, ktorá hovorí, že * pre všetkých * i, xyi
z musí byť v L.6. Pretože ste našli rozpor, váš počiatočný predpoklad, že L je pravidelný, musí byť nepravdivý. Preto nie nie je pravidelné.
* Príklad: Nech l ={a
n
1. Predpokladajme, že l je pravidelný.
2. Nech * p * je dĺžka čerpania.
3. Vyberte * s * =a
p
p
4. Zvážte možné rozdelenia * s * do * xyz * s | y |> 0 a | xy | <=*p *. Pretože | xy | <=* p * a * s * začína p , * xy * musí pozostávať iba z 'a. Preto:
* x =a
j
Pre niektorých j> =0
* y =a
* z =a
p
5. Vyberte i =0. Potom xy
i
z =xz =ap
p
p
6. protirečenie! Pumping Lemma hovorí, že pre všetkých i, xy
i
z musí byť v L. Našli sme rozdelenie a hodnotu I, pre ktorú nie je.7. Preto nie nie je pravidelné.
Kľúčové úvahy a osvedčené postupy:
* Vyberte správnu metódu: Najlepšia metóda závisí od jazyka.
* V prípade jednoduchých jazykov, konštrukcia DFA/NFA alebo regulárneho výrazu je často najjednoduchšia.
* Pre jazyky postavené z iných bežných jazykov pomocou štandardných operácií používajte vlastnosti uzavretia.
*Pre jazyky podozrivé, že sú *neregistrované *, použite vetu čerpacej lemmy alebo myhill-nerv.
* Clarity and Rigor: Pri preukázaní jazyka je pravidelný, jasne definujte váš automatický/regulárny výraz a vysvetlite, prečo akceptuje * všetky * reťazce v jazyku a * iba * tieto reťazce. Inými slovami, dokázať oba smery implikácie. Nejasný popis nestačí.
* minimalizácia: Ak vytvoríte DFA, je užitočné (ale nevyžadované) na jeho minimalizáciu. Minimalizovaná DFA je jedinečná pre daný jazyk.
* prax: Práca na mnohých príkladoch je najlepším spôsobom, ako porozumieť týmto pojmom a rozvíjať intuíciu potrebnú na ich efektívne uplatňovanie.
Stručne povedané, preukázanie, že jazyk je pravidelný, zvyčajne zahŕňa preukázanie jeho rovnocennosti s formálnou definíciou pravidelnosti:buď priamym vytvorením stroja (FA) alebo vzoru (regulárny výraz), ktorý ho rozpoznáva, alebo jeho ukázaním je vytvorený z bežných komponentov pomocou známych operácií, ktoré zachovávajú pravidelnosť. Naopak, čerpacia lemma sa používa na vyvrátenie pravidelnosti.