Venus AUEB Forum

Το παρόν thread προορίζεται για το μάθημα "Αυτόματα & Πολυπλοκότητα". Εδώ μπορείτε να συζητάτε για ό,τι σχετίζεται με το συγκεκριμένο μάθημα. Υπενθυμίζουμε ότι με βάση τους κανονισμούς λειτουργίας του forum απαγορεύονται τα greeklish, double posts και τα κεφαλαία. Για προηγούμενες συζητήσεις μπορείτε να ανατρέξετε εδώ.

Καλή αρχή! :D

Θέματα Μαΐου 2019

1. Τέσσερα Σωστό/Λάθος με σύντομη αιτιολόγηση. + Δύο προτάσεις να εξηγήσουμε γιατί είναι λανθασμένες.
2. Δώσε κανονική έκφραση για γλώσσες. Σχεδίασε NFA/DFA. Σου έδινε δύο λέξεις και έπρεπε να δείξουμε αν ανήκουν ή όχι στις γλώσσες που δόθηκαν.
3. Δύο ασκήσεις με λήμμα άντλησης + 2 ασκήσεις με μηχανές Turing, όπου ζητούσε άτυπη περιγραφή των βημάτων του αλγορίθμου. Η πρώτη ήταν με μια ταινία u#u, όπου u ανηκει στο {a,b} και πως η M.T. αποφασίζει. Η 2η ήταν το ίδιο αλλα με u.u ( χωρίς την δίεση ).
4. Αναγωγές αποφασισιμότητας.