7.1 Αλφάβητα, λέξεις και γλώσσες

Ορισμός 7.1   (Αλφάβητο) Αλφάβητο είναι ένα οποιοδήποτε μη κενό πεπερασμένο σύνολο, του οποίου τα στοιχεία ονομάζουμε σύμβολα ή γράμματα .

Παράδειγμα 7.1   Το δυαδικό αλφάβητο $\Sigma_2 = {\left\{{0, 1}\right\}}$. Υπό μία έννοια αυτό είναι το πλέον ενδιαφέρον αλφάβητο. Ένας λόγος είναι ότι αυτό είναι το αλφάβητο που χρησιμοποιείται στους σημερινούς υπολογιστές. Ο σημαντικότερος όμως λόγος είναι ότι το $\Sigma_2$ μπορεί να «μιμηθεί» αποτελεσματικά οποιοδήποτε άλλο αλφάβητο. Το τι σημαίνει αυτό ελπίζουμε να γίνει ξεκάθαρο αργότερα.

Παράδειγμα 7.2   Το αλφάβητο $\Sigma_{GR}={\left\{{A,B,\Gamma,\ldots,\alpha,\beta,\gamma,\ldots,\omega,\ldots}\right\}}$ περιλαμβάνει όλα τα γράμματα και σημεία στίξης της Ελληνικής γλώσσας.

Ορισμός 7.2   (Λέξη) Λέξη πάνω από ένα αλφάβητο $\Sigma$ λέγεται μια πεπερασμένη ακολουθία

$$\alpha = \alpha_1 \ldots \alpha_n$$

γραμμάτων $\alpha_i\in\Sigma$, ενδεχομένως και κενή (δηλ. με $n=0$).

Ο αριθμός $n \ge 0$ λέγεται μήκος της λέξης $\alpha$ και συμβολίζεται με ${\left\vert{\alpha}\right\vert}$.

Η κενή λέξη συμβολίζεται πάντα με το $\epsilon$.

Με $\Sigma^*$ συμβολίζουμε το σύνολο όλων των λέξεων πάνω από το αλφάβητο $\Sigma$.

Παράδειγμα 7.3   Η $w = 0101$ είναι μια λέξη πάνω από το δυαδικό αλφάβητο $\Sigma_2$, με μήκος ${\left\vert{w}\right\vert} = 4$.

Ορισμός 7.3   (Γλώσσα) Μια γλώσσα $L$ πάνω από ένα αλφάβητο $\Sigma$ είναι ένα οποιοδήποτε σύνολο, πεπερασμένο ή άπειρο, λέξεων πάνω από το $\Sigma$. Ως συνήθως στα μαθηματικά με ${\left\vert{L}\right\vert}$ συμβολίζουμε τον πληθάριθμο της $L$.

Παράδειγμα 7.4   Το κενό σύνολο $\emptyset$ αποτελεί μια γλώσσα πάνω από οποιοδήποτε αλφάβητο $\Sigma$ που θα το ονομάζουμε κενή γλώσσα .

Παράδειγμα 7.5   Αν είναι $\Sigma$ ένα αλφάβητο τότε, καταχρηστικά, συμβολίζουμε πάλι με $\Sigma$ τη γλώσσα πάνω από το $\Sigma$ που αποτελείται από όλες τις δυνατές λέξεις με ακριβώς ένα γράμμα, το ίδιο δηλ. το αλφάβητο με μία έννοια.

Παράδειγμα 7.6   Το σύνολο $\Sigma^*$ όλων των λέξεων πάνω από ένα αλφάβητο $\Sigma$ είναι η πλήρης γλώσσα πάνω από το $\Sigma$. Για οποιοδήποτε $\Sigma$ αυτή είναι μια άπειρη γλώσσα που περιέχει ως υπογλώσσες (υποσύνολα) όλες τις γλώσσες πάνω από το $\Sigma$.

Παράδειγμα 7.7   Το σύνολο $E$ όλων των επωνύμων που εμφανίζονται τον τηλεφωνικό κατάλογο Κρήτης του 2015 αποτελεί μια γλώσσα πάνω από το αλφάβητο $\Sigma_{GR}$ των γραμμάτων και σημείων στίξης της ελληνικής γλώσσας (υποθέτουμε εδώ ότι δεν χρησιμοποιούνται πουθενά γράμματα του λατινικού αλφαβήτου στον κατάλογο). Η $E$ είναι μια πεπερασμένη αλλά μεγάλη γλώσσα.

