96002

Przykład:

Niech T = {a, b}. Zbiór regularny nad T:

{e, a, ab, abb, abbb, abbbb, ...} = {e} u {a} {b}' zapisujemy jako slab*

Przykład:

(011) 011 odpowiada zbiorowi

«0}u{l»* {0>{1 }{1) = {0, 1}* {011} będącemu dowolnym ciągiem zer i jedynek zakończonym sekwencją: 011

Dwa wyrażenia p i q regularne są równe (równoważne), gdy odpowiadające im zbioiy regularne P i Q są równe (identyczne).

Zapisując wył ażenia regularne stosujemy następujące priorytety operatorów:

(1)    () - najwyższy,

(2) *

(3)    * - (kcukalenacja)

(4)    | - najniższy.

Niech p, q i r będą dowolnymi wyrażeniami regularnymi Prawdziwe są następujące zależności i tożsamości: plq = qlp pl(qlr) = (plq)lr p(qr) = (pq)r pqlpr = p(qlr) pqlrq = (plr)q

ep = pe = p 0p = P0 = 0 e‘ = e 0' = e

p‘ = pip" = (ple)*

<pY = p‘

plp = p pl0 = p elp' = p' elpp' = p'

Elp*p = p* pqqlpq" = pq'

(plq)* = (p’lqV = (p’q*)"