2 svar
73 visningar
Elias Sk är nöjd med hjälpen
Elias Sk 59
Postad: 10 dec 2023 13:22 Redigerad: 10 dec 2023 14:02

Hur många DFA är möjliga?

Hej, jag löser uppgifter om automater, där en av uppgifterna ser ut såhär:
Jag vet inte riktigt hur jag ska tolka uppgiften.

Det jag tänker mig är hur många olika sluttillstånd resp. hur pilarna pekar som är efterfrågat. Dvs först:

EDIT: det finns 8 olika sätt som tillstånden kan vara "arrangerade" i, inte 5. Jag missade:
-> 1 ->- 2 ->- 3
-> 1 ->- 2 ->- 3
-> 1 ->- 2 ->- 3
Slutnod: X, inte slutnod: X

Alltså att det inns 8 olika sätt som själva tillstånden kan ha, och sedan ska man också lägga till sätten man kan dra pilarna till de olika tillstånden, där ett sätt är detta:

Osv för alla sätt man kan "dra pilarna" för alla olika maskiner.

Är detta en rätt tolkning av uppgiften eller är jag ute och cyklar?

Och om detta är rätt tolkning, kan någon hjälpa till med att lösa den. Jag skulle kunna rita upp ALLA olika möjligheter, men det finns antagligen en bättre metod som jag ej kan komma på. Som sagt om jag tolkat uppgiften rätt.

Alex111 333
Postad: 11 dec 2023 01:16 Redigerad: 11 dec 2023 01:18

Ser som att det skulle kunna vara åt det rätta spåret  med "pil- och cirkeldiagram" ifall automaten är en FSM (Finite-State machine)

Elias Sk 59
Postad: 19 dec 2023 18:32

Uppdatering. Jag vet svaret, men för folk som ev hittat denna tråd för att se en lösning så skriver jag in den här:

1 - Vi börjar med att räkna på hur många olika sätt "a" och "b" kan "överföras" till ett annat tillstånd. Vardera symbol kan "överföras" till 3 olika tillstånd; 1, 2 resp. 3.
Här måste man dock komma ihåg att varje tillstånd kan vara ett slut- eller icke sluttillstånd, vilket innebär att dessa kombinationer behöver dubblas för att täcka båda tillstånden. Uttrycket för antal kombinationer blir därför: 2×32

2 - Detta är alltså alla möjliga kombinationer för symbolerna "a" och "b" att "överföras" från ett tillstånd. Det finns dock dock lika många möjliga kombinationer att "överföra" vardera symbol för alla tillstånd; 1, 2 resp. 3, så därför kommer uttrycket från "steg" 1 att behöva multipliceras 3 gånger enligt samma princip som i "steg" 1. Det nya uttrycket blir därför (2×32)3

3 - Nu är alla möjliga kombinationer räknade en gång. Men det finns ytterligare 3 kombinationer, nämligen vilket tillstånd som är starttillståndet. Det finns 3 möjliga starttillstånd och därmed behöver de redan räknade kombinationerna multipliceras 3 gånger, 1 gång för varje potentiellt starttillstånd. Det slutgiltiga uttrycket kommer därför att bli 3×(2×32)3

SVAR: Antal möjliga DFA är 17 496 st

Svara Avbryt
Close