Jeg jobber med et problem satt for en klasse, og tenkte på et spørsmål knyttet til det jeg jobbet med. Er det et minimum antall stater som en endelig automat må ha for å kunne akseptere binære strenger som representerer tall deles med et heltall n I et tidligere problemsett kunne jeg konstruere en DFA som aksepterte binære strenger delelig med 3 med 3 stater . Er dette en tilfeldighet, eller er det noe som er iboende med det generelle problemet med å oppdage strengene delelig med n som antyder et minimum antall stater jeg lover dette vil ikke svare på et leksersspørsmål for meg. ) spurte Jan 29 12 på 0:35 HuckBennett Jeg er enig med Kaveh at dette spørsmålet skal lukkes på cstory, for det meste å være konsistent. Men jeg er også enig med deg: dette er et morsomt spørsmål, og når du først ser DFAer, er det definitivt en du bør spørre deg selv. Jeg tror OP bør prøve å ha det gøy å trene svaret for seg selv, og deretter konsultere math. SE for mer info. ndash Artem Kaznatcheev 9830 Jan 29 12 på 6:10 Dette er et hjemmearbeid (selv om det er inspirert av et lekserespørsmål), det er et interessant spørsmål, jeg tror ikke det er et kjent resultat, og svaret på spørsmålet dukket opp i en forskningsjournal. Jeg ser ikke hvorfor det burde være stengt. Den øvre grensen var lekser, og det er faktisk enkelt, men spørsmålet handlet om den nedre grensen. ndash Peter Shor Jan 29 12 kl 13:43 Jeg studerer regelmessige uttrykk og fant et interessant praksisproblem på nettet som innebærer å skrive et vanlig uttrykk for å gjenkjenne alle binære tall delbart med 3 (og bare slike tall). For å være ærlig, spurte problemet om å konstruere en DFA for et slikt scenario, men jeg skjønte at det burde være likeverdig å bruke vanlige uttrykk. Jeg vet at det er en liten regel på plass for å finne ut om et binært tall er delbart med 3: ta tallet på like steder i sifferet og trekk av antall i ulige steder i sifferet - dersom dette er lik null , tallet er delt med 3 (eksempel: 110 - 1 i den samme 2 spalten og en 1 i oddetallet 1). Imidlertid har jeg problemer med å tilpasse dette til et vanlig uttrykk. Det nærmeste jeg kommer er å innse at tallet kan være 0, så det ville være den første staten. Jeg så også at alle binære tall deles med 3 begynner med 1, så det ville være den andre staten, men jeg stakk derfra. Kan noen hjelpe til med å spørre Mar 11 13 på 1:50 Etter hva Oli Charlesworth sier, kan du bygge DFA for delbarhet av base b nummer av en bestemt divisor d. hvor stater i DFA representerer resten av divisjonen. For ditt tilfelle (base 2 - binært tall, divisor d 3 10): Merk at DFA ovenfor aksepterer tom streng som et tall som er delt med 3. Dette kan enkelt løses ved å legge til en mellomliggende tilstand foran: Konvertering til teoretisk regulært uttrykk kan gjøres med normal prosess. Konvertering til praktisk regex i smaker som støtter rekursiv regex kan gjøres enkelt, når du har DFA. Dette vises for tilfelle av (base b 10, d 7 10) i dette spørsmålet fra CodeGolf. SE. Bryter den ned, du kan se hvordan den er konstruert. Den atomiske gruppering (eller ikke-backtracking-gruppen, eller en gruppe som oppfører seg i besittelse), brukes for å sikre at bare det tomme strengalternativet er tilpasset. Dette er et triks å etterligne (DEFINE) i Perl. Da svarer gruppene A til G til resten av 0 til 6 når tallet er delt med 7. besvart 11. mars kl. 6:44. Jeg har en annen måte på dette problemet, og jeg tror dette er lettere å forstå. Når vi deler et tall med 3, kan vi ha tre remainders: 0,1,2. Vi kan beskrive et tall som er delbart med 3 ved å bruke uttrykk 3t (t er et naturlig tall). Når vi legger til 0 etter et binært tall hvis gjenværende er 0, vil det faktiske desimalnummeret bli doblet. Fordi hvert siffer går til en høyere posisjon. 3t 2 6t, dette er også delbart med 3. Når vi legger til en 1 etter et binært nummer, hvis gjenværende er 0, vil det faktiske desimalnummeret bli doblet pluss 1. Fordi hvert siffer går til en høyere posisjon etterfulgt av en 1 3t 2 1. resten er 1. Når vi legger til en 1 etter et binært tall hvis gjenværende er 1. Det faktiske desimalnummeret blir doblet pluss en, og resten er 0 (3t 1) 2 1 6t 3 dette er delbart med 3. Når vi legger til 0 etter et binært tall, hvis gjenværende er 1. Det faktiske desimalnummeret vil bli doblet. Og resten vil være 2 (3t 1) 2 6t 2. Når vi legger til 0 etter et binært nummer hvis resten er 2. Resten blir 1. (3t 2) 2 3t 4 3 (2t 1) 1 Når vi legger til en 1 etter et binært tall hvis gjenværende er 2. Så vil resten være 2. (3t 2) 2 1 t 5 3 (2t 1) 2. Uansett hvor mange 1 du legger til et binært tall hvis gjenværende er 2, vil resten være 2 for alltid. (3 (t 1) 2) 2 1 3 (t 2) 5 3 (t 3) 2 svarte Nov 6 15 kl 20:45 Binær tall delbart med 3 faller inn i 3 kategorier: Tall med to påfølgende 1 eller 2 1s skilt av et jevnt antall 0s. Effektivt avbryter hvert par seg selv. (eks. 11, 110, 1100, 100, 10010, 1111) (desimal: 3, 6, 12, 9, 18, 15) Tall med tre 1s hver avskilt med et oddetall 0s. Disse tripplene avbryter også seg selv. (ex 10101, 101010, 1010001, 1000101) (desimal: 21, 42, 81, 69) Enkelte kombinasjoner av de to første reglene (inkludert i hverandre) (ex 1010111, 1110101, 1011100110001) (desimal: 87, 117 , 5937) Så et regulært uttrykk som tar hensyn til disse tre reglene er ganske enkelt: betyr at tidligere numbergruppe er valgfritt, indikerer et valg av alternativer på begge sider i parentesBelow, jeg har skrevet et svar for n er lik 5, men du kan søke samme tilnærming til å tegne DFAer for enhver verdi av n og ethvert posisjonsnummersystem, for eksempel binært, ternært. Først len deg termen Komplett DFA, en DFA definert på komplett domene i: Q Q heter Complete DFA. Med andre ord kan vi si i overgangsdiagram over komplett DFA, det er ingen manglende kanten (for eksempel fra hver tilstand i Q er det en utgående kanten til stede for hvert språk-symbol i). Merk: Noen ganger definerer vi delvis DFA som Q Q (Les: Hvordan: Q Q leses i definisjonen av en DFA). Design DFA-godkjenning Binære tall deles med nummer n: Trinn-1. Når du deler et tall med n, kan påminnelsen enten være 0, 1. (n - 2) eller (n - 1). Hvis resten er 0 som betyr at det er delbart med n ellers ikke. Så, i min DFA vil det være en tilstand q r som ville tilsvare en restverdi r. hvor 0 lt er lt (n - 1). og totalt antall stater i DFA er n. Etter å ha behandlet en tallstreng over, er sluttstaten qr innebærer at nr (påminnelsesoperatør). I noen automater er formålet med en stat som minneelement. En stat i en atomat lagrer litt informasjon som fans bytte som kan fortelle om viften er av eller på tilstanden. For n 5, fem stater i DFA som svarer til fem påminnelsesinformasjon som følger: Stats q 0 nådd hvis påminnelsen er 0. Stats q 0 er den endelige tilstanden (aksepttilstand). Det er også en innledende tilstand. Tilstand q 1 når hvis påminnelsen er 1, en ikke-endelig tilstand. Oppgi q 2 hvis påminnelsen er 2, en ikke-endelig tilstand. Oppgi q 3 hvis påminnelsen er 3, en ikke-endelig tilstand. Oppgi q 4 hvis påminnelsen er 4, en ikke-endelig tilstand. Ved å bruke over informasjon, kan vi begynne å tegne overgangsdiagram TD av fem stater som følger: Så, 5 står for 5 gjenværende verdier. Etter å ha behandlet en streng hvis sluttstaten blir q 0 betyr det at desimalkvivalent av inngangsstrengen er delt med 5. I figur over er q 0 merket sluttstilling som to konsentriske sirkler. I tillegg har jeg definert en overgangsregel: (q 0, 0) q 0 som en selvløkke for symbol 0 ved tilstand q 0. Dette skyldes at desimaltall av en streng består av bare 0 er 0 og 0 er delelig med n. Steg 2 . TD ovenfor er ufullstendig og kan bare behandle strenger på 0 s. Legg nå noen flere kanter slik at den kan behandle påfølgende tallstrenger. Kontroller tabell nedenfor, viser nye overgangsregler som kan legges til neste trinn: For å behandle binær streng 1 bør det være en overgangsregel: (q 0. 1) q 1 To: - binær representasjon er 10. sluttstat skal være q 2 . og for å behandle 10. trenger vi bare å legge til en mer overgangsregel: (q 1. 0) q 2 bane. (q 0) 1 (q 1) 0 (q 2) Tre: - i binær er det 11. sluttstaten er q 3. og vi må legge til en overgangsregel: (q 1. 1) q 3 sti. (q 0) 1 (q 1) 1 (q 3) Fire: - i binær 100. slutt-tilstand er q 4. TD prosesserer allerede prefiks streng 10, og vi trenger bare å legge til en ny overgangsregel: (q 2. 0) q 4 bane. (q 0) 1 (q 1) 0 (q 2) 0 (q 4) Trinn 3. Fem 101 Over overgangsdiagrammet i figur 2 er fortsatt ufullstendig og det mangler mange mangler, for eksempel er det ikke definert overgang for: (q 2. 1) -. Og regelen bør være til stede for å behandle strenger som 101. Fordi 101 5 er delelig med 5 og aksepterer 101, vil jeg legge til: (q 2. 1) q 0 i figur 2 ovenfor. Sti: (q 0) 1 (q 1) 0 (q 2) 1 (q 0) med denne nye regelen, overgangsdiagram blir som følger: Under hvert trinn velger jeg neste påfølgende binærnummer for å legge til en manglende kanten til jeg får TD som en komplett DFA. Vi kan behandle 11 i dagens TD i figur 3 som: (q 0) 11 (q 3) 0 (). Fordi 6 5 1 betyr dette å legge til en regel: (q 3. 0) q 1. Trinn 6 Legg til tolv, tretten, fjorten Totalt antall kanter i overgangsdiagram figur-12 er 15 Q 5 3 (en komplett DFA). Og denne DFA kan akseptere alle strenger som består over disse desimalekvivalenter, er delbare med 5. Hvis du merker ved hvert trinn, er det tre oppføringer i tabellen fordi jeg ved hvert trinn legger til all mulig utgående kant fra en tilstand for å lage en komplett DFA (og Jeg legger til en kant slik at qr-tilstanden blir for resten er r) Hvis du vil legge til ytterligere, husk også at to vanlige språk er en vanlig. Hvis du trenger å designe en DFA som aksepterer binære strenger, er desimalekvivalenten enten delbar med 3 eller 5, og trekk deretter to separate DFAer for delbar med 3 og 5, og bind deretter begge DFA-ene til å konstruere mål DFA (for 1 lt n lt 10 din har til forening 10 DFAer). Hvis du blir bedt om å tegne DFA som aksepterer binære strenger slik at desimalkvivalenten er delt med 5 og 3, så ser du etter DFA for delelig med 15 (men omtrent 6 og 8). Merk: DFAer tegnet med denne teknikken vil bli minimert DFA bare når det ikke finnes en felles faktor mellom nummer n og base, f. eks. Det er ikke mellom 5 og 2 i første eksempel, eller mellom 5 og 3 i andre eksempel, derfor er begge DFA-konstruksjonene ovenfor minimert DFAer. Hvis du er interessert i å lese videre om mulige mini-statene for nummer n og base b, lest papir: Divisibility and State Complexity. under jeg har lagt til et python-skript, skrev jeg det for moro mens jeg lærte pythonbiblioteket pygraphviz. Jeg legger til det jeg håper det kan være nyttig for noen i someway. Design DFA for base b-nummerstrenger delbart med nummer n: Så vi kan bruke overtrick for å tegne DFA for å gjenkjenne talestrenger i hvilken som helst base b de er delbare et gitt nummer n. I det DFA vil totalt antall stater være n (for n remainders) og antall kanter skal være lik b n mdash som er komplett DFA: b antall symboler i språket i DFA og n antall stater. Ved å bruke overtrick, har jeg skrevet et Python Script for å tegne DFA for inngangsbase og nummer. I skript, fyller funksjonen dividedbyN DFAs overgangsregler i basenummerstrinn. I hvert trinn-nummer konverterer jeg num til tallstrengnummer med funksjon baseN (). For å unngå å behandle hver talestreng, har jeg brukt en midlertidig datastruktur oppslagstavle. I hvert trinn evalueres og lagres sluttstatus for nummerstrengsnoder i oppslagstabell for bruk i neste trinn. For overgangsgrafikk av DFA, har jeg skrevet en funksjonstrekkegrafikk ved hjelp av Pygraphviz-biblioteket (veldig enkelt å bruke). For å bruke dette skriptet må du installere graphviz. Hvis du vil legge til fargerike kanter i overgangsdiagram, genererer jeg tilfeldig fargekoder for hver symbolskollektorfunksjon. Tilsvarende, skriv inn base 4 og nummer 7 for å generere - dfa aksepterer talestreng i base 4 som er delbare med 7 Btw, prøv å endre filnavn til. png eller. jpeg.
No comments:
Post a Comment