Dfa Delbart By $ 5 Binära Alternativ

Jag arbetar med ett problem som ställs för en klass och tänkte på en fråga som rör det jag jobbade med. Finns det ett minimum antal stater som en ändlig automat måste ha för att kunna acceptera binära strängar som representerar antal delbara med ett heltal n I en tidigare problemuppsättning kunde jag konstruera en DFA som accepterade binära strängar delbara med 3 med 3 tillstånd . Är detta en slump, eller finns det något som är inneboende för det allmänna problemet att upptäcka strängar delbara av n som föreslår ett minimalt antal stater jag lovar att detta inte kommer att svara på en läxhetsfråga för mig. ) frågade jan 29 12 på 0:35 HuckBennett Jag håller med Kaveh att denna fråga borde vara stängd på cstheory, mestadels för att vara konsekvent. Men jag håller också med dig: det här är en rolig fråga och när du först ser DFAs är det definitivt en du borde fråga dig själv. Jag tycker att OP bör försöka ha kul att arbeta ut svaret för sig själv, och sedan rådfråga math. SE för mer info. ndash Artem Kaznatcheev 9830 Jan 29 12 på 6:10 Det här är en läxa (även om det är inspirerat av en läxa), det är en intressant fråga, jag tror inte att det är ett välkänt resultat och svaret på frågan framgår av en forskningsjournal. Jag ser inte varför den borde vara stängd. Övre gränsen var läxor, och det är verkligen lätt, men frågan handlade om nedre gränsen. ndash Peter Shor Jan 29 12 på 13:43 Jag studerar regelbundna uttryck och fann ett intressant praktikproblem på nätet som innebär att man skriver ett regelbundet uttryck för att känna igen alla binära nummer delbara med 3 (och endast sådana siffror). För att vara ärlig frågade problemet att konstruera en DFA för ett sådant scenario, men jag tänkte att det borde vara likvärdigt möjligt med regelbundna uttryck. Jag vet att det finns en liten regel på plats för att ta reda på om ett binärt tal är delbart med 3: ta antalet på jämn plats i siffran och subtrahera av antalet på ojämna platser i siffran - om detta är lika med noll , numret är delbart med 3 (exempel: 110 - 1 i den jämn 2 spalten och en 1 i odd 1 spåret). Men jag har problem med att anpassa detta till ett vanligt uttryck. Det närmaste jag kommer är att inse att numret kan vara 0, så det skulle vara det första tillståndet. Jag såg också att alla binära nummer delbara med 3 börjar med 1, så det skulle vara den andra staten, men jag fastnar därifrån. Kan någon hjälpa till med att fråga frågade mar 11 13 på 1:50 Efter vad Oli Charlesworth säger kan du bygga DFA för delbarhet av bas b nummer av en viss divisor d. där staterna i DFA representerar resten av divisionen. För ditt fall (bas 2 - binärt tal, divisor d 3 10): Observera att DFA ovan accepterar en tom sträng som ett nummer delbart med 3. Detta kan enkelt fixas genom att lägga till ytterligare ett mellanliggande tillstånd: Konvertering till teoretiskt regelbundet uttryck kan göras med den normala processen. Omvandling till praktisk regex i smaker som stöder rekursiv regex kan enkelt göras när du har DFA. Detta visas för (bas b 10, d 7 10) i denna fråga från CodeGolf. SE. Att bryta ner det kan du se hur det är konstruerat. Den atomgruppering (eller icke-backtracking-gruppen, eller en grupp som uppträder i sig) används för att säkerställa att endast det tomma strängalternativet matchas. Detta är ett trick att emulera (DEFINE) i Perl. Sedan motsvarar grupperna A till G resten av 0 till 6 när antalet är dividerat med 7. svarat 11 mar 13 kl 6:44 Jag har en annan väg till det här problemet och jag tycker att det är lättare att förstå. När vi delar ett tal med 3 kan vi ha tre remainders: 0,1,2. Vi kan beskriva ett tal som är delbart med 3 med uttrycket 3t (t är ett naturligt tal). När vi lägger till 0 efter ett binärt tal vars återstod är 0, kommer det faktiska decimaltalet att fördubblas. Eftersom varje siffra flyttar till en högre position. 3t 2 6t, detta är också delbart med 3. När vi lägger till ett 1 efter ett binärt tal vars viloläge är 0, kommer det faktiska decimaltalet att fördubblas plus 1. Eftersom varje siffra flyttas till en högre position följt av en 1 3t 2 1. resten är 1. När vi lägger till ett 1 efter ett binärt tal vars vila är 1. Det faktiska decimaltalet kommer att fördubblas plus en och resten är 0 (3t 1) 2 1 6t 3 detta är delbart med 3. När vi lägger till en 0 efter ett binärt tal vars återstod är 1. Det faktiska decimaltalet kommer att fördubblas. Och resten kommer att vara 2 (3t 1) 2 6t 2. När vi lägger till en 0 efter ett binärt nummer vars resten är 2. Resten blir 1. (3t 2) 2 3t 4 3 (2t 1) 1 När vi lägger till 1 efter ett binärt tal vars återstod är 2. Då återstår fortfarande 2. (3t 2) 2 1 t 5 3 (2t 1) 2. Oavsett hur många 1 du lägger till i ett binärt tal vars återstod är 2, kommer återstoden att vara 2 för alltid. (3 (t 1) 2) 2 1 3 (t 2) 5 3 (t 3) 2 svarat Nov 6 15 kl 20:45 Binära tal delas med 3 faller i 3 kategorier: Nummer med två i följd 1s eller två 1s separerade av ett jämnt antal 0s. Effektivt parar varje par ut sig själv. (ex 11, 110, 1100, 100, 10010, 1111) (decimal: 3, 6, 12, 9, 18, 15) Nummer med tre 1s separerade med ett udda antal 0s. Dessa tripletar avbryter också sig själva. (ex 10101, 101010, 1010001, 1000101) (decimal: 21, 42, 81, 69) Vissa kombinationer av de två första reglerna (inklusive inuti varandra) (ex 1010111, 1110101, 1011100110001) (decimal: 87, 117 , 5937) Så ett regelbundet uttryck som tar hänsyn till dessa tre regler är helt enkelt: betyder att den tidigare numbergruppen är valfri anger ett val av alternativ på båda sidor inom parentesBelow, jag har skrivit ett svar för n är lika med 5, men du kan ansöka samma tillvägagångssätt för att teckna DFA för något värde av n och något positionsnummer system, t. ex. binärt, ternärt. Först luta termen Komplett DFA, en DFA definierad på fullständig domän i: Q Q heter Fullständig DFA. Med andra ord kan vi säga i övergångsdiagram över komplett DFA, det finns ingen saknad kant (t ex från varje stat i Q finns en utgående kant närvarande för varje språksymbol i). Obs! Ibland definierar vi partiell DFA som Q Q (Läs: Hur: Q Q läses i definitionen av en DFA). Design DFA accepterar binära nummer delbart med nummer n: steg-1. När du delar ett tal med n kan påminnelsen antingen vara 0, 1. (n - 2) eller (n - 1). Om återstoden är 0 betyder det att delningen är delbar av n annars inte. Så i min DFA kommer det att finnas ett tillstånd q r som skulle motsvara ett restvärde r. där 0 lt lt (n - 1). och totalt antal tillstånd i DFA är n. Efter att ha bearbetat en talsträng över är sluttillståndet q r innebär att n r (påminnelseoperatör). I vilken som helst automat är en stats syfte ett minneelement. Ett tillstånd i en atomat lagrar viss information som fans byta som kan berätta om fläkten är avstängd eller i läge. För n 5, fem stater i DFA som motsvarar fem påminnelsesinformation enligt följande: Status q 0 uppnådd om påminnelsen är 0. State q 0 är det slutliga tillståndet (accepterande tillstånd). Det är också ett initialt tillstånd. Stat q 1 når om påminnelsen är 1, ett icke-slutligt tillstånd. Ange q 2 om påminnelsen är 2, ett icke-slutligt tillstånd. Ange q 3 om påminnelsen är 3, ett icke-slutligt tillstånd. Ange q 4 om påminnelsen är 4, ett icke-slutligt tillstånd. Med hjälp av ovanstående information kan vi börja rita övergångsdiagram TD av fem stater enligt följande: Så, 5 anger 5 återstående värden. Efter bearbetning av en sträng om sluttillståndet blir q 0 betyder det att decimalekvivalent av ingångsträngen är delbar med 5. I ovanstående figur q är 0 det slutliga tillståndet som två koncentriska cirklar. Dessutom har jag definierat en övergångsregel: (q 0, 0) q 0 som en egen slinga för symbol 0 vid tillstånd q 0. detta beror på att decimalvärdet av en sträng består av endast 0 är 0 och 0 är delbar med n. Steg 2 . TD ovan är ofullständig och kan bara bearbeta strängar på 0 s. Lägg nu till några fler kanter så att det kan bearbeta efterföljande talsträngar. Kontrollera tabellen nedan, visar nya övergångsregler som kan läggas till nästa steg: För att bearbeta binär sträng 1 borde det finnas en övergångsregel: (q 0. 1) q 1 Två: - Binär representation är 10. Slutstaten ska vara q 2 . och att behandla 10. behöver vi bara lägga till en övergångsregel: (q 1. 0) q 2-väg. (q 0) 1 (q 1) 0 (q 2) Tre: - i binär är det 11. slutstaten är q 3. och vi måste lägga till en övergångsregel: (q 1. 1) q 3-väg. (q 0) 1 (q 1) 1 (q 3) Fyra: - i binär 100. sluttillstånd är q 4. TD bearbetar redan prefixsträng 10 och vi behöver bara lägga till en ny övergångsregel: (q 2. 0) q 4 sökväg. (q 0) 1 (q 1) O (q 2) O (q 4) Steg-3. Fem 101 Ovanstående övergångsdiagram i figur 2 är fortfarande ofullständigt och det finns många saknade kanter, för exempel är ingen övergång definierad för: (q 2. 1) -. Och regeln bör vara närvarande för att bearbeta strängar som 101. Eftersom 101 5 är delbar med 5 och att acceptera 101 kommer jag att lägga till: (q 2. 1) q 0 ovanstående figur 2. Vägen: (q 0) 1 (q 1) 0 (q 2) 1 (q 0) med denna nya regel, övergångsdiagram blir enligt följande: Nedan i varje steg väljer jag nästa efterföljande binära nummer för att lägga till en saknad kant tills jag får TD som en komplett DFA. Vi kan bearbeta 11 i nuvarande TD i figur 3 som: (q 0) 11 (q 3) 0 (). Eftersom 6 5 1 betyder det att lägga till en regel: (q 3. 0) q 1. Steg 6 Lägg till tolv, tretton, fjorton Totalt antal kanter i övergångsdiagram figur-12 är 15 Q 5 3 (en komplett DFA). Och denna DFA kan acceptera att alla strängar som överstiger dessa decimala ekvivalenter är delbara med 5. Om du märker vid varje steg finns det tre poster i tabellen, eftersom i varje steg lägger jag till all möjlig utgående kant från ett tillstånd för att göra en komplett DFA (och Jag lägger till en kant så att qr-status blir för resten är r) För att lägga till ytterligare, kom ihåg att fackföreningen i två vanliga språk också är en vanlig. Om du behöver designa en DFA som accepterar binära strängar, är decimalekvivalenten antingen delbar med 3 eller 5, rita sedan två separata DFA-enheter för delbar med 3 och 5 och fäst båda DFA-modulerna för att konstruera mål DFA (för 1 lt n lt 10 din har till union 10 DFAs). Om du uppmanas att rita DFA som accepterar binära strängar så att decimalekvivalenten är delbar med 5 och 3 båda så letar du efter DFA av delbar med 15 (men ungefär 6 och 8). Obs! DFA-ritningar med denna teknik minimeras endast DFA när det inte finns någon gemensam faktor mellan nummer n och bas t. ex. Det finns ingen mellan 5 och 2 i första exemplet, eller mellan 5 och 3 i andra exemplet, varför båda DFA-konstruktionerna ovan är minimerade DFA. Om du är intresserad av att läsa mer om möjliga mini-tillstånd för nummer n och bas b läs papper: Divisibility and State Complexity. nedanför har jag lagt till ett Python-skript, jag skrev det för skojs skull när jag lärde mig Python biblioteket pygraphviz. Jag lägger till det jag hoppas det kan vara till hjälp för någon i someway. Design DFA för bas b-nummersträngar delbara med nummer n: Så vi kan tillämpa ovanligt trick för att rita DFA för att känna igen talsträngar i vilken bas b som helst som är delbart ett givet nummer n. I det DFA kommer totalt antal stater att vara n (för n remainders) och antal kanter ska vara lika med b n mdash som är komplett DFA: b antal symboler på språket i DFA och n antal tillstånd. Använda ovanstående trick, nedan har jag skrivit ett Python-skript för att rita DFA för inmatningsbas och nummer. I skript befolker funktionen divideradN DFA: s övergångsregler i basnumret. I varje steg-num omvandlar jag num till numrera strängtal med hjälp av funktionsbasN (). För att undvika att bearbeta varje talsträng har jag använt en tillfällig datastruktur. I varje steg utvärderas slutdatum för nummersträngsnoder och lagras i lookuptable för att användas i nästa steg. För övergångsgrafen för DFA har jag skrivit en funktionsritningsgrafik med Pygraphviz-biblioteket (mycket lätt att använda). För att använda det här skriptet måste du installera graphviz. För att lägga till färgglada kanter i övergångsdiagram, genererar jag slumpmässigt färgkoder för varje symbol getcolordict-funktion. På samma sätt anger du bas 4 och nummer 7 för att generera - dfa accepterande talsträng i bas 4 som är delbara med 7 Btw, försök ändra filnamn till. png eller. jpeg.