Hoe word eindige staatsmasjiene gekombineer om die unie van tale te verteenwoordig wat deur twee masjiene erken word?
In die veld van berekeningskompleksiteitsteorie word eindigetoestandmasjiene (FSM's) wyd gebruik om die gedrag van stelsels te modelleer en te ontleed. FSM'e is wiskundige modelle wat bestaan uit 'n eindige aantal toestande en oorgange tussen hierdie toestande gebaseer op insetsimbole. Hulle word algemeen gebruik om gewone tale voor te stel, wat 'n subset van formele tale is wat deur gereelde uitdrukkings beskryf kan word of deur FSM'e gegenereer kan word.
Om die unie van tale wat deur twee FSM'e erken word, te verteenwoordig, moet ons die twee masjiene kombineer op 'n manier wat ons toelaat om stringe te herken wat aan enige van die tale behoort. Dit kan bereik word deur 'n proses genaamd die vakbondoperasie.
Die vereniging van twee FSM's, M1 en M2, behels die skep van 'n nuwe FSM, M, wat die taal erken wat gevorm word deur die unie van die tale wat deur M1 en M2 erken word. Dit kan gedoen word deur 'n nuwe begintoestand in te stel en dit aan die begintoestande van M1 en M2 te koppel deur gebruik te maak van ε-oorgange (oorgange wat geen insetsimbool verbruik nie). Die ε-oorgange laat die masjien toe om tussen die twee begintoestande te kies en dienooreenkomstig voort te gaan met die herkenningsproses.
Die vakbondbedryf vereis ook 'n paar wysigings aan die oorspronklike masjiene. Eerstens moet ons verseker dat die finale toestande van M1 en M2 finale toestande in die nuwe masjien M bly. Dit kan bereik word deur ε-oorgange van die finale toestande van M1 en M2 na 'n nuwe finale toestand in M in te stel. -oorgange laat die masjien toe om 'n string te aanvaar as dit deur M1 of M2 aanvaar word.
Verder moet ons verseker dat die oorgange van M1 en M2 in die nuwe masjien M behoue bly. Dit kan gedoen word deur bloot die oorgange van M1 en M2 na M te kopieer. Indien daar enige algemene oorgange tussen M1 en M2 is, kan hulle saamgevoeg word in 'n enkele oorgang in M.
Kom ons kyk na 'n eenvoudige voorbeeld om die proses te illustreer. Gestel ons het twee FSM'e, M1 en M2, soos hieronder getoon:
M1:
Begin toestand: q0
Finale toestand: q2
Oorgange: (q0, a) -> q1, (q1, b) -> q2
M2:
Begin toestand: p0
Finale toestand: p2
Oorgange: (p0, c) -> p1, (p1, d) -> p2
Om die unie van die tale wat deur M1 en M2 erken word, te verteenwoordig, skep ons 'n nuwe FSM, M:
M:
Begintoestand: s0 (nuwe begintoestand)
Finale toestand: f2 (nuwe finale toestand)
Oorgange: (s0, ε) -> q0, (s0, ε) -> p0, (q2, ε) -> f2, (p2, ε) -> f2
(q0, a) -> q1, (q1, b) -> q2, (p0, c) -> p1, (p1, d) -> p2
In hierdie voorbeeld erken die nuwe FSM M die unie van die tale wat deur M1 en M2 erken word. Dit begin in die nuwe begintoestand s0 en kan oorgaan na óf q0 óf p0 deur ε-oorgange te gebruik. Van daar af volg dit die oorgange van M1 en M2 gebaseer op die invoersimbole. As dit die finale toestand van óf M1 óf M2 bereik, kan dit oorgaan na die nuwe finale toestand f2 deur ε-oorgange te gebruik.
Om op te som, die unie van tale wat deur twee FSM'e erken word, kan verteenwoordig word deur die masjiene te kombineer en ε-oorgange in te voer om die keuse tussen die begintoestande moontlik te maak. Daarbenewens kan ε-oorgange gebruik word om die finale toestande van die oorspronklike masjiene aan 'n nuwe finale toestand in die gekombineerde masjien te verbind. Deur die oorspronklike oorgange te bewaar, kan die nuwe masjien stringe herken wat aan enige van die tale behoort wat deur die oorspronklike masjiene erken word.
Ander onlangse vrae en antwoorde t.o.v EITC/IS/CCTF Computational Complexity Theory Fundamentals:
- NP is die klas tale wat polinoomtydverifieerders het. Maar die verifieerder van 'n klas P is polinoom. Dit lyk asof hierdie NP-definisie los of teenstrydig is.
- 'n Verifieerder vir klas P is polinoom?
- Kan 'n Nondeterministic Finite Automaton (NFA) gebruik word om die toestandsoorgange en aksies in 'n firewall-konfigurasie voor te stel?
- Is die gebruik van drie bande in 'n multiband TN gelykstaande aan enkelbandtyd t2(vierkant) of t3(kubus)? Met ander woorde is die tydskompleksiteit direk verwant aan die aantal bande?
- As die waarde in die vastepuntdefinisie die limiet van die herhaalde toepassing van die funksie is, kan ons dit steeds 'n vaste punt noem? In die voorbeeld wat gewys word as ons in plaas van 4->4 4->3.9, 3.9->3.99, 3.99->3.999 het, … is 4 steeds die vaste punt?
- As ons twee TM'e het wat 'n beslisbare taal beskryf, is die ekwivalensievraag nog onbeslisbaar?
- In die geval van die opsporing van die begin van die band, kan ons begin deur 'n nuwe band T1=$T te gebruik in plaas daarvan om na regs te skuif?
- Hoe groot is die stapel van 'n PDA en wat bepaal die grootte en diepte daarvan?
- Is daar huidige metodes om Tipe-0 te herken? Verwag ons dat kwantumrekenaars dit haalbaar sal maak?
- Hoekom is LR(k) en LL(k) nie ekwivalent nie?
Sien meer vrae en antwoorde in EITC/IS/CCTF Computational Complexity Theory Fundamentals