614372768

Zapis wyrażeń regularnych warto uprościć poprzez wprowadzenie kilku założeń. Jeśli, operator * ma wyższy priorytet niż złożenie lub +, oraz jeśli złożenie ma wyższy priorytet niż + to wyrażenie ((0(1*)) + 0) można zapisać jako 01* + 0. Efektem przyjęcia priorytetów jest możliwość opuszczenia zbędnych nawiasów. Wyrażenia typu rr* można skracać do r⁺. Zakładamy także, że r¹ = rrrrr ^.. rrr.

Podsumowując w wyrażeniach regularnych stosujemy następujące priorytety operatorów:

1.    () - najwyższy priorytet,

2.    *

3.    • - (złożenie)

4.    + - najniższy priorytet.

Przykład 2 Wyrażenie 00 jest wyrażeniem regularnym reprezentującym {00}. Wyrażenie (0+1)* reprezentuje wszystkie słowa złożone z zer oraz jedynek. Inne wyrażenie (0 + l)*00(0 + l)* opisuje zbiór wszystkich łańcuchów zer oraz jedynek, zawierających przynajmniej dwa kolejne zera. Wyrażenie (1+10)* to zbiór wszystkich łańcuchów zer oraz jedynek które rozpoczynają się od jedynki ale nie zawierają dwóch kolejnych zer. Przykładem jest słowo 1101011 które, jeśli podzielimy na 1 — 10 —10 — 1 — 1 jasno wskazuje iż jest słowem generowanym przez (1 + 10)*. Wyrażenie (0 + 1)*011 opisuje wszystkie łańcuchy zer i jedynek kończące się 011. Słowa generowane przez wyrażenie 0*1*2* to dowolnej długości ciągi zer. a następnie jedynek i na końcu dwójek. Podobnym wyrażenie 00*11*22* które jest podobne jak poprzednie ale gwarantuje, że zawsze będzie przynajmniej jedno zero, jedna jedynka bądź dwójka. Nieco bardziej skrótowo można to zapisać jako 0⁺l⁺2⁺.

3.1 Prawa algebry zbiorów/języków regularnych

Niech p, q i r będą dowolnymi wyrażeniami regularnymi. Prawdziwe są następujące zależności i tożsamości:

p\q = q\p	p\(q\r) = (p|ą)|r
p(qr) = (pq)r	pq\pr = p(q\r)
pq\rq = (p\r)q	Ap = pA = p
Dp = p0 = 0	A* = A
0* = A	P* = pIp* = (pM*
(pT = P*	P|P = P
p|0 — p	A|p* = p*
A|pp* = p*	A|p*p = p*
pqq*\pq’ = pq*	(p|ą)* = (p*|ą*)* = (p*ą*)*

Przykład 3 Dla przykładu zostanie udowodnione przedostatnie prawo z przedstawionej listy: abb*\ab* — ab*

ponieważ:

abb*\ab* = (ab)(b)* U (a)(6)* = (ab,abb,abbb,...) U (a, ab, abb,...) = (a, ab, abb,...) = (a)(6)*

4 Zadania

1.    Udowodnić twierdzenie 1.

2.    Udowodnić twierdzenie 2.

3.    Udowodnić twierdzenie 3.

4.    Podać formalny opis oraz tabelę przejścia dla funkcji S dla dwóch następujących automatów:

• deterministyczny automat akceptujący liczby rzeczywiste zapisane w notacji o następującym przykładzie 10.23E —14:

15