a) το μήκος της λέξης εισόδου
b) το πλήθος των καταστάσεων της
c) το πλήθος των καταστάσεων και των μεταβάσεων της
d) δεν υπάρχει γενικός κανόνας και ενδεχομένως, για ορισμένες λέξεις, να είναι μη φραγμένος δλδ άπειρος
a) η μηχανή Turing τερματίζει σε ΝΑΙ μόνο για τις λέξεις της γλώσσας
b) για κάθε λέξη η μηχανή Turing τερματίζει σε ΝΑΙ αν ανήκουν στην L, αλλιώς τερματίζει σε ΟΧΙ
a) αναγνωρίσιμη
b) κανονική
c) ανεξάρτητη συμφραζομένων
