Z Wikipedii

Skocz do: nawigacji, szukaj

Wyrażeniem regularnym nad alfabetem $Σ$ nazywamy ciąg znaków składający się z symboli $\varnothing, \epsilon, +, ^*, ), ($ oraz symboli z alfabetu $Σ$ następującej postaci:

$\varnothing, \epsilon$ są wyrażeniami regularnymi;
wszystkie symbole z $Σ$ są wyrażeniami regularnymi;
jeśli $e 1, e 2$ są wyrażeniami regularnymi, to są nimi również $e_1^*, (e_1), e_1e_2, e_1+e_2$ ;
wszystkie wyrażenia regularne są postaci opisanej w punktach 1-3.

Gwiazdka wiąże najsilniej, konkatenacja słabiej, suma najsłabiej. Każde wyrażenie regularne definiuje pewien język formalny. Każdy język definiowany przez wyrażenie regularne jest regularny.

Spis treści

1 Formalna definicja
2 Przykłady
- 2.1 Przykład 1
- 2.2 Zobacz też

[edytuj] Formalna definicja

Język definiowany przez wyrażenie regularne jest definiowany indukcyjnie. Niech L(w) oznacza język definiowany przez w. Wtedy baza indukcji jest następująca:

$L(\epsilon) = \{\epsilon\}\,$ (zbiór zawierający tylko słowo puste)
$L(\varnothing) = \varnothing$ (zbiór pusty)
$L(a) = \{a\}\,$ dla dowolnego a z alfabetu

Natomiast do konstrukcji wyrażeń służą 3 symbole:

$L(w+v) = L(w) \cup L(v)$ (suma języków)
$L(w^*) = (L(w))^* \,$ (domknięcie Kleene'ego)
$L(wv) = \{xy : x\in L(w) \wedge y \in L(v) \}$ (konkatenacja języków)

[edytuj] Przykłady

[edytuj] Przykład 1

Wyrażenie $(a+b)^*baba(a+b)^*\,$ definiuje język wszystkich słów nad alfabetem ${a, b}$ , które zawierają podsłowo baba.

[edytuj] Zobacz też

Polska liderem w pokazywaniu europejskich produkcji

Europejskie stacje telewizyjne przeznaczają ponad 65 proc. czasu antenowego na produkcje europejskie, w tym ponad 36 proc. na produkcje niezależnych producentów z UE - wynika z piątkowego raportu Komisji Europejskiej. Polska jest liderem rankingu krajów UE.

TVP procesuje się z "Dziennikiem"

Przeprosin i wpłaty 200 tys. na cel społeczny żąda TVP od "Dziennika" za artykuł pt. "Korupcja w TVP" - o domniemanej propozycji wiceszefowej Agencji Informacji TVP Patrycji Koteckiej wyższych wycen za materiały kompromitujące PO.

Maks Kolonko procesuje się z "Faktem"

Przeprosin i 100 tysięcy zł zadośćuczynienia żąda od wydawcy "Faktu" znany prezenter TV Mariusz Maks Kolonko za nazwanie go "łajdakiem" i sugestię, że swój związek z Weroniką Rosati traktował instrumentalnie.

Powstaje audiobook o Śląsku

Sześć płyt i książka z esejami złożą się na audiobook poświęcony Śląskowi. Ma to być dźwiękowy pejzaż regionu.

Dodatek o Powstaniu Warszawskim w "Rzeczpospolitej"

Dzisiaj dziennik "Rzeczpospolita" (Presspublica) ukaże się z dodatkiem poświęconym Powstaniu Warszawskiemu – "Warszawa '44".

Linki: Strona g��wna

Encyklopedia