Regularne expresssion jest zdefiniowany rekurencyjnie jako
- dla niektórych jest wyrażeniem regularnym,
- jest wyrażeniem regularnym,
- jest wyrażeniem regularnym,
- gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym,
- gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym,
- gdzie jest wyrażeniem regularnym jest wyrażeniem regularnym.
Ta definicja pochodzi ze strony 64 z
Sipser, Michael. Wprowadzenie do teorii obliczeń, wydanie trzecie. Cengage Learning, 2012.
Teraz mam następujące pytania.
- Dlaczego nie zawierają definicji
intersection
,complement
lubreverse
operacji? - Jeśli zmienimy czwarty element na , czy otrzymamy równoważną definicję, tj. Dla każdego języka regularnego istnieje zmodyfikowane wyrażenie regularne i odwrotnie?
- Wiem, że ta definicja jest kompletna i dobrze zdefiniowana, ale dlaczego jest lepsza od innych równoważnych, dobrze zdefiniowanych i kompletnych definicji?
formal-languages
regular-languages
regular-expressions
Ali Shakiba
źródło
źródło
Odpowiedzi:
1) Jeśli zezwolimy również na przecięcie i uzupełnienie, wówczas wyrażenia wynikowe są czasami nazywane rozszerzonymi wyrażeniami regularnymi; ponieważ zwykłe języki są zamknięte na operacje logiczne, nic nie zyskuje. To tylko cukier syntaktyczny. Podobny wniosek dotyczy operacji odwrotnej. Jednym z powodów, dla których w pierwszej instancji nie wspomniano o wszystkich innych operacjach, jest cel, aby definicja była jak najprostsza, tak aby (indukcyjne) dowody nie musiały zajmować się wieloma przypadkami. Inną przyczyną może być to, że jeśli zezwalamy na niektóre operacje, ale w innych przypadkach, w niektórych przypadkach nie powstają bardzo odmienne (nieregularne) klasy językowe, na przykład jeśli weźmiemy pod uwagę rozszerzone wyrażenie regularne bez operatora gwiazdy, wówczas otrzymujemy odpowiednią podklasę klas regularnych , tak zwane języki bez gwiazd lub aperiodyczne, patrz wikipedia: język bez gwiazd .
2) Jeśli zachowamy pozycje 1. - 6., ale po prostu zmienimy pozycję 4. używając przecięcia zamiast związku, otrzymamy odpowiednią podklasę zwykłych języków. Na przykład nie moglibyśmy już opisać języka ponieważ wiązałoby się to ze zjednoczeniem i (patrz dowód poniżej). Jeśli pozwolimy na uzupełnienie, rzeczy się zmienią, ponieważ mamy związek z powrotem przez prawa DeMorgan.L={a,b} {a} {b}
3) Częściowo odpowiedziałem na to w 1), ale co masz na myśli mówiąc, że ta definicja jest preferowana? Znam definicje, w których 2. jest pomijane (jak mamy do 6., że ) lub 3. jest pomijane (ponieważ mamy )) lub oba są pominięte; więc ta nie jest minimalną możliwą definicją (daje nam również cukier składniowy, ponieważ mamy dodatkowe symbole do opisania i ).L(∅∗)={ε} ∅=L(X∗¯¯¯¯¯¯¯ {ε} ∅
EDYCJA : Mój pierwszy wspomniany komentarz w 2) był niepoprawny, języki w zamknięciu indukcyjnym w , i niekoniecznie są podzbiorami dla niektórych , na przykład rozważ . Niemniej jednak mamy do czynienia z tym, że nie może być opisane takim wyrażeniem. Dam dowód, a mianowicie, że jeśli dla jakiegoś wyrażenia ze zmodyfikowanym 4. elementem, to jeśli (a stąd ) Dowód przechodzi przez indukcję wyrażenia∘ ∗ ∩ x∗ x∈X L(a∘b)={ab} L={a,b} L=L(R) X={a,b} a≠b
Uwaga: Jeden powszechnie używany wniosek: jeśli , to lub . Wynika to z, stąd i lub i . W pierwszym przypadku mamy i stąd .a=uw u=a w=a 1=|a|=|uw|=|u|+|w| |u|=0 |w|=1 |u|=1 |w|=0 u=ε a=w
źródło
Raport techniczny, który wprowadził języki regularne, wyrażenia regularne i automaty skończone, zadaje pytanie na stronie 70:
(Wkrótce potem zauważono, że jest wygodniejszym operatorem niż i ma równoważną moc. W dzisiejszych czasach zamiast tego używamy ).E∗ E∗F E∗
Odpowiedź zajmuje kilka stron. Po pierwsze, należy zauważyć, że należy szukać odpowiedzi na pytanie, czy powstałe języki tworzą interesującą klasę i jak porównują się z językami opisanymi innymi sposobami. Na stronie 72 zaznaczono, że negacja i koniunkcja są zbędne: nie dodają żadnej ekspresyjnej mocy. Na stronie 80 i dalszych udowodniono, że zwykłe języki są dokładnie tymi językami rozpoznawanymi przez skończone maszyny stanów.
Innymi słowy: odpowiedź Stefana można bezpiecznie uznać za rozstrzygającą, ponieważ została już podana w raporcie, który po raz pierwszy wprowadził te pojęcia.
źródło
Z tego wyboru operatorów (zjednoczenie, konkatenacja i gwiazda) można zbudować NFA o wielkości liniowej do wielkości wyrażenia. Z drugiej strony, jeśli dodasz przecięcie i uzupełnienie, rozmiar równoważnego automatu może eksplodować nie elementarnie, co zwykle nie jest pożądane.
źródło