Αλφάβητα

Ορισμοί

Αλφάβητο

Αλφάβητο Σ είναι ένα μη κενό, πεπερασμένο σύνολο συμβόλων.

Για λόγους απλούστευσης θεωρούμε ότι ένα αλφάβητο μπορεί να έχει ως σύμβολα μόνο γράμματα, αριθμούς και χαρακτήρες όπως οι # και $.

Αγγλικό αλφάβητο: {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 (Αποδεικνύεται με επαγωγή)