next up previous contents
Next: 5.11 Context free γραμματικές Up: 5 Ημερολόγιο Μαθήματος (Διδακτικές Previous: 5.9 Τρ, 5/11/02: Ελαχιστοποίηση   Contents

5.10 Δε, 18/11/02: Θέματα και αποτελέσματα Προόδου

Δείτε εδώ για τα αποτελέσματα της προόδου (άριστα το 30).

Τα θέματα που ρωτήθηκαν ήταν τα παρακάτω 6 προβλήματα (τα πρώτα τρία για τη μισή τάξη και τα υπόλοιπη γα την άλλη μισή).

  1. Κατασκευάστε DFA για τις γλώσσες (α) $00^*1^*1$, και (β) ${\left\{{w\in{\left\{{a,b}\right\}}^*:    6 \mid A(w)+2B(w)}\right\}}$, όπου $A(w)$, και $B(w)$ είναι το πλήθος των $a$ και των $b$ στη λέξη $w$ και $x\vert y$ σημαίνει ότι το $x$ διαιρεί το $y$.
  2. Δώστε μια κανονική έκφραση για τη γλώσσα που αναγνωρίζει το αυτόματο του Σχήματος 18.

    \begin{figure}
% latex2html id marker 2501
\refstepcounter{fcap}\centering \psfig{figure=midterm-enfa1.eps} \end{figure}

    Σχήμα 18. Το Σχήμα για την Άσκηση 2
  3. Δείξτε ότι η γλώσσα ${\left\{{(ab)^k(cd)^k:   k\in{\mathbf N}}\right\}}$ δεν είναι κανονική.
  4. Κατασκευάστε DFA για τις γλώσσες (α) τις λέξεις του ${\left\{{0,1}\right\}}^*$ που περιέχουν την υπολέξη 0000, και (β) τη γλώσσα που δίνεται από την κανονική έκφραση $10+(0+11)0^*1$.
  5. Δώστε μια κανονική έκφραση για τη γλώσσα που αναγνωρίζει το αυτόματο του Σχήματος 19.

    \begin{figure}
% latex2html id marker 2517
\refstepcounter{fcap}\centering \psfig{figure=midterm-enfa2.eps} \end{figure}

    Σχήμα 19. Το Σχήμα για την Άσκηση 5
  6. Δείξτε ότι η γλώσσα ${\left\{{xx:   x\in{\left\{{0,1}\right\}}^*}\right\}}$ δεν είναι κανονική.



Mihalis Kolountzakis 2003-09-04