Γλώσσες

Ορισμοί

Γλώσσα (language)

Τυπική Γλώσσα (ή γλώσσα) είναι ένα σύνολο από συμβολοσειρές (ή λέξεις) ενός αλφαβήτου Σ.

Ισχύει: Γλώσσα είναι κάθε σύνολο λέξεων = L ⊆ Σ* (όπου Σ* κάθε πιθανός συνδυασμός συμβόλων του Σ).

Για παράδειγμα: L = {μηδέν, ένα, δύο, τρία, ... εννέα} είναι μια γλώσσα στο αλφάβητο Σ = {α, β, γ, ..., ω}.

Το σύνολο των επιτρεπτών ονομάτων στη γλώσσα προγραμματισμού C++.

Η γλώσσα των επιτρεπτών αλγεβρικών εκφράσεων, που σχηματίζονται με το όνομα (μεταβλητής) x, τους δυαδικούς τελεστές + και * και τη χρήση παρενθέσεων. Για παράδειγμα: (x + x * (x + x)).

Kleene star γλώσσας

Η Kleene star μιας γλώσσας L συμβολίζεται με L* και είναι το σύνολο των συμβολοσειρών που προκύπτουν από παράθεση 0 ή περισσοτέρων συμβολοσειρών της L.

L* = {w ∈ Σ* : η w = w1...wk για k ≥ 0 και w1, ..., wk ∈ L}

Πεπερασμένη γλώσσα

Μία πεπερασμένη γλώσσα μπορεί να ορισθεί παραθέτοντας όλες τις συμβολοσειρές που την απαρτίζουν.

Η {one, two, three, ..., ten} είναι γλώσσα με αλφάβητο το {a, b, ..., z}

Άπειρη γλώσσα

Είναι μια γλώσσα με άπειρες συμβολοσειρές.

{0, 01, 011, 0111, ... }
{w ∈ Σ* : η w έχει ίσο πλήθος 1 και 0}
{w ∈ Σ*: w = wR}
Γενικά: L = {w ∈ Σ* : η w έχει την ιδιότητα p}

Ιεραρχία Chomsky

Υπάρχουν κατηγορίες γλωσσών τις οποίες έχει ορίσει και ταξινομήσει ο Τσόμσκι (Chomsky).

Σύμφωνα με την ταξινόμηση Chomsky έχουμε τις τέσσερις παρακάτω γλώσσες.

  • Τύπου 0 - TM (Turing Machines. Μηχανές Turing)
  • Τύπου 1 - LBA (Linear Bounded Automata (LBA). Γραμμικά Περιορισμένα Αυτόματα)
  • Τύπου 2 - PDA (PushDown Automata (Αυτόματα Στοίβας), Γραμματικές χωρίς συμφραζόμενα)
  • Τύπου 3 - DFA (και NFA)

Υπάρχουν κοινοί κανόνες για όλες τις γλώσσες όπως:

  • L = ∅ (κενό σύνολο)
  • L = {ε} όπου ε η κενή συμβολοσειρά
  • L = {α} όπου α ∈ Σ (γλώσσα με ένα σύμβολο)
  • L = {w} όπου w ∈ Σ* (γλώσσα με μία λέξη)

Επίσης:

