5.1 Τρ, 24/9/02: Εισαγωγικά

Μιλήσαμε κατ' αρχήν για ορισμένες έννοιες τις οποίες θα μελετήσουμε κατά τη διάρκεια του εξαμήνου. Το μάθημα συνίσταται ουσιαστικά σε μια μελέτη ορισμένων μοντέλων υπολογισμού, ή, αντίστοιχα, στη μελέτη κλάσσεων γλωσσών που αναγνωρίζονται από τα μοντέλα αυτά. Το μοντέλο υπολογισμού από το οποίο θα αρχίσουμε είναι η λεγόμενη μηχανή πεπερασμένων καταστάσεων και η αντίστοιχη κλάσση γλωσσών που αναγνωρίζονται από μηχανές πεπερασμένων καταστάσεων είναι οι κανονικές γλώσσες (regular languages).

Ορίσαμε τις έννοιες:

1. Αλφάβητο $\Sigma$ είναι ένα οποιδήποτε πεπερασμένο σύνολο, του οποίου τα στοιχείά ονομάζουμε σύμβολα ή γράμματα. Π.χ. $\Sigma = {\left\{{0, 1}\right\}}$ ή $\Sigma$ = όλα τα γράμματα και σημεία στίξης της Ελληνικής γλώσσας.
2. Λέξη πάνω από ένα αλφάβητο $\Sigma$ λέγεται μια πεπερασμένη ακολουθία γραμμάτων του $\Sigma$, ενδεχομένως και κενή (η κενή λέξη συμβολίζεται πάντα με το $\epsilon$). Π.χ. αν $\Sigma = {\left\{{0, 1}\right\}}$ τότε $w = 0101$ είναι μια λέξη πάνω από το $\Sigma$, με μήκος ${\left\vert{w}\right\vert} = 4$. Η κενή λέξη $\epsilon$ έχει μήκος 0.
3. Μια γλώσσα $L$ πάνω από ένα αλφάβητο $\Sigma$ είναι ένα οποιοδήποτε σύνολο, πεπερασμένο ή άπειρο, λέξεων πάνω από το $\Sigma$. Π.χ., αν $\Sigma = {\left\{{0, 1}\right\}}$ το σύνολο
   $$Q = {\left\{{w: \exists k\in {\mathbf N}: {\left\vert{w}\right\vert} = k^2}\right\}}$$
   είναι η γλώσσα όλων των δυαδικών λέξεων με μήκος που είναι τέλειο τετράγωνο. Μια γλώσσα $L$ μπορεί να περιέχει την κενή λέξη ή όχι.
4. Αν $\alpha = \alpha_1 \ldots \alpha_m$ και $\beta = \beta_1 \ldots \beta_n$ είναι δύο λέξεις πάνω από το $\Sigma$ με μήκη $m$ και $n$, τότε ορίζουμε τη συγκόλληση (concatenation) $\alpha\beta$ να είναι η λέξη $\alpha_1\ldots\alpha_m\beta_1\ldots\beta_n$, που έχει μήκος το άθροισμα των μηκών. Προφανώς ισχύει πάντα $\alpha\epsilon = \epsilon\alpha = \alpha$, για κάθε λέξη $\alpha$.

   Μια λέξη $\pi$ λέγεται πρόθεμα (prefix) μιας λέξης $\alpha$ αν υπάρχει λέξη $\beta$ τ.ώ. $\alpha = \pi\beta$. Ομοίως η $\pi$ λέγεται επίθεμα (suffix) της $\alpha$ αν υπάρχει $\beta$ τ.ώ. $\alpha = \beta\pi$. Είναι φανερό ότι μια λέξη με μήκος $n$ έχει ακριβώς $n+1$ προθέματα και άλλα τόσα επιθέματα.

