Digszám 01 Reguláris nyelvek Flashcards
(11 cards)
Mi az a reguláris nyelv?
Olyan formális nyelv, amit reguláris kifejezéssel lehet leírni, és amit véges automaták (DFA vagy NFA) képesek felismerni.
Mi az a reguláris kifejezés?
Egy olyan szabályhalmaz, amivel leírható, hogy milyen szavak tartoznak egy adott nyelvhez. Fő műveletei: unió, konkatenáció, Kleene-csillag.
Mit jelent az, hogy egy nyelv zárt egy műveletre?
Azt, hogy ha az adott műveletet két (vagy több) nyelven elvégezzük, az eredmény is reguláris nyelv marad.
Mely műveletekre zártak a reguláris nyelvek?
Unió, konkatenáció, Kleene-csillag, metszet (komplementerrel és unióval), komplementer (DFA végállapot-csere).
Mit csinál a Kleene-csillag művelet?
Egy nyelv szavait ismétli tetszőleges alkalommal – akár nullaszor is. Példa: a* = {ε, a, aa, aaa, …}
Mi az NFA és a DFA közötti különbség?
A DFA-ban minden állapotból minden bemeneti szimbólumra egy és csak egy átmenet van. Az NFA-ban lehet több átmenet is egy szimbólumra, sőt, ε-átmenet is lehet (olvasás nélkül ugrás).
Mit jelent az $M = (K, Σ, δ, s, F)$ jelölés?
A véges automata definíciója:
- $K$: állapotok halmaza
- $Σ$: ábécé (bemeneti jelek)
- $δ$: átmenetfüggvény
- $s$: kezdőállapot
- $F$: elfogadó állapotok halmaza
Hogyan alakítunk egy reguláris kifejezést NFA-vá? (RE → NFA)
A három alapművelethez külön kis automatákat konstruálunk:
- Unió: új kezdő- és végállapot, ε-átmenetekkel
- Konkatenáció: első automata vége össze van kötve a második kezdetével
- Kleene-csillag: új hurok, ami visszavisz a kezdethez és elfogadja az üres szót is
Hogyan alakítható NFA → DFA?
Állapothalmaz-építéssel: minden DFA állapot egy halmaza az NFA állapotainak. Ezt hívjuk subset construction-nak.
Mi a Kleene-csillag intuitív jelentése?
Egy nyelv elemeinek ismétlése, nullától végtelenig. Pl. a* → lehet üres szó is, vagy akárhány a.
Mit jelent az, hogy egy szó generálható: $S ⇒^* w$?
A kezdőszimbólumból $S$ szabályokkal el tudunk jutni a szóhoz $w$, akárhány lépésben.
