Πεπερασμένα αυτόματα και κανονικές εκφράσεις

Εισαγωγή

• Ο σχεδιασμός και η υλοποίηση γλωσσικών εργαλείων υποστηρίζεται από ένα ευρύ φάσμα θεωρητικής γνώσης.
• Αυτή περιλαμβάνει μεταξύ άλλων:
  • τον αφηρημένο ορισμό μιας γλώσσας,
  • τον ορισμό ενός αυτομάτου που μπορεί να αναγνωρίσει μια γλώσσα,
  • τον ορισμό γραμματικών που περιγράφουν μια γλώσσα,
  • την ισοδυναμία αυτομάτων και γλωσσών και
  • αλγορίθμους για την αποδοτική υλοποίηση των παραπάνω.

Συμβολισμοί

Αλφάβητο (alphabet):

Πεπερασμένο σύνολο συμβόλων

Συμβολοσειρά (string):

Πεπερασμένη ακολουθία συμβόλων. Το μήκος της συμβολοσειράς χ συμβολίζεται ως |χ|.

Κενή συμβολοσειρά (empty string):

Συμβολοσειρά με μήκος 0. Συμβολίζεται ως ε.

Παράθεση (concatenation):

Η δημιουργία μιας νέας συμβολοσειράς από δύο άλλες (x, y) με τη σειριακή παράθεση των συμβόλων τους. Συμβολίζεται ως xy

Γλώσσα (language):

Ένα υποσύνολο των συμβολοσειρών που μπορούν να δημιουργηθούν από ένα συγκεκριμένο αλφάβητο.

• Παράθεση δύο γλωσσών: LM = { xy | x ε L και y ε M }
• Ένωση δύο γλωσσών: L U M = { xy | x ε L ή y ε M }
• κλείσιμο (closure) μιας γλώσσας L: L^* = U_i=0^άπειροLⁱ
• θετικό κλείσιμο (positive closure) μιας γλώσσας L: L⁺ = U_i=1^άπειροLⁱ

Πεπερασμένα αυτόματα

• πεπερασμένα αυτόματα (finite automata) και τα
• αυτόματα στοίβας (push down automata)

Τα πεπερασμένα αυτόματα ορίζονται από την πεντάδα Μ = (Κ, Σ, δ, S, F):

K

Πεπερασμένο σύνολο καταστάσεων

Σ

Πεπερασμένο αλφάβητο εισόδου

δ

συνάρτηση αλλαγής κατάστασης (transition function) από μια κατάσταση Χ σε μια Χ' με βάση ένα σύμβολο εισόδου σ. δ(Χ, σ) = Χ'

S

Αρχική κατάσταση

F

Σύνολο τελικών καταστάσεων

Αν η συνάρτηση δ είναι μονότιμη τότε το αυτόματο αυτόματο καλείται ντετερμινιστικό πεπερασμένο αυτόματο (ΝΠΑ) (deterministic finite automaton (DFA)). Αντίθετα, αν για κάποιες τιμές (Χ, σ) της δ υπάρχουν πολλές πιθανές νέες καταστάσεις X' τότε το αυτόματο καλείται μη ντετερμινιστικό πεπερασμένο αυτόματο (ΜΠΑ) (non-deterministic finite automaton (NFA)). Οι γλώσσες που αναγνωρίζονται από τα πεπερασμένα αυτόματα λέγονται κανονικές γλώσσες (regular languages). Οι γλώσσες αυτές είναι κατάλληλες για να περιγράψουν τις λεκτικές μονάδες ενός προγράμματος.

Ένα πεπερασμένο αυτόματο μπορεί να παρασταθεί ως:

• γράφος μετάβασης (transition graph)
• πίνακας αλλαγής κατάστασης (transition table)

Κανονικές εκφράσεις

• Για ένα σύμβολο της αλφαβήτου a η κανονική έκφραση a συμβολίζει τη γλώσσα {a}.
• Αν R και S δύο κανονικές εκφράσεις για τις γλώσσες L_R και L_S τότε:
  • η έκφραση R|S συμβολίζει τη γλώσσα L_R U L_S.
  • η έκφραση R.S συμβολίζει τη γλώσσα L_R . L_S.
  • η έκφραση R^* συμβολίζει τη γλώσσα L_R^*.
  • η έκφραση R⁺ συμβολίζει τη γλώσσα L_R⁺.

Κανονικές εκφράσεις στο Unix

^

Αρχή της γραμμής

$

Τέλος της γραμμής

.

Οποιοδήποτε γράμμα

[abc]

Ένα από τα γράμματα a, b, ή c

[a-z]

Ένα από τα γράμματα a μέχρι z

[^abc]

Οποιοδήποτε γράμμα εκτός από τα a, b, και c.

Έκφραση*

Η έκφραση μηδέν ή περισσότερες φορές

Έκφραση+

Η έκφραση μία ή περισσότερες φορές

Έκφραση?

Η έκφραση μία ή καμία φορά

Έκφραση1|Έκφραση1

Η έκφραση1 ή η έκφραση2

(Έκφραση)

Το περιεχόμενο στην παρένθεση

Παράδειγμα: (με την εντολή cd ~dspin φτάνετε σε έναν κατάλογο που περιέχει ένα αρχείο με πολλές λέξεις (words))

athena:~> egrep 'abo' words
...
sabotage
seaboard
taboo
thereabouts
turnabout
vagabond
whereabout
...

athena:~> egrep '^abo' words
aboard
abode
abolish
abolition
abominable
abominate
aboriginal                 

athena:~> egrep bent words
absorbent
bent
benthic
debenture
incumbent
recumbent

athena:~> egrep 'bent$' words
absorbent
bent
incumbent
recumbent                                  

athena:~> egrep "heaven|hell" words
eggshell
heaven
heavenly
heavens
hell
hellfire
hellish
hello
hells
...

athena:~> egrep "(ga)(ba)+" words
gabardine
megabaud

athena:~> egrep pe+l words
..
peel
peeled
...

Ασκήσεις

1. Να γράψετε ως κανονικές εκφράσεις τις παρακάτω εκφράσεις του egrep:

   w[xyz]k*
   a[^a-x]q
   a(b?)
   

2. Να σχεδιάσετε ένα γράφο μετάβασης που να αναγνωρίζει τη γλώσσα με τις παρακάτω συμβολοσειρές:

   Kadafi
   Gadafi
   Ghadafi
   Khadafi
   

3. Να σχεδιάσετε ένα γράφο μετάβασης που να αναγνωρίζει την κανονική έκφραση a^* . (b | c) . (d | b)⁺.

Βιβλιογραφία

• Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές σ. 15-23. Συμμετρία 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms, pages 318–3335. Addison-Wesley, 1974.
• Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools, pages 83–157. Addison-Wesley, 1985.

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:27 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».