Konstruera en deterministisk tillståndsmaskin
Hej, jag har en fråga som har att göra med deterministiska tillståndsmaskiner. Jag förstår inte exakt hur man ska utifrån ett given språk bilda maskinen eller tabellen. Frågan lyder:
Konstruera en deterministisk tillståndsmaskin för språket som består av ett jämnt antal a:n följt av ett udda antal b:n . Ange antigen tillståndsmängden, övergångsfunktionen, de accepterande tillstånden och starttillstånden, eller en grafisk representation.
Jag skulle uppskatta all minska hjälp i det här svåra situationen, tacksam för svar!
kan ingen hjälpa?
Al97i skrev:kan ingen hjälpa?
Al97i, det står i Pluggakutens regler att man skall vänta åtminstone 24 timmar innan man bumpar sin tråd. Det står också i reglerna att du skall visa hur du har försökt och hur långt du har kommit. Om du gör detta, har du mycket större chans att få hjälp. Meningen med Pluggakuten äar att du skall få den hjälp du behäver för att kunna lösa din uppgift själv, inte att någon annan skall servera färdiga lösningar på dina problem. /moderator
@smargdalena jag ber om ursäkt om jag skrev för hastigt. Ja, jag har börjat med lösningen, jag tänkte att språket kanske kan vara aabbb (ett jämnt antal a:n, följt av ett udda antal b:n). Men hur tänker jag nu? hur ska jag utifrån det här språket bilda en övergångstabell?
Al97i skrev:@smargdalena jag ber om ursäkt om jag skrev för hastigt. Ja, jag har börjat med lösningen, jag tänkte att språket kanske kan vara aabbb (ett jämnt antal a:n, följt av ett udda antal b:n). Men hur tänker jag nu? hur ska jag utifrån det här språket bilda en övergångstabell?
aabbb är en sträng i språket, men man ska känna igen alla sådana strängar.
Laguna skrev:Al97i skrev:@smargdalena jag ber om ursäkt om jag skrev för hastigt. Ja, jag har börjat med lösningen, jag tänkte att språket kanske kan vara aabbb (ett jämnt antal a:n, följt av ett udda antal b:n). Men hur tänker jag nu? hur ska jag utifrån det här språket bilda en övergångstabell?
aabbb är en sträng i språket, men man ska känna igen alla sådana strängar.
men blir det inte som ett reguljärt uttryck om jag skriver det typ som (aa)*b(bb)*? kan det här anses vara ett språk eller är det ett reguljärt uttryck?
Al97i skrev:Laguna skrev:Al97i skrev:@smargdalena jag ber om ursäkt om jag skrev för hastigt. Ja, jag har börjat med lösningen, jag tänkte att språket kanske kan vara aabbb (ett jämnt antal a:n, följt av ett udda antal b:n). Men hur tänker jag nu? hur ska jag utifrån det här språket bilda en övergångstabell?
aabbb är en sträng i språket, men man ska känna igen alla sådana strängar.
men blir det inte som ett reguljärt uttryck om jag skriver det typ som (aa)*b(bb)*? kan det här anses vara ett språk eller är det ett reguljärt uttryck?
Det är ett reguljärt uttryck. I det här sammanhanget kan man väl säga att det definierar ett språk (helt rätt också). Men nu var det en tillståndsmaskin du skulle göra.
Jag tycker att språket verkar vara tvetydigt. "språket som består av ett jämnt antal a:n följt av ett udda antal b:n". Ska det alltså vara ett udda antal b:n efter varje delsträng med a:n eller ska det vara ett udda antal b:n totalt efter första delsträngen innehållandes ett jämnt antal a:n?
Ex. tillhör strängen aabaab språket? (efter första "aa" har vi totalt 2 stycken b:n, vilket inte är ett udda antal).
hur ska jag utifrån det här språket( (aa)*b(bb)*) avgöra hur många tillstånd maskinen ska innehålla?
@moffen men det blir ju alltid udda antal b:n eftersom vi har ett b utan för parantesen också
Al97i skrev:hur ska jag utifrån det här språket( (aa)*b(bb)*) avgöra hur många tillstånd maskinen ska innehålla?
@moffen men det blir ju alltid udda antal b:n eftersom vi har ett b utan för parantesen också
I ditt reguljära uttryck ja, men vad är egentligen språket i uppgiften? Det var det jag undrade över.
språket kan ju beskrivas av det reguljära uttrycket, då det reguljära uttrycket är språket som innehåller alla ord som består av ett jämnt antal a:n följt av ett udda antal b:n.
Al97i skrev:språket kan ju beskrivas av det reguljära uttrycket, då det reguljära uttrycket är språket som innehåller alla ord som består av ett jämnt antal a:n följt av ett udda antal b:n.
Nu skriver du ju bara av uppgiftstexten. Jag tycker att den är tvetydig på grund av vad jag skrev i mitt första inlägg. Men om vi antar att ditt reguljära uttryck beskriver språket, kan du ta fram en DFA för språket? Har du koll på hur en DFA fungerar? Visa hur du tänker/dina försök. Du kan göra en grafisk representation om du vill, det är tydligast tycker jag.
Jag har precis börjat läsa om DFA, därför jag lite osäker. Men jag kan lägga ut bild på min lösning, inte är säker om den är rätt
Tyvärr stämmer det inte riktigt, kan du se att din DFA exempelvis accepterar strängen "ab"? Det måste vara ett jämnt antal a:n, och det är det ju inte i strängen "ab". Testa att redigera den lite grann och lägg in bild igen :)
Det finns en startpil men det borde finnas en slutpil också.
Jag hoppas det här är rätt
Från 1 går man om man får aa eller b. Vad gör man om man får ab?
Edit: tja, då matchar man väl inte. Men om man har fått a så är man i ett mellantillstånd som du inte har visat. Tänk så att du bara behandlar en insymbol i taget.
Det går väl inte om man får ab, det är 2 a. Eller tänker jag fel?
Al97i skrev:Det går väl inte om man får ab, det är 2 a. Eller tänker jag fel?
Du hann nog svara innan jag lade till lite mer text.
Är min lösning fel?
Jag skulle vilja att man behandlar bara en insymbol i taget, så att man kan överföra alla tillstånd till ett datorprogram utan några dolda tillstånd, men jag vet inte vad din lärobok säger.
i exemplena i boken finns det också bara en insymbol eller två insymboler av två olika alfabet och inte av samma som i min. Men det känns som att det jag har ritat är rätt logiskt om man testar, jag är lite osäker hur det skulle se ut med bara en insymbol.
Det är inte korrekt. En DFA får högst läsa ett tecken per tillståndsövergång och det måste finnas en tillståndsövergång för varje tecken i alfabetet (dvs i ditt tillstånd 2 måste det finnas en pil för a också). Som jag tidigare nämnt tycker jag att språket är tvetydigt, men nu förutsätter jag att vi kör på språket "Jämnt antal a:n som sedan följs av udda antal b:n, där ingen delsträng börjar på b och slutar på a".
Du får antagligen försöka dela upp det i olika fall:
1. Vi läser ett a -> vi måste läsa ett till a (som ditt "fusk" med att läsa aa i din grafiska representation (då blir det en NFA)).
2. Vi läser ett b -> vi får inte läsa fler a (men får såklart läsa fler b:n men antalet b:n måste komma i par...)
3. Vi läser ett b efter ett a -> ...
4. Vi läser ett b efter udda antal a -> ...
5. Vi läser ett a efter ett b -> ...
.
.
.
Försök rita lite och se om du får till något. Ovanstående behöver såklart inte vara disjunkta, men idéer. Dela med dig av dina tankegångar och försök.
Tack för hjälpen!
