Dlaczego wyrażenia regularne są definiowane za pomocą operacji łączenia, łączenia i operacji gwiazdowych?

11

Regularne expresssion jest zdefiniowany rekurencyjnie jako

$a$ dla niektórych jest wyrażeniem regularnym, $a \in \Sigma$
$\varepsilon$ jest wyrażeniem regularnym,
$\emptyset$ jest wyrażeniem regularnym,
$(R_1 \cup R_2)$ gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym, $R_1$ $R_2$
$(R_1 \circ R_2)$ gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym, $R_1$ $R_2$
$(R_1)^*$ gdzie jest wyrażeniem regularnym jest wyrażeniem regularnym. $R_1$

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, complementlub reverseoperacji?
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? $R_1 \cap R_2$
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

2

Ogranicz się do jednego pytania na post.

— Raphael

16

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(\emptyset^{\ast}) = \{\varepsilon\}$ $\emptyset = L(\overline{ X^{\ast} }$ $\{\varepsilon\}$ $\emptyset$

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 $\circ$ $^{\ast}$ $\cap$ $x^{\ast}$ $x \in X$ $L(a\circ b) = \{ab\}$ $L = \{a,b\}$ $L = L(R)$ $X = \{a,b\}$ $a\ne b$

{a, b} \subseteq L \Rightarrow a b \in L .

$\{a,b\} \subseteq L \Rightarrow ab \in L.$

R

$R$ . W przypadku przypadku podstawowego zachowuje się on pusto, teraz załóżmy, że dotyczy on . Jeśli i , to stąd hipoteza indukcyjna mamy . Jeśli to jako musimy mieć i lub odwrotnie. Załóżmy pierwszy przypadek. Jeśli , to przez hipotezę indukcyjną, stąd

L (R_{1}), L (R_{2})

$L(R_1), L(R_2)$

L = L (R_{1} \cap R_{2}) = L (R_{1}) \cap L (R_{2})

$L = L(R_1 \cap R_2) = L(R_1) \cap L(R_2)$

{a, b} \subseteq L

$\{a,b\} \subseteq L$

{a, b} \subseteq L (R_{i}), i = 1, 2

$\{a,b\} \subseteq L(R_i), i = 1,2$

a b \in L (R_{1}) \cap L (R_{2})

$ab \in L(R_1) \cap L(R_2)$

{a, b} \subseteq L (R_{1} \circ R_{2}) = L (R_{1}) L (R_{2})

$\{a,b\} \subseteq L(R_1\circ R_2) = L(R_1)L(R_2)$

a = a \cdot ε = ε \cdot a

$a = a\cdot \varepsilon = \varepsilon\cdot a$

a \in L (R_{1})

$a\in L(R_1)$

ε \in L (R_{2})

$\varepsilon \in L(R_2)$

b \in L (R_{1})

$b \in L(R_1)$

a b \in L (R_{1})

$ab \in L(R_1)$

a b = a b \cdot ε \in L (R_{1}) L (R_{2})

$ab = ab\cdot \varepsilon \in L(R_1)L(R_2)$ . Załóżmy teraz, że , to mamy z definicji . Wreszcie, jeśli , a następnie i dla niektórych . Jeśli , znajdujemy podstawie hipotezy indukcyjnej, więc załóżmy , ale daje , podobnie albo albo daje a hipoteza indukcyjna podaje

b \in L (R_{2})

$b \in L(R_2)$

a \cdot b \in L (R_{2}) L (R_{2})

$a\cdot b \in L(R_2)L(R_2)$

L (R_{1}) L (R_{2})

$L(R_1)L(R_2)$

a, b \in L (R_{1}^{*})

$a,b \in L(R_1^{\ast})$

a \in L (R_{1})^{n}

$a \in L(R_1)^n$

b \in L (R_{2})^{m}

$b \in L(R_2)^m$

n, m > 0

$n,m > 0$

n = m = 1

$n = m = 1$

a b \in L (R_{1})

$ab \in L(R_1)$

n > 1

$n > 1$

a \in L (R_{1})

$a \in L(R_1)$

m = 1

$m = 1$

m > 1

$m > 1$

b \in L (R_{1})

$b \in L(R_1)$

a b \in L (R_{1}) \subseteq L (R_{1}^{*})

$ab \in L(R_1) \subseteq L(R_1^{\ast})$ .

◻

$\square$

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 = \varepsilon$ $a = w$

— StefanH
źródło

2

Rzeczywiście nie znajduje się w zestawie „nieregularnych” języków, ale jest dlatego, że .

{a, b}

$\{a,b\}$

{a, b}^{*}

$\{a,b\}^{\ast}$

{a, b}^{*} = (a^{*} \circ b^{*})^{*}

$\{a,b\}^{\ast} = (a^{\ast}\circ b^{\ast})^{\ast}$

— rici

Tak, czasami trudno jest zobaczyć, co można wyrazić, a co nie za pomocą sprytnej kombinacji gwiazdy i innych, które można dosięgnąć dość daleko.

— StefanH

10

Raport techniczny, który wprowadził języki regularne, wyrażenia regularne i automaty skończone, zadaje pytanie na stronie 70:

Pytanie może pojawić się dla czytelnika, dlaczego wybraliśmy poszczególne trzy operacje , i ? $E\vee F$ $EF$ $E*F$

(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.

— reinierpost
źródło

Dzięki za link. Zawsze wyjaśniam moim uczniom, że operacje są naturalnymi abstrakcjami z wyboru (jak jeśli-to-jeszcze) sekwencji (instrukcje następujące po sobie) i iteracji (jak podczas wykonywania). Ale najwyraźniej nie wspomina o tym Kleene?

— Hendrik Jan

Jestem tylko facetem, który przejrzał artykuł Kleene i był zaskoczony, że wszystko w mojej odpowiedzi już tam jest. Nic więcej nie wiem. Sądzę więc, że odpowiedzią jest przeczytanie artykułu i być może poszukiwanie wszystkiego, co wcześniej napisał o tym Kleene.

— reinierpost

4

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.

— doganulus
źródło