Open eClass - Univ. of the Aegean | Θεωρία Υπολογισμού [open] | Άσκηση αυτοαξιολόγησης - Ενότητα 4η (Αυτόματα στοίβας, λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα)

Το Λ. Άντλησης (για Ανεξάρτητες Συμφραζομένων ) το εφαρμόζουμε γ.ν.δ.ο. μια:

a) άπειρη γλώσσα δεν είναι ανεξάρτητη συμφραζομένων

b) άπειρη γλώσσα είναι ανεξάρτητη συμφραζομένων

Το πλήθος των καταστάσεων ενός πεπερασμένου αυτομάτου στοίβας εξαρτάτε από:

a) το μήκος της λέξης εισόδου

b) από το είδος των συμβόλων της λέξης εισόδου

c) είναι σταθερό, ανεξάρτητο της λέξης εισόδου

Ο χρόνος τερματισμού ενός πεπερασμένου αυτομάτου στοίβας είναι ανάλογος με:

a) το μήκος της λέξης εισόδου

b) το πλήθος των καταστάσεων του

c) το πλήθος των καταστάσεων και των μεταβάσεων του και το μέγεθος της στοίβας

d) για ορισμένες λέξεις, είναι μη φραγμένος δλδ άπειρος

Ένα πεπερασμένο αυτόματο στοίβας μπορεί να εξομοιώσει:

a) ένα πεπερασμένο αυτόματο

b) μια μηχανή Turing

Course : Θεωρία Υπολογισμού [open]