Για δύο γλώσσες έστω Α και Β σε ένα κοινό αλφάβητο έστω Σ ισχύουν:

  • Συνένωση (concatenation): L = A.B (ή L = AB, κάθε λέξη στην L είναι της μορφής αβ όπου α ∈ Α και β ∈ Β.
  • Ένωση (union): L = A⋃B (κάθε λέξη στην L είναι λέξη στην Α ή Β)
  • Τομή (intersection): L = A⋂B (κάθε λέξη στην L είναι κοινή στην Α και Β)
  • Συμπλήρωμα (complement) L = ¬A (κάθε λέξη που δεν υπάρχει στην Α είναι λέξη της L)
  • Κλειστότητα του Kleene (Kleene star): L = A* (είναι για την L όλες οι λέξεις που είναι συνδυασμός από μηδέν ή περισσότερες λέξεις της Α)

Επίσης ισχύουν τα παρακάτω:

  • L0 = {ε}
  • Ln+1 = LLn
  • L* = L0L1L2...
  • L+ = L1L2...
  • L* = L0L+

Κανονική Γλώσσα (regular language)

Είναι μια γλώσσα τύπου 3.

Είναι μια τυπική γλώσσα που μπορεί να εκφραστεί από:

  • ένα πεπερασμένο αυτόματο (deterministic automaton) ή
  • μία κανονική έκφραση (regular expression) ή
  • μια κανονική γραμματική (regular grammar)

Μια κανονική γλώσσα ορίζεται από μια γραμματική. Η γραμματική περιγράφει τους κανόνες σύμφωνα με τους οποίους παράγονται οι συμβολοσειρές (ή λέξεις) της γλώσσας.

Η γλώσσα που παράγεται από τη γραμματική έστω G συμβολίζεται ως L(G).

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

Η αλγεβρική παράσταση που εκφράζει μια κανονική γλώσσα λέγεται κανονική έκφραση (regular expression).

Η γραμματική που παράγει μια κανονική γλώσσα λέγεται κανονική γραμματική (regular grammar).

Το Λήμμα Άντλησης (λήμμα pumping)

Με το λήμμα pumping αποδεικνείουμε ότι μια γλώσσα δεν είναι κανονική αλλά όχι το αντίθετο.

Παράδειγμα με παράθεση γλωσσών

Η παράθεση των γλωσσών L1 και L2 είναι η γλώσσα:

L = L1L2 = {w ∈ Σ* : η w = xy για κάποιο x ∈ L1 και y ∈ L2}

Αν Σ = {0, 1},

L1 = {w ∈ Σ* : w έχει άρτιο αριθμό 0} και

L2 = {w ∈ Σ* : w αρχίζει με 0 και ακολουθούν μόνο 1}

τότε

L1L2 = {w ∈ Σ* : w έχει περιττό αριθμό 0 και τελειώνει με διαδοχικά 1}

Γλώσσες Χωρίς Συμφραζόμενα (ΓΧΣ)

Είναι οι γλώσσες που παράγονται από γραμματικές χωρίς συμφραζόμενα ή ισοδύναμα αυτόματα στοίβας. Είναι τύπου 2 σύμφωνα με τον Chomsky.

Γλώσσες Με Συμφραζόμενα

Η γλώσσα που παράγεται από μια Γραμματική Με Συμφραζόμενα (ΓΜΣ) ονομάζεται γλώσσα με συμφραζόμενα. Είναι τύπου 1 σύμφωνα με τον Chomsky.

Αναδρομικές Γλώσσες

Αναδρομική γλώσσα λέγεται η γλώσσα όταν όλες οι λέξεις που ανήκουν στη γλώσσα γίνονται αποδεκτές (accepted) από μια μηχανή Turing ενώ όλες οι λέξεις που δεν ανήκουν στη γλώσσα απορρίπτονται (rejected).

Αναδρομικά Απαριθμήσιμες Γλώσσες

Είναι η γλώσσα που όταν όλες οι λέξεις που ανήκουν στη γλώσσα γίνονται αποδεκτές (accepted) από μια μηχανή Turing ενώ όλες οι λέξεις που δεν ανήκουν στη γλώσσα δεν είναι υποχρεωτικό ότι θα απορρίπτονται (rejected). Υπάρχει για παράδειγμα η περίπτωση να μπαίνουν σε ατέρμονα βρόχο.

Αναδρομικά Απαριθμήσιμες Γλώσσες (ορισμός 2)

Η γλώσσα L παράγεται από μια Μη Περιορισμένη Γραμματική (ΜΠΓ) τότε και μόνο τότε όταν η L είναι αναδρομικά απαριθμήσιμη. Οι αναδρομικά απαριθμήσιμες γλώσσες γίνονται αποδεκτές από τις Μηχανές Τούρινγκ. Είναι τύπου 0 σύμφωνα με τον Chomsky.

Αποφασίσιμες Γλώσσες

Είναι όλες οι αναδρομικές γλώσσες. Όλες οι αναδρομικές είναι αποφασίσιμες και αντίστροφα.

Μερικώς Αποφασίσιμες γλώσσες

Είναι όλες οι Αναδρομικά Απαριθμήσιμες Γλώσσες.

Μη Αποφασίσιμες Γλώσσες

Είναι όλες οι γλώσσες που δεν είναι Αποφασίσιμες Γλώσσες. Δεν υπάρχει μηχανή Turing για αυτές τις γλώσσες.

Υπάρχε περίπτωση μια μη αποφασίσιμη να είναι μερικώς αποφασίσιμη. Σε αυτή την περίπτωση υπάρχει αντίστοιχη μηχανή Turing.