Κανονικές εκφράσεις (Regular expressions)

Οι κανονικές εκφράσεις (ή παραστάσεις) είναι αλγεβρικές παραστάσεις που εκφράζουν (παράγουν) μια κανονική γλώσσα.

Μια κανονική έκφραση συμβολίζεται συνήθως με R ή r ή re.

Η γλώσσα που παράγεται από μια r συμβολίζεται με L(r).

Θεώρημα

Μια γλώσσα L μπορεί να παρασταθεί με κανονική έκφραση αν είναι κανονική. Δηλαδή L=L(M) όπου Μ πεπερασμένο αυτόματο.

Πράξεις και τελεστές

Οι πράξεις που μπορούμε να χρησιμοποιήσουμε είναι:

  • Παράθεση ή συνένωση (concatenation)
  • Ένωση (union)
  • Άστρο του Kleene (Kleene star)

Τελεστές που μπορούμε να χρησιμοποιήσουμε είναι:

  • Η τελεία (.) για την παράθεση η οποία όμως παραλείπεται για συντομία.
  • Το σύμβολο συν (+) για την ένωση.
  • Το σύμβολο αστερίσκος (*) για το άστρο του Kleene.

Επίσης ισχύουν:

  • R = ∅ (Εκφράζει τη γλώσσα L = ∅)
  • R = ε (Εκφράζει τη γλώσσα L = {ε})
  • R = α (Εκφράζει τη γλώσσα L = {α} όπου α ∈ Σ (γλώσσα με ένα σύμβολο))
  • R = w (Εκφράζει τη γλώσσα L = {w} όπου w ∈ Σ* (γλώσσα με μία λέξη))

Παραδείγματα με πράξεις των παραπάνω τελεστών.

(r+s): Εκφράζει τη γλώσσα L = L(r) ⋃ L(s)
(rs): Εκφράζει τη γλώσσα L = L(r)L(s)
(r*): Εκφράζει τη γλώσσα L = L(r) = L*

Μπορούμε να χρησιμοποιήσουμε παρενθέσεις για να ξεχωρίσουμε ενότητες όπως σε κάθε αλγεβρική παράσταση. Για παράδειγμα: (r+s)r.

Προτεραιότητα τελεστών

Η προτεραιότητα τελεστών έχει όπως παρακάτω:

  • Άστρο Kleene
  • Παράθεση ή συνένωση (concatenation)
  • Ένωση (union)

Παραδείγματα

Μερικά παραδείγματα από κανονικές εκφράσεις.

R = a(a + b)* (οι λέξεις αρχίζουν πάντα με a)
R = (a + b)*aa(a + b)* (οι λέξεις περιέχουν πάντα τουλάχιστον δύο συνεχόμενα a)
R = (a + ε)(ba + b)* (οι λέξεις δεν περιέχουν συνεχόμενα a)
R = a*b*

Ιδιότητες κανονικών εκφράσεων

∅ + R = R + ∅ = R
∅R + R∅ = R∅ + ∅R = ∅
εR = Rε = R
ε* = ε
∅* = ε
R + R = R
R + Q = Q + R (αντιμεταθετική)
(R + Q) + P = R + (Q + P) (προσεταιριστική)
(RQ)P = R(QP) (προσεταιριστική)
R(Q + P) = RQ + RP (επιμεριστική)
(Q + P)R = QR + PR (επιμεριστική)
R*R* = R*
RR* = R*R
(R*)* = R*
ε + RR* = ε + R*R = R*
(PQ)*P = P(QP)*
(P + Q)* = (P*Q*)* = (P* + Q*)*

Επίσης οι παρακάτω εκφράσεις είναι ισοδύναμες.

(x + y)∗
(x∗ + y)∗
x∗(x + y)∗
(x + yx∗)∗
(x∗y∗)∗
x∗(yx∗)∗
(x∗y)∗x

Το θεώρημα του Arden

Εάν P και Q είναι δύο κανονικές εκφράσεις στο Σ, και εάν η P δεν περιέχει το ε, τότε η ισότητα R = Q + RP έχει μια μοναδική λύση: R = QP*.

Το θεώρημα του Arden είναι χρήσιμο στη μετατροπή πεπερασμένων αυτόματων σε κανονικές εκφράσεις.

Να αποδειχτεί ότι:

(1+00*1)+(1+00*1)(0+10*1)*(0+10*1) = 0*1(0+10*1)*

Να σχεδιάσετε εκφράσεις για τις παρακάτω γλώσσες στο αλφάβητο Σ = {a, b}.

  • Γλώσσα με λέξεις μήκους 2 συμβόλων
  • Γλώσσα με λέξεις μήκους τουλάχιστον 2 συμβόλων
  • Γλώσσα με λέξεις μήκους μέχρι 2 συμβόλων

Έστω το αλφάβητο ∑ = {a, b, c}. Να βρείτε την κανονική έκφραση για λέξεις που θα περιέχουν μόνο ένα a.

Έστω το αλφάβητο ∑ = {a, b}. Να βρείτε την κανονική έκφραση για λέξεις που θα περιέχουν τουλάχιστον τρία συνεχόμενα b.

Έστω το αλφάβητο ∑ = {a, b}. Να βρείτε την κανονική έκφραση για λέξεις που θα αρχίζουν με δύο συνεχόμενα a.

Έστω το αλφάβητο ∑ = {a, b}. Να βρείτε την κανονική έκφραση για λέξεις που θα αρχίζουν με b και θα τελειώνουν με δύο συνεχόμενα a.

Έστω το αλφάβητο ∑ = {a, b}. Να βρείτε την κανονική έκφραση για λέξεις που θα τελειώνουν σε aba ή aaba.

Έστω το αλφάβητο ∑ = {a, b, c}. Να βρείτε την κανονική έκφραση για λέξεις που θα περιέχουν από 0 μέχρι 3 a.

Hint: (ε + a) σημαίνει 0 ή 1 a