Παράδειγμα 7.8   Το σύνολο

$$Q = {\left\{{w\in \Sigma_2^*: \exists k\in {\mathbb{N}}: {\left\vert{w}\right\vert} = k^2}\right\}}$$

είναι η γλώσσα όλων των δυαδικών λέξεων με μήκος που είναι τέλειο τετράγωνο. Προφανώς πρόκειται για μια άπειρη γλώσσα.

Παράδειγμα 7.9   Το σύνολο $L_k$ όλων των λέξεων του $\Sigma_2$ με μήκος ακριβώς $k$, όπου $k$ είναι ένας φυσικός αριθμός, είναι μια πεπερασμένη υπογλώσσα του $\Sigma_2^*$. Για διαφορετικά $k, k'$ οι δύο γλώσσες $L_k, L_{k'}$ είναι ξένες μεταξύ τους. Για κάθε λέξη $w \in \Sigma_2^*$ υπάρχει ακριβώς ένα $k$, το $k={\left\vert{w}\right\vert}$, για το οποίο $w \in L_k$. Οι γλώσσες $L_k$.$k \ge 0$, αποτελούν συνεπώς μια διαμέριση της πλήρους γλώσσας $\Sigma_2^*$.

Άσκηση 7.1   Το παρακάτω πρόγραμμα σε python τυπώνει όλες τις λέξεις με δεδομένο μήκος πάνω από ένα δοσμένο αλφάβητο.

def words_of_length(S, k):
    """ Return a list with all words over alphabet S of length k"""
    if k==0:
        return ['']
    result = []
    tails = words_of_length(S, k-1)
    for first in S:
        for t in tails:
            result.append(first+t)
    return result

S = ['a', 'b']
print words_of_length(S, 3)
SS = ['a', 'b', 'c']
print words_of_length(SS, 3)
print words_of_length(SS, 0)

Το αποτέλεσμα αυτού του προγράμματος είναι:

