Automaten en Berekenbaarheid: verschil tussen versies
Naar navigatie springen
Naar zoeken springen
examen 15/01/07 namiddag |
k categorie 3bi |
||
| Regel 13: | Regel 13: | ||
* Beschrijf het correspondentieprobleem van Post. Argumenteer waarom het onbeslisbaar is. Is het herkenbaar? argumenteer | * Beschrijf het correspondentieprobleem van Post. Argumenteer waarom het onbeslisbaar is. Is het herkenbaar? argumenteer | ||
* Stel L een taal met <math>|\Sigma| \geq 2</math>. Alle strings in de rest van de opgave zijn elementen van <math>\Sigma^*</math>. Definiëer de afstand d(s,t) tussen de strings <math>s = s_{0}s_{1} \ldots s_n</math> en <math>t = t_{0}t_{1} \ldots t_{n}</math> als volgt: <math>d(s,t) = \sharp \{ i | s_{i} \neq t_{i} \}</math> als <math>|s| = |t|</math>. Definiëer nu de taal L<sub>1</sub>fout = <math> \{ x | \exists a \in L : |a| = |x| \wedge d(a,x) \leq 1 \} </math>. Bewijs nu het volgende: als L regulier is, dan is L<sub>1</sub>fout ook regulier. (Hint: vertrek van een DFA van L, en construeer een NFA met toestanden <math>Q \times \{0,1\}</math>) | * Stel L een taal met <math>|\Sigma| \geq 2</math>. Alle strings in de rest van de opgave zijn elementen van <math>\Sigma^*</math>. Definiëer de afstand d(s,t) tussen de strings <math>s = s_{0}s_{1} \ldots s_n</math> en <math>t = t_{0}t_{1} \ldots t_{n}</math> als volgt: <math>d(s,t) = \sharp \{ i | s_{i} \neq t_{i} \}</math> als <math>|s| = |t|</math>. Definiëer nu de taal L<sub>1</sub>fout = <math> \{ x | \exists a \in L : |a| = |x| \wedge d(a,x) \leq 1 \} </math>. Bewijs nu het volgende: als L regulier is, dan is L<sub>1</sub>fout ook regulier. (Hint: vertrek van een DFA van L, en construeer een NFA met toestanden <math>Q \times \{0,1\}</math>) | ||
[[Categorie:3bi]] | |||
Versie van 16 jan 2007 14:06
Dit vak wordt gegeven door prof. Demoen.
Informatie over het examen
Het examen is volledig mondeling, met schriftelijke voorbereiding. De theorie is gesloten boek, de oefening is open boek (alhoewel je het boek eigenlijk niet nodig hebt)
- Vraag 1: een 'makkelijke' theorievraag, uit het lijstje van de mogelijke examenvragen
- Vraag 2: een 'moeilijke' theorievraag, ook ergens uit de cursus
- Vraag 3 (open boek): oefening waarin je iets moet bewijzen
Examens
2007-01-15 (namiddag)
- Beschrijf in detail de transformatie van een deterministische eindige toestandsautomaat naar een equivalente deterministische eindige toestandsautomaat met een minimaal aantal toestanden. Beschrijf de notie van "equivalentie van automaten" in deze context en argumenteer waarom er wel of geen kleinere equivalente deterministische eindige toestandsautomaat bestaat. Kan een kleinere equivalent niet-deterministische eindige toestandsautomaat bestaan?
- Beschrijf het correspondentieprobleem van Post. Argumenteer waarom het onbeslisbaar is. Is het herkenbaar? argumenteer
- Stel L een taal met . Alle strings in de rest van de opgave zijn elementen van . Definiëer de afstand d(s,t) tussen de strings en als volgt: als . Definiëer nu de taal L1fout = . Bewijs nu het volgende: als L regulier is, dan is L1fout ook regulier. (Hint: vertrek van een DFA van L, en construeer een NFA met toestanden )