Olen työskennellyt luokkaan liittyvälle ongelmalle ja ajattelin kysymystä, joka liittyi siihen, mitä työskentelin. Onko olemassa minimaalinen määrä tiloja, jotka äärellisen automaatin on täytettävä, jotta voidaan hyväksyä binaarisia merkkijonoja, jotka edustavat numeroita, jotka ovat kokonaislukuina n. Aikaisemmissa ongelmajoukkoissa pystyn rakentamaan DFA: n, joka hyväksyi binääriluvut, jotka jakautuvat kolmella ja 3 tilalla . Onko tämä sattumaa, vai onko jotain, joka liittyy yleiseen ongelmaan, joka ilmaisee n: n kanssa jakautuvia jonoja, mikä viittaa vähimmäismäärään valtioita, joita lupaan, ei vastaa kotitehtäviin kysymykseen minulle. ) kysyi Jan 29 12 klo 0:35 HuckBennett Olen samaa mieltä Kavehin kanssa, että tämä kysymys olisi suljettava cstheorysta, lähinnä johdonmukaiseksi. Olen kuitenkin myös samaa mieltä kanssasi: tämä on hauska kysymys ja kun näet ensin DFA: t, se on ehdottomasti yksi, jonka pitäisi kysyä itseltäsi. Mielestäni OP: n pitäisi yrittää olla hauskaa selvittää vastaus itselleen ja sitten kysyä lisätietoja math. SE: stä. ndash Artem Kaznatcheev 9830 Jan 29 12 at 6:10 Tämä ei ole kotitehtäviä (vaikka se on innoittamana kotitehtävän kysymyksellä), se on mielenkiintoinen kysymys, en usko, että se on tunnettu tulos ja vastaus kysymykseen ilmestyi tutkimuslehti. En näe miksi se olisi suljettu. Yläraja oli kotitehtävä, ja se on todellakin helppoa, mutta kysymys oli alemmasta sidosta. ndash Peter Shor Jan 29 12 at 13: 43 Olen itseopiskelu säännöllisiä ilmaisuja ja löytänyt mielenkiintoisen käytännön ongelma verkossa, johon kuuluu kirjoittaa säännöllisesti ilmaista tunnistaa kaikki binaariluvut jakautuvat 3 (ja vain tällaisia numeroita). Jotta olisin rehellinen, ongelmana oli DFA: n rakentaminen tällaiselle skenaariolle, mutta ajattelin, että sen pitäisi olla yhtä mahdollista käyttämällä säännöllisiä lausekkeita. Tiedän, että siellä on pieni sääntö, jossa selvitetään, onko binaariluku jaollinen kolmella: ottakaa numeroiden lukumäärä parillisissa paikoissa ja vähennä numerot parillisissa paikoissa numerolla - jos tämä on nolla , numero on jaollinen 3: llä (esimerkki: 110 - 1 parillisessa 2 korttipaikassa ja 1 parittomassa 1 korttipaikassa). Minulla on kuitenkin vaikeuksia mukauttaa tätä säännöllisesti. Lähin Ive tulee ymmärtää, että numero voi olla 0, joten se olisi ensimmäinen tila. Olen myös nähnyt, että kaikki binääriluvut, jotka ovat jaettavissa 3: llä, alkavat 1: llä, joten se olisi toinen tila, mutta Im jumissa sieltä. Voisiko joku auttaa? Kysyi 11. maaliskuuta klo 13.50 Oli Charlesworthin mukaan, voit rakentaa DFA: n, jonka perusteella jakaja b-numeron voi jakaa tietyn jakajaan d. jossa DFA: n osavaltiot edustavat loput jakautumisesta. Sinun tapauksessasi (base 2 - binäärinumero, jakajan d 3 10): Huomaa, että yllä oleva DFA hyväksyy tyhjän merkkijonon numeroina, jotka ovat jaettavissa 3: llä. Tämä voidaan helposti korjata lisäämällä edellinen välitila: Konversio teoreettiselle säännölliselle lausekkeelle voidaan tehdä normaalilla prosessilla. Muunnos käytännölliseen regex-muotoon, joka tukee rekursiivista regexia, voidaan tehdä helposti, kun olet saanut DFA: n. Tämä näkyy tapauksessa (base b 10, d 7 10) tässä kysymyksessä CodeGolf. SE: sta. Kun hajotat sen, näet kuinka se on rakennettu. Atomiyhdistelmää (tai ei-backtracking-ryhmää tai ryhmä, joka käyttäytyy hallitsevasti) käytetään varmistamaan, että ainoastaan tyhjä merkkijonovaihtoehto on sovitettu. Tämä on temppu emuloida (DEFINE) Perlissä. Sitten ryhmät A-G vastaavat jäljelle jäänyttä 0-6, kun numero on jaettu 7. Vastaus: Marraskuu 11 13, 6:44 Minulla on toinen tapa tähän ongelmaan ja mielestäni tätä on helpompi ymmärtää. Kun jakamalla numero on kolme, meillä voi olla kolme jäljellä olevaa osaa: 0,1,2. Voimme kuvata numeron, joka on jaollinen 3: llä käyttäen lauseketta 3t (t on luonnollinen luku). Kun lisätään 0 binaariluvun jälkeen, jonka loppuosa on 0, todellinen desimaaliluku kaksinkertaistuu. Koska jokainen numero siirtyy korkeammalle. 3t 2 6t, tämä on myös jaollinen 3: llä. Kun lisäämme 1 binäärisen numeron jälkeen, jonka loppuosa on 0, todellinen desimaaliluku kaksinkertaistuu plus 1. Koska jokainen numero siirtyy korkeammalle sijalle ja seuraa 1 3t 2 1. loppuosa on 1. Kun lisätään 1 binäärisen numeron jälkeen, jonka loput on 1. Todellinen desimaaliluku kaksinkertaistuu plus yksi ja loput on 0 (3t 1) 2 1 6t 3 tämä on jaollinen 3. Kun lisäämme 0 binäärisen numeron jälkeen, jonka loput on 1. Todellinen desimaaliluku kaksinkertaistuu. Ja loput ovat 2 (3t 1) 2 6t 2. Kun lisäämme 0 binäärisen numeron jälkeen loppuosa on 2. Loput ovat 1. (3t 2) 2 3t 4 3 (2t 1) 1 Kun lisätään 1 binäärisen numeron jälkeen, jonka loput on 2. Sitten jäljelle jää edelleen 2. (3t 2) 2 1 t 5 3 (2t 1) 2. Ei ole väliä kuinka monta 1 lisäät binääriseen numeroon, jonka jäljellä on 2, loput 2 ikuisesti. (3) 2 3 (t 2) 5 3 (t 3) 2 vastasi marraskuun 6 15 kello 20:45 3: n jakautuvat binääriluvut jakautuvat kolmeen luokkaan: Numerot kahdella peräkkäisellä 1: llä tai kahdella 1: parillinen lukumäärä 0s. Tehokkaasti jokainen pari kumoaa itsensä. (esim. 11, 110, 1100, 1001, 10010, 1111) (desimaali: 3, 6, 12, 9, 18, 15) Numerot, joissa on kolme 1s, erotettuina parittomalla lukumääräl - lä 0s. Nämä tripletit myös purkavat itseään. (esim. 10101, 101010, 1010001, 1000101) (desimaali: 21, 42, 81, 69) Joitakin yhdistelmää kahdesta ensimmäisestä säännöstä (sisältäen toistensa sisäpuolella) (esim. 1010111, 1110101, 1011100110001) , 5937) Joten säännöllinen lauseke, jossa otetaan huomioon nämä kolme sääntöä, on yksinkertaisesti: tarkoittaa sitä, että edellinen ryhmä on vapaaehtoinen osoittaa vaihtoehtoja molemmilta puolilta suluissaBelow, olen kirjoittanut vastauksen n: stä 5, mutta voit hakea sama lähestymistapa DFA: iden tekemiseen mille tahansa n: narvolle ja minkään paikkasijoitusjärjestelmän numerolle, esim. binaarinen, ternäärinen. Ensin laitetaan termi Täydellinen DFA, DFA, määritelty täydellisellä verkkotunnuksella: QQ kutsutaan täydelliseksi DFA: ksi. Toisin sanoen voimme sanoa täydellisestä DFA: n siirtymäkaaviosta puuttuvien reunojen puuttuessa (esimerkiksi jokaisesta Q: n tilasta on yksi lähtevä reuna jokaiselle kielisymbolille). Huomaa: Joskus määritellään osittainen DFA Q Q: ksi (Luku: Kuinka Q Q lukee DFA: n määritelmässä). Suunnittele DFA, joka hyväksyy binääriluvut, jotka ovat jaettavissa numerolla n: Step-1. Kun jakaat numeron n: llä, muistutus voi olla joko 0, 1. (n - 2) tai (n - 1). Jos loppu on 0, se tarkoittaa, että se on jaollinen n: llä. Joten DFA: ssa tulee olemaan tila q r, joka vastaa jäljellä olevaa arvoa r. jossa 0 litraa (n - 1). ja tilojen kokonaismäärä DFA: ssa on n. Sen jälkeen, kun on käsitelty useita merkkijonoja, lopputila q r tarkoittaa, että n r (muistutusoperaattori). Jokaisessa automateissa valtion tarkoitus on kuin muistielementti. Atatomatan tila tallentaa tietoja kuten fanikytkimet, jotka voivat selvittää, onko tuuletin päällä tai on päällä. N 5: lle viisi DFA: n tilaa, jotka vastaavat viittä muistutustietoa, seuraavasti: Tila q 0 saavutetaan, jos muistutus on 0. Tila q 0 on lopullinen tila (hyväksyvä tila). Se on myös alkutila. Tila q 1 saavuttaa, jos muistutus on 1, ei lopullinen tila. Tila q 2, jos muistutus on 2, ei lopullista tilaa. Tila q 3, jos muistutus on 3, ei lopullinen tila. Tila q 4, jos muistutus on 4, ei lopullista tilaa. Yllä mainittujen tietojen avulla voimme aloittaa viiden tilan siirtymäkaavio TD: n seuraavasti: Joten, 5 tilaa 5 jäljellä olevaa arvoa varten. Kun merkkijono on käsitelty, jos lopputila muuttuu q 0: ksi, se tarkoittaa, että desimaalijakauma on syötettävä merkkijonon jakauma viidellä. Yllä olevassa kuvassa q 0 on merkitty lopulliseksi tilaksi kahdeksi samankeskiseksi ympyräksi. Lisäksi olen määritellyt siirtymäsäännön: (q 0 .0) q0 omana silmukkana symbolina 0 tilassa q0. tämä johtuu siitä, että minkä tahansa merkkijonon desimaaliekvivalentti on vain 0 on 0 ja 0 on jaollinen n: llä. Vaihe 2. TD on epätäydellinen ja voi käsitellä vain merkkijonoja 0 s. Lisää lisää reunoja niin, että se voi käsitellä myöhemmät numerot merkkijonot. Seuraavassa taulukossa esitetään uusia siirtymäsääntöjä, joita voidaan lisätä seuraava vaihe: Binary-merkkijonon 1 käsittelemiseksi pitäisi olla siirtymäsääntö: (q 0. 1) q 1 Kaksi: - binäärinen esitystapa on 10. lopputila pitäisi olla q 2 . ja käsittelemään 10. tarvitsemme vain yhden siirtymäsäännön: (q 1. 0) q 2-polku. (q 0) 1 (q 1) 0 (q 2) Kolme: - binaarissa se on 11. lopputila on q 3. ja meidän on lisättävä siirtymäsääntö: (q 1. 1) q 3-polku. (q 0) 1 (q 1) 1 (q 3) Neljä: - binaarisessa 100. lopputilassa q 4. TD käsittelee jo etuliitejonoa 10 ja tarvitsemme vain uuden siirtymäsäännön: (q 2. 0) q 4-polku. (q 0) 1 (q 1) 0 (q 2) 0 (q 4) Vaihe 3. Viisi 101 Siirtymäkaavion yläpuolella kuvassa 2 on edelleen puutteellinen ja monta puuttuvaa reunaa on olemassa. Esimerkiksi siirtymä ei ole määritelty: (q 2. 1) -. Ja säännön tulisi olla läsnä 101: n merkkijonojen käsittelyyn. Koska 101 5 on jaollinen 5: llä ja hyväksyä 101, lisään: (q2.1) q0 yllä olevassa kuvassa-2. Polku: (q 0) 1 (q 1) 0 (q 2) 1 (q 0) tämän uuden säännön kanssa, siirtymäkaavio tulee seuraavasti: Jokaisen vaiheen alapuolella valitsen seuraavan seuraavan binaarinumeron puuttuvan reunan lisäämiseksi, kunnes saan TD täydelliseksi DFA: ksi. Voimme käsitellä 11 nykyisessä TD: ssä kuvassa 3 seuraavasti: (q 0) 11 (q 3) 0 (). Koska 6 5 1 tämä tarkoittaa lisätä yhden säännön: (q 3. 0) q 1. Vaihe 6 Lisää kaksitoista, kolmetoista, neljätoista Reunojen kokonaismäärä siirtymäkaaviossa kuva-12 on 15 Q5 3 (täydellinen DFA). Ja tämä DFA voi hyväksyä, että kaikki merkkijono koostuu siitä, mikä desimaaliluku on jaollinen 5: llä. Jos huomaat jokaisessa vaiheessa, taulukossa on kolme merkintää, koska jokaisessa vaiheessa lisään kaikki mahdolliset lähtevät reunat tilasta täydellisen DFA: n tekemiseksi (ja Lisään reunan niin, että qr valtion saa loput on r) Lisätä lisäksi, muistakaa kahden säännöllisen kielen liittäminen ovat myös säännöllisiä. Jos haluat suunnitella DFA: n, joka hyväksyy binääriset merkkijonot, desimaaliekvivalentti on joko jakautuva 3 tai 5, piirrä sitten kaksi erillistä DFA: ta jakautuvaksi 3: llä ja 5: llä ja liitä sitten molemmat DFA: t DFA: n rakentamiseksi (1 lt n lt 10 liittoon 10 DFA: ta). Jos sinua pyydetään tekemään DFA: sta, joka hyväksyy binääriset merkkijonoet, niin että desimaaliluku on jaollinen 5: llä ja 3: llä, niin sitten etsit DFA: ta, joka on jaollinen 15: llä (mutta mikä on noin 6 ja 8). Huomaa: tällä tekniikalla piirretyt DFA: t minimoidaan DFA: n avulla vain silloin, kun n: n ja emäksen välillä ei ole yhteistä tekijää. ensimmäisessä esimerkissä ei ole 5: n ja 2: n välillä tai 5: n ja 3: n välillä toisessa esimerkissä, joten molemmat DFA: t, jotka on konstruoitu edellä, minimoidaan DFA: t. Jos olet kiinnostunut lue lisää mahdollisista mini-tiloista numeroon n ja b-lukupaperiin: Divisibility and State Complexity. Alla on lisätty Python-skripti, kirjoitin sen hauskanpitoa oppimalla Python-kirjaston pygraphviz. Lisään sitä, toivon, että se voi olla hyödyllistä jollekulle jonkin verran. Suunnittele DFA b-numero-merkkijonoille, jotka ovat jaettavissa numerolla n: Joten voimme soveltaa edellä mainittua temppua piirtää DFA: ta tunnistamaan lukujonoja mistä tahansa perusjoukosta b ne ovat jakaja annettuina n: na. Tällöin DFA: n tilojen kokonaismäärä on n (n jäljellä olevilla alueilla) ja reunojen lukumäärän on oltava yhtä kuin b n mdash, joka on täydellinen DFA: b symbolimäärä DFA: n ja n tilamäärän kielellä. Käyttämällä yllä temppua, alla olen kirjoittanut Python-komentosarjan piirtämään DFA: n syöttöalustaan ja numeroon. Skriptissä toiminto dividedbyN populates DFAs siirtymäsäännöt perus numero vaiheet. Jokaisessa vaiheessa-num, muuntaisin num numeerimerkkiin numeerisesti funktion baseN () avulla. Jotta vältettäisiin kunkin numerojonon käsitteleminen, olen käyttänyt väliaikaista tietorakennetta tarkasteltavissa. Kussakin vaiheessa numeeristen merkkijonojen loppumäärää arvioidaan ja tallennetaan lookuptable - muodossa käytettäväksi seuraavassa vaiheessa. DFA: n siirtymäkaavioon olen kirjoittanut funktion drawtransitiongraphin käyttäen Pygraphviz-kirjastoa (erittäin helppokäyttöinen). Tämän scriptin käyttämiseksi sinun on asennettava graphviz. Lisäämällä värikkäitä reunoja siirtymäkaaviossa satunnaisesti luodaan värikoodit jokaiselle symbolille getcolordict-toiminnolle. Vastaavasti, kirjoita base 4 ja numero 7 generoimaan - dfa hyväksyvän numeron merkkijono 4, jotka ovat jaettavissa 7 Btw: llä, yritä vaihtaa tiedostonimi. png: hen tai. jpeg: iin.
No comments:
Post a Comment