5. Αν $L_1, L_2$ είναι δύο γλώσσες πάνω από το $\Sigma$ ορίζουμε τη γλώσσα
   $$L_1L_2 = {\left\{{xy: x\in L_1, y\in L_2}\right\}}.$$
   Ορίζουμε επίσης $L^0 = {\left\{{\epsilon}\right\}}$ και για $n\ge 1$ $L^n = L L \cdots L$ (συγκόλληση της $L$ με τον εαυτό της $n$ φορές). Τέλος ορίζουμε
   $$L^*=\bigcup_{k=0}^\infty L^k$$
   και
   $$L^+=\bigcup_{k=1}^\infty L^k.$$
   Με βάση αυτούς τους συμβολισμούς, και παρατηρώντας ότι με $\Sigma$ πέρα από το αλφάβητο συμβολίζουμε και τη γλώσσα πάνω από το $\Sigma$ με στοιχεία όλες τις λέξεις πάνω από το $\Sigma$ με ένα ακριβώς γράμμα, έχουμε ότι $\Sigma^*$ είναι η γλώσσα όλων των λέξεων πάνω από το $\Sigma$ και $\Sigma^+$ είναι η γλώσσα όλων των μη κενών λέξεων πάνω από το $\Sigma$. Έτσι, αντί να λέμε ότι $L$ είναι μια γλώσσα πάνω από το $\Sigma$ γράφουμε απλώς $L \subseteq \Sigma^*$.

   Για να βεβαιωθείτε ότι έχετε καταλάβει το περιεχόμενο της σημερινής διάλεξης βεβαιωθείτε ότι καταλαβαίνετε τι περιγράφει η γλώσσα

   $${\left\{{+,-,\epsilon}\right\}}1{\left\{{0,1}\right\}}^*.$$
   Αυτή είναι η συγκόλληση τριών γλωσσών, της ${\left\{{+,-,\epsilon}\right\}}$, της $1$ (συντομογραφία της γλώσσας ${\left\{{1}\right\}}$ με ένα στοιχείο) και της ${\left\{{0,1}\right\}}^*$. Όταν, όπως εδώ, δεν περιγράφουμε το αλφάβητο, αυτό συνάγεται από όλα τα σύμβολα που έχουν χρησιμοποιηθεί, στην προκειμένη περίπτωση δηλαδή $\Sigma = {\left\{{0,1,+,-}\right\}}$.
6. Ένα κατευθυνόμενο γράφημα είναι μια συλλογή από κορυφές και ακμές που τις ενώνουν, όπως στο σχήμα παρακάτω. Λέγεται κατευθυνόμενο επειδή υπάρχει η έννοια της κατεύθυνσης πάνω στις ακμές. Οι δε ακμές μπορούν να ενώνουν και μια κορυφή με τον εαυτό της, όπως επίσης μπορούν να υπάρχουν και πολλαπλές ακμές που ενώνουν το ίδιο ζεύγος κορυφών.

   
   Σχήμα 1. Ενα κατευθυνόμενο γράφημα με 4 κορυφές και 6 ακμές.
   Σε ένα γράφημα δεν έχει καμία σημασία ο τρόπος που το σχεδιάζουμε πάνω στο χαρτί, αλλά αυτό που μας ενδιαφέρει είναι μόνο ποια κορυφή συνδέεται με ποια.

   Σε ένα τέτοιο γράφημα μονοπάτι αποτελεί μια οποιαδήποτε πεπερασμένη ακολουθία διαδοχικών κορυφών. Οι κορυφές $u$ και $v$ λέγονται διαδοζικές αν υπάρχει η ακμή $u \to v$. Έτσι, στο σχήμα που φαίνεται παραπάνω το 24231 είναι ένα μονοπάτι μήκους 4 (το μήκος είναι το πόσες ακμές διανύονται στο μονοπάτι). Αν αρχή και τέλος του μονοπατιού συμπίπτουν αυτό λέγεται κύκλος, π.χ. το 424.

Άσκηση 5.1.1   Πόσες λέξεις μήκους $n$ υπάρχουν πάνω από ένα αλφάβητο με $k$ γράμματα;

Άσκηση 5.1.2   Δείξτε ότι για κάθε γλώσσα $L$ και φυσικούς αριθμούς $m, n$ ισχύει $L^{m+n} = L^m L^n$.

Άσκηση 5.1.3   Έστω κατευθυνόμενο γράφημα $G$ με $n$ κορυφές και μονοπάτι στο $G$ μέ μήκος $k\ge n$. Δείξτε ότι το μονοπάτι περιέχει ένα κύκλο, ένα υπομονοπάτι δηλ. του τύπου $u_1 \to u_2 \to \cdots \to u_l$ με $u_1 = u_l$.