10. märtsi praktikum
Kodutöö arutelu: Regex → NFA
Kuna kodutöö valmistas mõningaid raskusi, proovime paremini aru saada, kuidas võiks algoritmiliselt teostada regulaaravaldise puu läbimist. Teeme kõigepealt koos läbi (a|b)*b(a|b)
teisendamist automaadiks. Valige ise üks järgmistest regulaaravaldistest ja tehke sama protsess läbi:
(a|ε)*b
(a*|b*)ab
Automaatide koostamine: AKTRegexChallenge
Selle ülesanne eesmärk on koostada automaate, mis aktsepteerivad teatud keeli. Ülesannel on kolm eri raskust.
- Sõnad, milles esinevad täpselt üks '1' ja vähemalt üks '0'.
- Sõnad, mis sisaldavad paarisarv a-sid ja paarisarv b-sid.
- Kolmega jaguvad binaararvud.
Kõigepealt võib proovida, kas vastavad keeled õnnestub teil regulaaravaldistena kirja panna. (See on juba alates teisest tasemest väga raske!) Meil on selleks automaatne kontrollija: regex_checker.jar. Palju mõistlikum strateegia on kasutada JFLAP automaadi koostamiseks ja siis lasta JFLAP ise teisendada automaat regulaaravaldiseks. Tuleb aga meeles pidada, et JFLAP kasutab |
asemel +
.
Automaatidega modelleerimine
- Näide: bugide haldamine
- Näide: müügihaldus
- Autokooli läbimine
- java.io.InputStream
- GUId
- Plokkskeemid?