Αλφάβητα
Ορισμοί
Αλφάβητο
Αλφάβητο Σ είναι ένα μη κενό, πεπερασμένο σύνολο συμβόλων.
Για λόγους απλούστευσης θεωρούμε ότι ένα αλφάβητο μπορεί να έχει ως σύμβολα μόνο γράμματα, αριθμούς και χαρακτήρες όπως οι # και $.
Αγγλικό αλφάβητο: {a, b, ..., z, A, B, ..., Z}
Δυαδικό αλφάβητο: {0, 1}
Δεκαδικό αλφάβητο: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Μήκος αλφάβητου (cardinality)
Με |Σ|
συμβολίζουμε το μήκος του αλφάβητου (αριθμός στοιχείων). Για παράδειγμα, εάν Δ = Δυαδικό αλφάβητο
, τότε |Δ| = 2
.
Τα αλφάβητα έχουν πεπερασμένο μήκος.
Συμβολοσειρά (ή λέξη ή word ή string)
Συμβολοσειρά ενός αλφάβητου είναι μια πεπερασμένη και διατεταγμένη ακολουθία συμβόλων του.
Η κενή συμβολοσειρά (ε ή e) δεν περιέχει σύμβολα.
Ηhello
είναι συμβολοσειρά του{a, b, ..., z}
Η0111001
είναι συμβολοσειρά του{0, 1}
Η3210
είναι συμβολοσειρά του:{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Το σύνολο όλων των συμβολοσειρών (συμπεριλαμβανομένης της κενής) ενός αλφάβητου Σ
συμβολίζεται με Σ*
και λέγεται κλειστότητα του Kleene (Kleene closure) ή άστρο του Kleene.
Το σύνολο όλων των συμβολοσειρών (εκτός της κενής) ενός αλφάβητου Σ
συμβολίζεται με Σ+
(Positive
closure).
Με ανάλογο τρόπο ορίζουμε και τα σύνολα: Σ0, Σ1, Σ2 ...
Έστω: Σ = {a, b}, τότε:
Σ0 = σύνολο συμβολοσειρών με μήκος: 0. {ε} Σ1 = σύνολο συμβολοσειρών με μήκος: 1. {a, b} Σ2 = σύνολο συμβολοσειρών με μήκος: 2. {aa, ab, ba, bb}
Ισχύουν τα παρακάτω:
Σ* = Σ0 ⋃ Σ1 ⋃ Σ2 ⋃ Σ3 ...
Σ* = Σ+ ⋃ {ε}
Μήκος συμβολοσειράς
Μήκος |w|
μιας συμβολοσειράς w
είναι το μήκος της ως ακολουθία (το σύνολο των συμβόλων).
Μια συμβολοσειρά έστω w ∈ Σ*
μπορεί να παρουσιαστεί και ως συνάρτηση w : 1, ...|w| → Σ
, όπου η τιμή w(j)
είναι το σύμβολο που βρίσκεται στη θέση j
.
Για παράδειγμα: Αν w = test
, τότε w(1) = t
, w(2) = e
κλπ.
Το μήκος της συμβολοσειράς:over
είναι4
.
Για αλφάβητα με μήκος n
ο αριθμός συμβολοσειρών με |w| = n
που μπορεί να παραχθεί είναι 2n
Έστω Σ = {0, 1}. Οι παραγόμενες συμβολοσειρές με |w| = 2
είναι:
00, 01, 10, 11
Παράθεση ή συνένωση συμβολοσειρών (concatenation)
Η παράθεση δύο συμβολοσειρών x
και y
γράφεται ως xy
και αποτελείται από τα σύμβολα της x
ακολουθούμενα από αυτά της y
.
Τυπικά γράφουμε: w = xy
.
Ισχύουν:
- |w| = |x| + |y|
- w(j) = x(j) για j = 1, ..., |x|
- w(|x| + j) = y(j) για j = 1, ..., |y|
(meta)(data) = metadata
(011)(1001) = 0111001
(853)(315)= 853315
Ιδιότητες παράθεσης συμβολοσειρών
Ουδέτερο στοιχείο
∀ w ∈ Σ*, wε = εw = w
Προσεταιριστική ιδιότητα
∀ w, x, y ∈ Σ*, (wx)y = w(xy)
Δεν ισχύει η αντιμεταθετική ιδιότητα
ab ≠ ba
Υποσυμβολοσειρά (substring)
Η συμβολοσειρά s
είναι υποσυμβολοσειρά μιας συμβολοσειράς w
αν και μόνο αν υπάρχουν συμβολοσειρές x
και y
τέτοιες ώστε w = xsy
.
Ισχύουν:
- Κάθε συμβολοσειρά
w
είναι υποσυμβολοσειρά του εαυτού της, επειδήw = ewe
- Η
e
είναι υποσυμβολοσειρά κάθε άλλης συμβολοσειράς, επειδήw = wee
- Αν
w = xk
για κάποιοx
, τότε ηk
είναι κατάληξη τηςw
. Για παράδειγμα: Η συμβολοσειράδραμα
είναι κατάληξη της συμβολοσειράςμελοδραμα
. - Αν
w = py
για κάποιαy
, τότε ηp
είναι πρόθεμα τηςw
. Για παράδειγμα: Ημελο
είναι πρόθεμα τηςμελοδραμα
- Μια συμβολοσειρά μπορεί να περιλαμβάνει πολλές εμφανίσεις κάποιας υποσυμβολοσειράς (Πολλαπλή παράθεση). Παράδειγμα: Η
bitbitbit
έχει τρεις εμφανίσεις τηςbit
. - Για κάθε συμβολοσειρά w και κάθε φυσικό αριθμό i, η συμβολοσειρά wi ορίζεται ως:
w0 = e
καιwi+1 = wiw
για κάθεi ≥ 0
w1 = w και (bit)3 = bitbitbit
Αντίστροφη συμβολοσειρά
Η αντίστροφη συμβολοσειρά wR της w είναι η ακολουθία των συμβόλων της w από το τέλος προς την αρχή.
helloR = olleh
Ισχύουν:
- Αν w είναι συμβολοσειρά μήκους 0, τότε wR = w = ε
- Αν w είναι συμβολοσειρά μήκους n + 1 > 0 τότε ∃ a ∈ Σ : (w = ua ⋀ wR = auR)
- (wx)R = xRwR (Αποδεικνύεται με επαγωγή)