Kodning i Diskret matte 2

För att kunna komma in i databasen och uppdatera sin information behöver agenterna välja lösenord. Ett lösenord ska se ut som följer:

• Exakt 3 x.
• Minst 2 z.
• Hur många y som helst.

För att kontrollera om en sträng ur alfabetet { x, y, z } är ett tillåtet lösenord behövs en accepterande automat.

4. Analysera med hjälp av kombinatorik hur många tillstånd automaten behöver ha?

5. Rita upp en accepterande automat som känner igen språket av tillåtna lösenord. Förklara
också vad vart och ett av tillstånden innebär?

6. Skriv ett reguljärt uttryck för språket. Förklara noga hur du resonerar ?

Mina lösningar :

uppgift 4

För att analysera hur många tillstånd automaten behöver ha, kan vi titta på de olika villkoren för lösenordet:
Exakt 3 x: Det finns endast en möjlig kombination av 3 x i strängen.
Minst 2 z: Vi kan ha 2, 3, 4, osv. z:n i strängen.
Hur många y som helst: Antalet y:n kan vara vilket positivt heltal som helst, inklusive 0.
För att bestämma antalet tillstånd som behövs, tittar vi på de maximala möjligheterna för varje del: 3 x:n, det maximala antalet z:n och hur många y:n som helst. Därför behöver automaten minst (3 + 1) * (2 + 1) * (1 + ∞) = 12 tillstånd

uppgift 5

uppgift 6

^x {3} z {2,} y*+λ

ELLER  :    ^xxxzz+ y*λ

x{3} matchar exakt tre x i följd.
z{2,} matchar minst två z i följd.
y* matchar hur många y som helst, inklusive inga y alls.