['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa',
 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab',
 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']
['']

Βεβαιωθείτε ότι καταλαβαίνετε πώς δουλεύει και πειραματιστείτε με αυτό ορίζοντας μερικά δικά σας αλφάβητα. Τροποποιήστε το ώστε να τυπώνει όλες τις λέξεις μήκους μέχρι $k$.

Άσκηση 7.2   Βρείτε το ${\left\vert{L_k}\right\vert}$. Αν $M_k$ είναι η υπογλώσσα του $\Sigma_2^*$ που αποτελείται από όλες τις λέξεις με μήκος το πολύ $k$, βρείτε το ${\left\vert{M_k}\right\vert}$.

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

Παράδειγμα 7.10   Ας είναι $\Sigma_{A}$ το αλφάβητο που αποτελείται από τα γράμματα του λατινικού αλφαβήτου, μικρά και κεφαλαία, τα δεκαδικά ψηφία, σημεία στίξης, παρενθέσεις, αγκύλες, τον λευκό (space) χαρακτήρα (να μη συγχέεται με την κενή λέξη $\epsilon$), το χαρακτήρα αλλαγής γραμμής (carriage return), και γενικά όλα τα σύμβολα που εμφανίζονται σε ένα σύγχρονο πληκτρολόγιο υπολογιστή. Αυτό το αλφάβητο ονομάζεται και αλφάβητο American Standard Code For Information Interchange - ASCII. (Για την ακρίβεια ο κώδικας ASCII είναι ένα standard αντιστοίχισης όλων των συμβόλων που αναφέραμε παραπάνω στους αριθμούς 0-127. Το standard αυτό ακολουθείται σήμερα σε όλους τους υπολογιστές.)

Η γλώσσα $L_C$ είναι εκείνο το σύνολο από λέξεις του $\Sigma_A^*$ που αποτελούν συντακτικά σωστά προγράμματα στη γλώσσα προγραμματισμού python. Αν δεν είστε γνώστες της γλώσσας αυτής αλλά κάποιας άλλης, μπορείτε να ορίσετε την αντίστοιχη γλώσσα. Ένα πρόγραμμα λοιπόν δεν είναι τίποτε άλλο από μια λέξη σε ένα κατάλληλο αλφάβητο. Αν αυτό ξενίζει να θυμίσουμε ότι και οι χαρακτήρες αλλαγής γραμμής βρίσκονται μέσα στο αλφάβητο, και άρα μια λέξη του $L_C$ μπορεί να περιέχει τα γράμματα ενός ολόκληρου αρχείου κειμένου.

Το $L_C$ είναι μια άπειρη γλώσσα αφού δεν υπάρχει άνω όριο στο μέγεθος ενός συντακτικά σωστού προγράμματος, και άρα υπάρχουν άπειρα τέτοια.

Ορισμός 7.4   (Συγκόλληση λέξεων, πρόθεμα και επίθεμα λέξης) Αν $\alpha = \alpha_1 \ldots \alpha_m$ και $\beta = \beta_1 \ldots \beta_n$ είναι δύο λέξεις πάνω από το αλφάβητο $\Sigma$ με μήκη $m$ και $n$, τότε ορίζουμε τη συγκόλληση (concatenation) $\alpha\beta$ να είναι η λέξη

$$\alpha\beta = \alpha_1\ldots\alpha_m\beta_1\ldots\beta_n,$$

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

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

Τέλος, μια λέξη $\pi$ λέγεται υπολέξη της $w$ αν υπάρχουν λέξεις $\alpha$, και $\beta$, ενδεχομένως κενές, τέτοιες ώστε $w = \alpha\pi\beta$.

Παράδειγμα 7.11   Αν $\Sigma={\left\{{a,b,c}\right\}}$ τότε η συγκόλληση των λέξεων $abc$ και $bb$ είναι η λέξη $abcbb$.

Παράδειγμα 7.12   Τα προθέματα της λέξης $abcd$ (δεν έχει σημασία σε ποιο αλφάβητο δουλεύουμε) είναι οι λέξεις $\epsilon, a, ab, abc, abcd$. Τα επιθέματα είναι οι λέξεις $abcd, bcd, cd, d, \epsilon$.

Παρατήρηση 7.1   Προφανώς ισχύει πάντα $\alpha\epsilon = \epsilon\alpha = \alpha$, για κάθε λέξη $\alpha$.

Είναι φανερό ότι μια λέξη με μήκος $n$ έχει ακριβώς $n+1$ προθέματα και άλλα τόσα επιθέματα.

Επίσης η συγκόλληση λέξεων είναι μια πράξη μη αντιμεταθετική, αφού, για παράδειγμα, αν $\alpha=01$ και $\beta=00$ τότε $\alpha\beta=0100 \neq 0001 = \beta\alpha$.

Παρατήρηση 7.2   Αν $\tau$ είναι γράμμα ενός αλφαβήτου $\Sigma$ τότε συμβολίζουμε επίσης με $\tau$ τη γλώσσα πάνω από το $\Sigma$ που περιέχει μόνο μια λέξη, τη λέξη $\tau$, που έχει μόνο ένα γράμμα.

Ορισμός 7.5   (Συγκόλληση γλωσσών) Αν $L_1, L_2$ είναι δύο γλώσσες πάνω από το $\Sigma$ ορίζουμε τη συγκόλληση $L_1L_2$ αυτών να είναι η γλώσσα

$$L_1L_2 = {\left\{{xy: x\in L_1, y\in L_2}\right\}}.$$

Αποτελείται δηλ. η $L_1L_2$ από όλες τις λέξεις που προκύπτουν ως συγκόλληση μιας λέξης από την $L_1$ με μια λέξη της $L_2$.

Ορίζουμε επίσης $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.$$

Παράδειγμα 7.13   Έστω $L = {\left\{{00, 11, \epsilon}\right\}}$. Τότε $L^* = L^+$ είναι η γλώσσα που απαρτίζεται από όλες εκείνες τις λέξεις από 0 ή 1 με άρτιο μήκος όπου το πρώτο γράμμα είναι ίδιο με το δεύτερο, το τρίτο με το τέταρτο κλπ. Η κενή λέξη ανήκει στην $L^*$.

Άσκηση 7.4   Περιγράψτε τη γλώσσα $1^*$ πάνω από το δυαδικό αλφάβητο $\Sigma_2$.

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

Άσκηση 7.6   Αν $L$ είναι μια οποιαδήποτε γλώσσα που δεν περιέχει την κενή λέξη $\epsilon$, ποια είναι ακριβώς η διαφορά των γλωσσών $L^*$ και $L^+$; Αλλάζει κάτι στην απάντηση αν $\epsilon \in L$;

Άσκηση 7.7   Bεβαιωθείτε ότι καταλαβαίνετε τι περιγράφει η γλώσσα

$${\left\{{+,-,\epsilon}\right\}}1{\left\{{0,1}\right\}}^*.$$

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