pumpsatsen, automatateori
L = w | w har jämnt antal {a,b}. Avgör om det är reguljärt eller inte.
Min tankegång:
a^Na^Nb^Nb^n, sedan pumpar jag ur det från språket så att jag får a^(N-j)a^(N)b^(N)b^(N) där j >= 1. Vrf får jag inte göra på det sättet? Det går tydligen att konstruera en automat men vrf kan jag inte börja pumpa på det sätt som jag gör? Det är ju i andra fall ok att t.ex. pumpa ur a^(N)b^(N). Det är förmodligen något med pumpning som jag missuppfattar?
Red Eagle skrev:L = {w | w har ett jämnt antal a, samt ett jämnt antal b}. Avgör om det är reguljärt eller inte.
Min tankegång:
a^Na^Nb^Nb^n, sedan pumpar jag ur det från språket så att jag får a^(N+j)a^(N)b^(N)b^(N) där j >= 1. Vrf får jag inte göra på det sättet? Det går tydligen att konstruera en automat men vrf kan jag inte börja pumpa på det sätt som jag gör? Det är ju i andra fall ok att t.ex. pumpa ur a^(N)b^(N). Det är förmodligen något med pumpning som jag missuppfattar?
bump
Red Eagle skrev:L = w | w har jämnt antal {a,b}. Avgör om det är reguljärt eller inte.
Min tankegång:
a^Na^Nb^Nb^n, sedan pumpar jag ur det från språket så att jag får a^(N-j)a^(N)b^(N)b^(N) där j >= 1. Vrf får jag inte göra på det sättet? Det går tydligen att konstruera en automat men vrf kan jag inte börja pumpa på det sätt som jag gör? Det är ju i andra fall ok att t.ex. pumpa ur a^(N)b^(N). Det är förmodligen något med pumpning som jag missuppfattar?
Gissningsvis är det ingen här på Pluggakuten som har de specialkunskaper som behövs för att ens kunna tyda vad din fråga handlar om. Jag begriper det exempelvis inte.
Jag tittar på wikipedia-artikeln och förstår något, men inte allt. Jag förstår t.ex. inte så mycket av "L = w | w har jämnt antal {a,b}". Vad är w, vad betyder det lodräta strecket, och vad menas med jämnt antal {a,b}?
Reguljära språk som sådana är inget mysterium för mig, men pumping lemma hade jag inte stött på förut.
Traditionellt löser man väl sådana här uppgifter genom att anta att språket är reguljärt och försöka konstruera en motsägelse genom pumpsatsen? Kom ihåg att dylika uppgifter är väldigt nischad datavetenskap och du klarar dig nog bättre genom att ställa frågor här:
Laguna skrev:Jag tittar på wikipedia-artikeln och förstår något, men inte allt. Jag förstår t.ex. inte så mycket av "L = w | w har jämnt antal {a,b}". Vad är w, vad betyder det lodräta strecket, och vad menas med jämnt antal {a,b}?
Reguljära språk som sådana är inget mysterium för mig, men pumping lemma hade jag inte stött på förut.
w betyder en godtycklig sträng. Jag menar att w har jämnt antal a samt jämnt antal b, exempelvis: aabb, aaaabbbb, abababab, etc. Enligt pumpsatsen så ska reguljära språk kunna pumpas men detta kan jag pumpa ut med w = a^(N)a^(N)b^(N)b^(N).
@Ebola: Har postat i cs stackexchange också.
Du skriver "pumpa ur", men satsen verkar bara tala om pumpa, som betyder lägga till (upprepa) delsträngar. Tar du bort delsträngar?
Laguna skrev:Du skriver "pumpa ur", men satsen verkar bara tala om pumpa, som betyder lägga till (upprepa) delsträngar. Tar du bort delsträngar?
Ber om ursäkt, det var slarvigt formulerat av mig. Jag lägger till/pumpar upp men när jag lägger till så faller den ur språket.
Kom nu på vad jag gjort för fel, förstår inte vad jag tänkte. Y som pumpas kmr naturligtvis vara jämn eftersom att jag inte kan anta att y är av en viss längd.
