Hemtal 1 i Algoritmer och komplexitet 1995

Hemtalet ska lösas enskilt, dvs helt utan samarbete. Följ hederskodexen som finns i kursprogrammet!
Lämna dina lösningar skriftligt till Viggo senast måndag den 27 mars klockan 12. I detta hemtal behöver inte fullständiga motiveringar ges till dina konstruktioner, men beskriv gärna dina idéer bakom varje konstruktion med några meningar.
Fullständigt korrekt lösning ger 2 bonuspoäng på tentan. Uppgift 1b kan ge ytterligare en halv poäng.

Uppgifter

  1. a)
    Konstruera en ickedeterministisk ändlig automat (NDFA) som känner igen språket som genereras av det reguljära uttrycket
             *         *
    ((xx + y)  xz + yy)
    
    b)
    Konstruera en deterministisk ändlig automat (DFA) som känner igen samma språk. Försök minimera antalet tillstånd i automaten. En halv poäng extra ges till dom som konstruerar den minsta fungerande automaten.

  2. Låt S vara språket av alla positiva heltal som är jämnt delbara med elva. Anta att talen skrivs binärt.
    a)
    Konstruera en deterministisk ändlig automat som känner igen S då talen läses från vänster till höger, dvs med mest signifikanta biten först. Beskriv automaten med formler och inte med en graf.
    b)
    Konstruera en deterministisk ändlig automat som känner igen S då talen läses från höger till vänster, dvs med minst signifikanta biten först. Beskriv automaten med formler och inte med en graf.

^ Upp till aktuella kurssidan.


Senast ändrad 1995-03-21 <viggo@nada.kth.se>