Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 2:
Για να πραγματοποιήσουν μια εξονυχιστική μελέτη των υπολογισμών, οι επιστήμονες υπολογιστών αντιμετωπίζουν τον υπολογιστή ως μια αφηρημένη μαθηματική έννοια, που λέγεται μοντέλο υπολογισμού. Υπάρχουν διάφορες διατυπώσεις που χρησιμοποιούνται, αλλά η πιο συχνή είναι η [[μηχανή Τούρινγκ]]. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν ένα [[προσωπικός υπολογιστής|προσωπικό υπολογιστή]] με άπειρη μνήμη, αν και μπορεί να την προσπελάσει μόνο σε μικρά διακριτά κομμάτια. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή διατύπωση και μπορούν να την αναλύσουν, να την χρησιμοποιήσουν σε αποδείξεις, και λόγω του ότι κατά πολλούς αντιπροσωπεύει το πιο ισχυρό εφικτό μοντέλο υπολογισμού. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ, θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή που έχει αρκετή μνήμη.
== Τυπική Γραμματική ==
{{Κύριο|Τυπική γραμματική}}
Στην [[επιστήμη υπολογιστών]] μια '''τυπική γραμματική''' (formal grammar) είναι μια [[αφηρημένη δομή]] που περιγράφει μια [[τυπική γλώσσα]] επακριβώς, δηλαδή είναι ένα σύνολο κανόνων που απεικονίζουν με μαθηματικά το [[σύνολο|σύνολο]], (συνήθως [[σύνολο|απειροσύνολο]]), των πεπερασμένου μήκους [[Στοιχειοσειρά|στοιχειοσειρών]] που σχηματίζονται με διακριτά στοιχεία (π.χ. γράμματα), τα οποία ανήκουν σε ένα σύνολο, συνήθως πεπερασμένο, που το λέμε ''αλφάβητο''.
Οι τυπικές γραμματικές ονομάστηκαν έτσι κατ’ αναλογία των [[Γραμματική|γραμματικών]] των γλωσσών που μιλούν οι άνθρωποι, αλλά τα αλφάβητα τους δεν περιέχουν κατ’ ανάγκη γράμματα. Οι τυπικές γραμματικές διαχωρίζονται σε δυο κύριες κατηγορίες : ''γενετικές'' (generative) και ''αναλυτικές'' (analytic).
Μια [[γενετική γραμματική]], (το πιο γνωστό είδος, που θα μπορούσε να ονομάζεται γεννητική ή παραγωγική γραμματική), είναι ένα σύνολο κανόνων με το οποίο όλες οι συμβολοσειρές που μπορούν να υπάρξουν σε μια γλώσσα μπορούν να παραχθούν με διαδοχικά [[Στοιχειοσειρά#Συναλύσωση|επιθέματα]] ξεκινώντας από ένα προκαθορισμένο ''αρχικό σύμβολο δημιουργίας στοιχειοσειράς''. Μια γενετική γραμματική ουσιαστικά είναι η τυπική μορφή του [[Αλγόριθμος|αλγορίθμου]] παραγωγής στοιχειοσειρών που ανήκουν στην γλώσσα.
:Συνοπτικά για την γενετική γραμματική :
:* λειτουργεί ως δημιουργός στοιχειοσειρών της γλώσσας, δηλαδή ''γράφει την γλώσσα'',
:* η πορεία είναι από την γραμματική προς τις λέξεις της γλώσσας,
:* εφαρμόζεται παραγωγική (top-down) προσέγγιση, από το γενικό προς το μερικό.
Μια [[Αναλυτική γραμματική]], αντιθέτως, είναι ένα σύνολο κανόνων που υποθέτουν ότι μιά αυθαίρετη στοιχειοσειρά δίνεται προς επεξεργασία και με διαδοχικά βήματα ανάλυσης προκύπτει ως αποτέλεσμα η τιμή μιας [[Μεταβλητή (προγραμματισμός)#Λογικές μεταβλητές|λογικής μεταβλητής]]:
* ΑΛΗΘΗΣ, αν η στοιχειοσειρά ανήκει στην γλώσσα που περιγράφει η αναλυτική γραμματική
* ΨΕΥΔΗΣ, αν η στοιχειοσειρά δεν ανήκει στην γλώσσα που περιγράφει η αναλυτική γραμματική.
:Συνοπτικά για την αναλυτική γραμματική :
:* σαρώνει την στοιχειοσειρά, τεχνολογεί τα μέρη που την αποτελούν και τα αναγνωρίζει, (είναι [[Συντακτική ανάλυση (προγραμματισμός)|συντακτικός αναλυτής]] (parser)), δηλαδή ''διαβάζει την γλώσσα'',
:* η πορεία είναι από τις λέξεις της γλώσσας προς την γραμματική της,
:* εφαρμόζεται επαγωγική (bottom-up) προσέγγιση, από το μερικό προς το γενικό.
== Βασικές Αρχές ==
| |||