05_WR_wyrazenia_regularne.pdf

(226 KB) Pobierz
WYRAņENIA REGULARNE.
WyraŇenia regularne nad alfabetem sĢ to napisy zbudowane
z symboli alfabetu , symboli , , znakw dziaþaı
+,
,
oraz nawiasw.
+
+
()
()
Np.: b
a + ,
a
b
+
,
aa
b
b
.
Piszemy
zamiast
.
Def. WyraŇenia regularne nad alfabetem sĢ napisami
okreĻlonymi przez nastħpujĢce warunki indukcyjne:
a) kaŇde
a jest wyraŇeniem regularnym,
b) i sĢ wyraŇeniami regularnymi,
c) jeŇeli i
sĢ wyraŇeniami regularnymi, to napisy
()
sĢ wyraŇeniami regularnymi.
()
+ ,
()
i
Zasady opuszczania nawiasw:
- opuszczamy zewnħtrzne nawiasy.
- uwzglħdniamy siþħ wiĢzania symboli dziaþaı (od
najsilniejszego): *, , +
() () ( )
+
+
()
()
Np.:
a
a
b
ac
znaczy
a
a
b
ac
.
+
+
KaŇde wyraŇenie nad oznacza pewien jħzyk nad .
Def. KaŇdemu wyraŇeniu przyporzĢdkowujemy jħzyk
L
()
przez indukcjħ po budowie :
L = dla
(){}
a
a
a
L
()
(){}
=
L
()()()
=
L
=+
L
L
()()()
=
L
L
() ()
=
L
L
Jħzyk
L nazywamy jħzykiem oznaczonym przez
wyraŇenie .
()
Def. RwnoĻę wyraŇeı regularnych
RwnoĻę
= jest prawdziwa dla wyraŇeı regularnych
i
, jeĻli
L = .
()()
L
Wszystkie prawdziwe rwnoĻci moŇna wyprowadzię
z aksjomatw algebry Kleene'go.
AKSJOMATY ALGEBRY KLEENEÓGO
Def.
=
+
(K1)
() ()
++
+
=
+
(K2)
=+
+
(K3)
=+
(K4)
+
=
(K5)
() ()
=
(K6)
=
=
=
=
(K7)
()
+
=
+
(K8)
()
+
=
+
=
(K9)
+
=
(K10)
+
(K11)
(K12)
TWIERDZENIA ALGEBRY KLEENEÓGO
(T1)
(T2)
=
(T3)
(T4)
(T5)
+
+
+
+
(T6)
+
+ ,
(T7)
+
(T8)
(T9)
(T10)
(T11)
=
()
(T12)
=
(T13)
(T14)
=
++
(T15)
() ()
(T16)
=+
() ()
(T17)
=
1012115941.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin