Állapotgépek, reguláris kifejezések

Állapotgépek

Szmájli	Ezt kell beírni
	:) :-)
	:D :-D
	<3

Feladat: megkeresni a beírt szövegben a szmájlikat, és utána úgy kiírni a szöveget, hogy képek szerepelnek benne helyettük.

Oldjuk meg ezt minél kevesebb memória felhasználásával!

Lehetne működőképes megoldást csinálni úgy, hogy beolvassuk az egész szöveget egy sztringbe. De ez elég rossz ötlet. Ha látunk egy hosszú szöveget, abban rá tudunk mutatni a szmájlikra, anélkül, hogy az előttük vagy utánuk lévő részt ismernünk kellene.

A feladatot elképzelhetjük egy adatfolyam (stream) problémaként. Valaki diktálja nekünk a szöveget (bejövő karakterek), nekünk pedig le kell írni azt (kimenő karakterek). A diktálás közben pedig nem szeretnénk a teljes szöveget, vagy hosszú szövegrészletet a fejünkben tartani.

Karakterek olvasása: a print()-en és input()-on kívül használhatóak:

import sys

c = sys.stdin.read(1) # olvas

sys.stdout.write(c) # ír

Nagyon fontos: a read(1) üres sztringet is adhat!

c = sys.stdin.read(1)

if c == "":
    print("Nincs adat, bemenet vége.")
else:
    print("Karakter:", c)

Példa: Blian élete. Az alábbi ploglam minden 'r' betűt 'l' betűle cselél.

import sys

def main():
    while True:
        c = sys.stdin.read(1)
        if c == "":
            break
        
        if c == 'r':
            sys.stdout.write('l')
        elif c == 'R':
            sys.stdout.write('L')
        else:
            sys.stdout.write(c)

main()

Emlékezzünk vissza: a program bemenete és kimenete fájlból/fájlba átirányítható. Például, ha a kimenetét a képernyő helyett egy fájlba szeretnénk átirányítani:

Átirányítás fájlba:

C:\> python3 blian.py >kimenet.txt
Brian élete

C:\> type kimenet.txt
Blian élete

Átirányítás fájlból:

C:\> type szoveg.txt
Példa bemenet a programnak.

C:\> python3 blian.py <szoveg.txt
Példa bemenet a ploglamnak.

Feladat: számoljuk meg a beolvasott szövegben az ly betűket:

• Az ly 1-nek számít: lyuk,
• az lly 2-nek: gally,
• nagybetűkkel most ne foglalkozzunk.

A probléma nehézsége

Önmagában egyik karakternél sem egyértelmű a teendő!

• l-nél: nem tudjuk, mit kell majd csinálni: alma, lyuk, gally
• y-nál: a teendő attól függ, előbb mi történt: négy, lyuk

Azt azért sejtjük, hogy a végleges döntés az y karakternél fog megszületni. Az l-nél nem lehet, hiszen a jövőbe nem látunk. Úgyhogy a második gondolatmenet a járható út. Eltárolni a teljes szöveget viszont felesleges, hiszen elég mindig csak egy kis részletet látni belőle.

Állapotgép = véges automata (finite-state machine)

Példa: italautomata

Az italautomata klasszikus példa az állapotgépre. Ez másképp reagál a sztornó gomb és az italválasztó gomb megnyomására attól függően, hogy be lett-e dobva már a pénz, vagy még nem. Ha bedobunk pénzt, és választunk italt, meg is kapjuk azt. Ha nem dobtunk be pénzt, hiába nyomkodjuk az italválasztó gombokat, nem fog történni semmi.

A kidolgozatlan ötlet az előzőek alapján:

sz = 0
while True:
    c = sys.stdin.read(1)
    if c == "":
        break
    
    if c == "y":
        if ……… l volt előtte ………:     # !
            sz += 1
        elif ……… ll volt előbb ………:   # !
            sz += 2

print(sz, "darab ly szerepelt.");

Tehát szükségünk van egy változóra, ami azt reprezentálja, mik voltak az előzmények, mi történt a múltban. Az y karaktert pedig ennek függvényében értelmezzük: nem l volt előtte, vagy egy l volt előtte, esetleg kettő. Ezt nevezzük állapotváltozónak.

Tervezzük meg az „ly” számláló állapotgépét! Melyik állapotban, milyen esemény hatására, mi a teendő?

Az alap állapotban egy l hatására még nem történik semmi, de tudjuk, hogy a következő karakternél figyelni kell, mert az esetleg egy y lehet. Ezért felvesszük az l_volt állapotot. Alap állapotban a másik két karaktertípus hatására semminek nem kell történnie. Az l_volt állapotnál y esetén növeljük a számlálót, és visszaugrunk alap állapotba (hiszen a következő karakternél már nem lesz igaz, hogy az ahhoz képest előző l betű volt). Az ll_volt állapotnál viszont egy harmadik l betű esetén maradunk ugyanabban az állapotban, mert a következő karakternél igaz lesz az, hogy az előző kettő l volt. (Ha van ilyen magyar szó egyáltalán.)

Az állapotgép működését állapotátmeneti gráffal adhatjuk meg. Minden állapotra (a gráf csúcsai) megadja, hogy az egyes eseményeknél (élekre írt karakterek) mi a teendő. A nyíl az új állapot felé mutat, illetve az elvégzendő tevékenység is a nyíl mellé írva szerepel.

Ez a megadás teljesen ekvivalens a táblázattal, amelyet a következő pont mutat majd be. Az állapotátmeneti gráf sokszor kevésbé áttekinthető, mint a táblázat – ha abból kell kódolni, akkor nehéz lehet követni a nyilakat. Az sem látszik rajta, hogy teljesen definiált-e, szemben a táblázattal, ahol látjuk, hogy minden cellája ki van-e töltve. Viszont tervezésre, ötletelésre kiválóan alkalmas. Az állapotgép által felismert jelsorozatokat (eseménysorozatokat) is könnyebb ezen felismerni, egyszerűen csak követni kell az átmenetekre (nyilakra, élekre) írt feliratokat.

A három lehetséges állapot: alap, l_volt és ll_volt.

Felsorolt típusként:

class LyAllapot:
    alap = 1
    l_volt = 2
    ll_volt = 3

Egyszerűen konstansokkal:

ALAP = 1
L_VOLT = 2
LL_VOLT = 3

Mivel az állapotváltozó lehetséges értékei egy véges halmazból kerülnek ki, ezért eszünkbe juthat a felsorolt típus. Ezt Pythonban osztálybeli konstansokkal szoktuk megvalósítani. Másik lehetőségünk, hogy egyszerűen konstansokat használunk. Ezek olyan változók, amelyeknek csak egyszer adunk értéket, és többször nem változtatjuk meg. Pythonban az a szokás, hogy az ilyenek nevét csupa nagybetűvel írjuk – hogy lehessen látni rajta, kicsit másra való, mint a többi változó.

Az állapotokat mindenképpen érdemes elnevezni valahogy a forráskódban is. Megtehetnénk, hogy egész számokat használunk állapotokat, de akkor a programkód követhetetlen lenne. Így viszont olvasható lesz, a programkódba is bekerülnek az állapotok nevei. Hogy milyen számokat rendelünk hozzá az állapotokhoz, az teljesen mindegy.

allapot = ALAP

while True:
    c = sys.stdin.read(1)
    if c == "":
        break
    
    if allapot == ALAP:
        if c == "l":
            allapot = L_VOLT
    elif allapot == L_VOLT:
        if c == "l":
            allapot = LL_VOLT
        elif c == "y": 
            sz += 1
            allapot = ALAP
        else:
            allapot = ALAP
    elif allapot == LL_VOLT:
        # ...

Minden beérkező karakternél a tevékenység és a következő állapot is függ a beérkező karaktertől és az állapottól. Más például a teendő egy beérkező y karakternél akkor, ha előzőleg l betűt láttunk. Ezért minden karakter feldolgozásánál a táblázat egy cellájából kell kiolvasnunk a teendőket. Ez alapján a kódban egy esetszétválasztást csinálhatunk, ami viszont triviális: a meglévő állapottábla vagy állapotátmeneti gráf alapján a programkód szisztematikusan, szinte gondolkozás nélkül elkészíthető!

Az eddigiek alapján a táblázat könnyen elkészíthető, most az egyszerűsítés kedvéért csak két szmájlira:

	normál	:	)	<	3
alap	→alap c	→kettőspont (semmi)	→alap c	→kisebb (semmi)	→alap c
kettőspont	→alap :, c	→kettőspont :	→alap	→kisebb :	→alap :, c
kisebb	→alap <, c	→kettőspont <	→alap <, c	→kisebb <	→alap

Itt is az állapotgép táblázatában minden cella tartalmaz egy következő állapotot (fent) és egy tevékenységet (lent). A tevékenység minden esetben valamilyen karakter vagy karakterek kiírását jelenti. c-vel jelöltük az épp beolvasott karakter képernyőre másolását; a többi kiírásnál pedig a megadott jelet kell majd a programnak kiírnia (pl. kisebb jel vagy kettőspont).

Mivel minden oszlopban ugyanaz az állapotátmenet, egyszerűbbnek tűnik az esemény (karakter) szerint csinálni az első esetszétválasztást:

if c == ':':
    if allapot == ALAP: pass
    elif allapot == KETTOSPONT: sys.stdout.write(':')
    elif allapot == KISEBB: sys.stdout.write('<')
    allapot = KETTOSPONT
elif c == ')':
    if allapot == ALAP: sys.stdout.write(c)
    elif allapot == KETTOSPONT: sys.stdout.write('☻')
    elif allapot == KISEBB: sys.stdout.write('<' + c)
    allapot = ALAP

Az állapot- és tevékenységtábla kézzel történő leprogramozása (ti. a hosszadalmas if–else sorozatok) helyett lehet egy sokkal okosabb ötletünk is.

Táblázat → csináljunk 2D listát a kódban!

• Minden cellában egy tevékenység és egy állapot. Ez azt jelenti, hogy a táblacella egy objektum.
• Az állapot: a következő állapot kódja.
• A tevékenységek: mi a teendő.

A tevékenység az ly számláló példájában könnyen leképezhető akár egy egész számra: mennyivel kell növelni a számlálót. Összetettebb esetben függvényeket is tehetünk ide – erről később lesz szó.

Az adatszerkezet: objektumok kétdimenziós táblázata.

class TablaCella:   # vagy simán egy tuple
    def __init__(self, allapot, tevekenyseg):
        self.allapot = allapot
        self.tevekenyseg = tevekenyseg

allapottabla = [
    [ ... ],
    [ ... ],
]

Kérdés, hogyan fogjuk ezt a listát indexelni.

Az állapotból és a karakterből is tömbindexet kellene csinálni:

• A sorokat az állapot szerint indexeljük: tabla[all]
• Az oszlopot a karakter szerint indexeljük: tabla[all][kar_o]
• Azon belül pedig pl. tabla[all][kar_o].allapot

ALAP = 0        # állapot → 0...2 egész szám
L_VOLT = 1
LL_VOLT = 2

def karakterosztaly(c): # char típusa → 0...2 egész szám
    if c == 'l': return 0
    if c == 'y': return 1
    return 2

Az állapotnál egyszerű a feladatunk. Azt amúgy is felsorolt típussal ábrázoljuk, vagy egyszerű konstansokkal, tehát már hozzárendeltünk egész számokat. Kicsit módosítjuk ezt, hogy 0-tól induljanak, mert a listát is 0-tól indexeljük.

A karakterekkel kicsit gondban vagyunk, azokat nem lehet ilyen egyszerűen – sok százezerféle karakter van, amelyeknek a kódja is igen nagy szám lehet. De nekünk csak háromfélét kell megkülönböztetni, az l betűt, az y betűt és az összes többit. Ezért írunk egy függvényt, amely ezekhez a kategóriákhoz rendel egész számokat. Kicsit „sormintás”, de most jó lesz ez a megoldás is.

A táblázat

allapotgep = [
    [(L_VOLT, 0),  (ALAP, 0), (ALAP, 0)], 
    [(LL_VOLT, 0), (ALAP, 1), (ALAP, 0)], 
    [(LL_VOLT, 0), (ALAP, 2), (ALAP, 0)], 
]

A táblázat egy az egyben megfelel az állapotátmeneti táblázatnak, amelyet először rajzoltunk ehhez a feladathoz.

A táblázatot használó kód

while True:
    c = sys.stdin.read(1)
    if c == "": break
    
    kar = karakterosztaly(c)
    (ujallapot, novekmeny) = allapotgep[allapot][kar]
    
    szaml += novekmeny
    allapot = ujallapot

Vagyis minden beolvasott karakterre csak kiolvassa a táblázatból a tevékenységet és a következő állapotot. Ez mindenhol egy tuple, amit az olvashatóság kedvéért kicsomagolunk az ujallapot és novekmeny nevű változókba. Így a tényleges tevékenység elvégzésénél (szaml += ...) és az állapotátmenetnél (allapot = ...) jobban olvasható a programkód.

Előnyök

• Tervezésnél: a tervezés eszköze!
• A felesleges állapotok kiszűrhetők
• Kódolásnál: mechanikusan kódolható
• Áttekinthetőbb, érthetőbb a kód, mint egy ad-hoc megoldás

Felhasználásuk

• Szűrőprogramok (fájlok feldolgozása); fordítóprogramok, nyelvi elemzők (pl. kommentek kiszűrése)
• Alkalmazások vezérlése (pl. egérkattintások, mozdulatok)
• Internetes alkalmazások kommunikációja (protokollok)
• Hardver: a processzor egy nagy állapotgép!

Hardver oldalról is fontos az állapotgép. A számítógép belseje is tele van ilyenekkel. A processzor működését is egy állapotgép vezérli: utasítás beolvasása, beolvasott utasítás dekódolása, utána további operandusok beolvasása (már a dekódolt utasítás jelentése alapján) stb. Erről a Digit tárgyban van szó.

Reguláris kifejezések

Feladat: keressük ki egy Python forráskódból a kommenteket!

print("Helló, világ!")   # első komment
i = i + 123             
return 0                 # második komment

print("Helló, világ!")   # első komment
i = i + 123             
return 0                 # második komment

A reguláris kifejezéseket főként az alábbi két feladat elvégzésére használják.

Formátumvalidáció

Az első feladattípus: formátumok validációja. Például ellenőrizni szeretnénk, hogy a felhasználó helyes formátumban adta-e meg egy űrlapban az adatait. Helyes-e a bankkártyaszáma? Ez egy 16 számjegyet tartalmazó sztring kell legyen, ahol a számjegyek négyesével vannak csoportosítva, és a csoportok szóközök elválasztva. Ha az elválasztás nem szóközökkel történik, vagy valahol nem négy számjegy van, esetleg véletlenül egy betű kerül a sztringbe, akkor a formátum helytelen.

Szövegrészek keresése

Hogy jön a reguláris kifejezések témája az állapotgépekhez? Úgy, hogy sok reguláris kifejezés könnyedén állapotgéppé alakítható. Erre mutatunk a következőkben néhány példát, azzal a megjegyzéssel, hogy a téma matematikájába nem megyünk bele. Ez annak tisztázásához lenne szükséges, hogy pontosan mely reguláris kifejezések írhatóak le állapotgépekkel és melyek nem.

Vezessünk be előbb néhány jelölést! Legyen a példa egy olyan állapotgép (véges automata), amelyik az ^ly$ kifejezést próbálja meg illeszteni. (Oké, ez egy egyszerű sztringösszehasonlítással is megoldható, de most a rajz jelölései a lényegesek.) Ez azt mondja, hogy a sztring elején jönnie kell egy l betűnek, aztán egy y betűnek, végül pedig nem lehet már más.

Az automata 4 állapotot tartalmaz.

• Az 1-essel jelölt állapot a kezdőállapot. Ezt onnan ismerjük meg, hogy kívülről egy nyíl megy bele.
• Innen l betű hatására a 2-essel jelölt állapotba megyünk. Bármi más karakter hatására a 4-es állapotba.
• A pirosra színezett 4-es állapot a visszautasítást jelöli. Ha ide jutunk, az azt jelenti, hogy a sztring nem illeszkedett. Például ha nem l betűvel kezdődött, akkor az 1→4 állapotátmenet után a feldolgozást be is fejezhetjük.
• Az y hatására a 2-es állapotból a 3-asba ugrik az automata. Ez az ún. elfogadó állapot, ugyanis ha itt vége lett a sztringnek, akkor tényleg egy "ly"-ról volt szó. Ha jönne még karakter, akkor viszont innen is a 4-esbe ugrik az automata – a visszautasításhoz, mert az y után már nem lehetne semmi.

Ez a rajz ugyanazt mutatja, mint a fenti, csak egyszerűbb jelölésekkel.

• A kezdőállapotot ugyanúgy jelöljük – kívülről belemutató nyíllal.
• A visszautasító állapotot nem jelöljük. Ha bárhol olyan bemenetet kap az automata, amihez nem tartozik jelölt átmenet, akkor azt jelölés nélkül elutasításnak tekintjük.
• Ezzel együtt értelemszerűen az „egyéb” feliratú átmenetek is eltűntek az ábráról.
• Az elfogadó állapotot duplán bekarikázás jelöli.

A reguláris kifejezés illesztéséhez tehát építeni kell egy véges automatát. Nézzük meg néhány egyszerűbb esetben, hogy működnek ezek! A példákban az egyszerűség kedvéért mindig teljes sztringet próbálunk illeszteni; vagyis a reguláris kifejezés elején mindig ^, a végén mindig $ lesz.

A + operátor egy vagy több előfordulást jelent. Tehát a sztring elején kell legyen egy a betű. Utána kell jönnie egy b betűnek, ami újabb állapotátmenetet eredményez. Innen két úton mehetünk tovább. Jöhet még b betű, akkor nem váltunk állapotot (tehát emiatt akármennyi további b betűt „megeszünk” ezen a ponton). Vagy egy c betű, aminek hatására az elfogadó állapotba kerülünk.

Mi történik, ha teszünk egy zárójelet az ab köré? Ilyenkor a + ismétlés operátor az ab karaktersorozatra vonatkozik, nem csak a b betűre. Vagyis az abc, ababc, abababc és hasonló sztringeket találja meg ez a kifejezés. Véges automatával ez is könnyen megvalósítható: amikor a b betű utáni állapotban vagyunk, onnan a betű hatására abba az állapotba kell visszamenni, amelybe a kezdeti a betű által is kerültünk. Így egy újabb b következhet majd, kiadva a második ab sorozatot. De ez megtörténhet bárhányszor.

A * operátor is ismétlést jelent, de ez elfogadja a nulla darab előfordulást is. Vagyis az ^ab*c$ reguláris kifejezésre az "ac" sztring is illeszkedik, a közepén nulla darab b betűvel. Ezért az a betű utáni, középső állapotból a b betű hatására nem mozdulunk el. Ha egyáltalán nincs b a sztring közepén, hanem az a után máris c jön, akkor elfogadjuk a sztringet. Ha viszont jön b, az nem változtat azon a helyzeten, hogy az a jó volt; egy c-nek persze jönnie kell előbb vagy utóbb.

Az ^ab?c$ kifejezésben a b megjelenése opcionális. Vagyis ez csak az "ac" és "abc" sztringekre illeszkedik. Az a utáni c-vel így egyből elfogadó állapotba jut a keresés. Ha az a után b jön, akkor egy másik állapotba kerül az automata – ahonnan persze c hatására ugyanúgy továbbhalad, mintha a b karakter nem jelent volna meg a sztringben.

Fontos látni a különbséget eközött és a * operátor között. A * esetén a gráfon hurokél jelenik meg, vagyis ugyanabban az állapotban marad az automata, mint előtte. Emiatt illeszthető a * előtti rész, vagyis a b betű bárhányszor. Itt viszont mindenképpen tovább kell haladni, hogy a b-t maximum egyszer illesszük csak.

A Python is tartalmaz beépítetten reguláris kifejezéseket feldolgozó függvényeket.

A használatnak két lépése van. Az első lépés az, hogy „le kell fordítanunk” a reguláris kifejezést. Ekkor a program ellenőrzi annak szintaxisát, és felépíti azt az állapotgépet, és egyéb más adatszerkezeteket, amikre később egy adott sztring illesztésekor szüksége van. Másik lépés pedig a „lefordított” reguláris kifejezés használata. Kényelmi funkcióként a Python ezt a két lépést egyetlen egy függvényben egyesíti, ez a re modul search függvénye. Most csak ezzel fogunk foglalkozni.

import re

try:
    regex = "ak+e"
    szoveg = "Nyakkendő és aknakereső."
    eredmeny = re.search(regex, szoveg)
    if eredmeny:
        eleje = eredmeny.start()
        vege = eredmeny.end()
        print("Illeszkedett, {}–{}".format(eleje, vege))
        print("Kivágott:", szoveg[eleje:vege])
    else:
        print("Nem illeszkedett.")
except re.error as e:
    print("Hiba történt:", e)

Illeszkedett, 2–6
Kivágott: akke

A függvény megkapja reguláris kifejezést és a vizsgálandó sztringet. A hibajelzés módja a szokásos: kivétel keletkezik, ha hiba történt. Ha viszont illeszkedést talált a függvény, akkor a visszatérési értéke nem None érték lesz, hanem egy Match objektum. Ennek legfontosabb függvényei a .start() és az .end(), amelyek az illeszkedő tartomány elejét és végét mutatják.

A re.search függvénynek meg lehetne adni a kezdő pozíciót is, ha több találatot is szeretnénk a sztringből kinyerni. Ha kíváncsiak lennénk, a sztring fennmaradó részében van-e még ilyen, akkor a 6-odik start pozíciótól kellene újra megpróbálnunk az illesztést, és másodjára meglenne az aknakereső „ake”-je is a nyakkendő „akke”-je után.

A zárójelekben megadott alkifejezések (csoportok, blokkok – grouping) szerepe valójában kettős. Ezzel nem csak precedenciát adhatunk meg, mint pl. az (ab)+ kifejezésben, ahol az ismétlés nem csak a b-re, hanem az ab karaktersorozatra vonatkozott. A re modul képes külön is kigyűjteni illesztett reguláris kifejezéseken belül a csoportok által meghatározott karaktersorozatokat (capture). Így a találatok esetén azok egyes belső részeit külön is megkapjuk sztringek formájában.

Kommentek tartalma

Az első példában kikeressük a forráskódból a kommenteket, és kigyűjtjük azok szövegeit (a kommenteket kezdő kettőskereszt karakterek nélkül).

print("Helló, világ!")   # első komment
i = i + 123
return 0                 # második komment

E-mail cím részei

A második példában e-mail címet vizsgálunk, és különválasztjuk belőle a kukac előtti és utáni részt.

A Python a regex motorja is képes a fentiekre. Találat esetén az eredmény objektum .group() függvénye adja meg a jelölt részeit.

regex = r"^([\w.]+)@(\w+(?:\.\w+)*)$"
szoveg = "valaki@pikac.hu"

eredmeny = re.search(regex, szoveg)
if eredmeny:
    print("Teljes illeszkedés:", eredmeny.group(0))
    print("Felhasználó:", eredmeny.group(1))
    print("Gép:", eredmeny.group(2))
else:
    print("Nem illeszkedett.")

Teljes illeszkedés: valaki@pikac.hu
Felhasználó: valaki
Gép: pikac.hu

A blokkokra a reguláris kifejezéseken belül is lehet hivatkozni. Ezt a visszaper karakterrel lehet jelölni; az utána írt szám a kifejezésben szereplő blokkra utal, a blokkok megjelenési sorrendjében. Az (a+)b\1 reguláris kifejezés ezért azt jelenti, hogy jönnie kell egy vagy több a betűnek (amennyi volt, azt megjegyezzük egy sztringben), aztán a következő karakter egy b betű kell legyen, végül pedig az első megjegyzett sztringrészlet újra. Vagyis pont ugyanannyi a betű kell legyen a b betű után, mint amennyi előtte volt.

Milyen állapotgépet konstruálnánk ehhez? Ha az elején egy a betű volt, a végén is egy kell legyen. Ha kettő, akkor olyan állapotba kell kerülni, ahonnan egy b betűvel és két további a betűvel lehet az elfogadáshoz jutni. (A többszörös egymás utáni állapotátmeneteket most csak pontozott vonallal jeleztük, hogy áttekinthető legyen a rajz.) A három a betűs kezdethez is tartoznia kell egy állapotnak, a négy betűshöz is, és így tovább. Az állapotokba írt számok azt jelölik, hány kezdő a betű hatására lehet oda eljutni.

Azt vesszük észre, hogy a tetszőlegesen sok ismétlődés és a visszahivatkozás miatt tetszőlegesen sok állapottal kellene rendelkeznie az automatának. Így viszont nem lenne véges, vagyis ez a feladat nem oldható meg véges automatával.

A matematikában használt reguláris kifejezés fogalom ezért különbözik a programozásban használt reguláris kifejezésektől. Az utóbbiak többféle szabályt tartalmazhatnak, és a lehetséges szabálytípusok között vannak olyanok is, amelyek már nem írhatóak le állapotgépekkel; ilyen a visszahivatkozás is. Az összetettebb kifejezéseket feldolgozni képes könyvtárak, mint amilyen a Pythoné is, nem mindig állapotgépekkel dolgoznak.

* – a lehető legtöbb

s = "alma" + "fa"

*? – a lehető legkevesebb

s = "alma" + "fa"

A *? a lehető legrövidebb illeszkedést jelenti. Vagyis miután a motor megtalálta a nyitó idézőjelet az első sztringhez (alma), feltételezi, hogy a .* nulla karakterre illeszkedik. Ez azonban nem jön be, mert a sztring nem üres, tartalmaz szöveget. Ezért egyre hosszabb sztringrészletekkel próbálkozik: a, al, alm, alma... Végül sikerrel jár, mert a sztring teljes tartalma után megtalálja azt a bezáró idézőjelet, ami a szóköz és az összeadás operátor előtt előtt van.

Ugyanez megtörténik a második sztring esetén is (fa), vagyis összesen két sztringet tartalmaz a forráskód. A legrövidebb megoldás megkeresése miatt ezt nem mohó (non-greedy) ismétlésnek szokták nevezni.

s = "Ez itt valójában # nem egy komment."
# Ez pedig "nem sztring", hiába van idézőjelek között.

Mi a helyzet a ^(méh|méz|mos)$ reguláris kifejezéssel? Ez a három felsorolt szóra illeszkedik, és csak azokra. Rajzoljuk fel ezt állapotgéppel! Az opcionalitás miatt három irányba indulunk; a három ágon az „m, é, h”, továbbá az „m, é, z”, illetve az „m, o, s” betűket kell illesztenünk, vagyis azok hatására kell a következő állapotba jutnunk. Bármelyik ágon végigértünk, elfogadó állapotba jutunk, egyéb esetben pedig nem illeszkedett a sztring.

Mit jelent ennek az automatának a kezdő állapota? Onnan három irányba indulhatunk, de minden irányba az m betű hatására megyünk tovább. Hogyan döntjük el, hogy merrefelé kéne menni? Az első m betű hatására ez nem dönthető el. Ha az első m betű hatására elindulunk a felső úton, a „méz” felé, aztán jön egy é betű, akkor azt hihetjük, jó úton járunk. De ha végül kapunk egy h betűt, vagyis a „méh” szó volt a bemenet, akkor nem utasíthatjuk vissza a sztringet. Ha a „mos” felé indulnánk kezdetben az m betű miatt, akkor a „méh” és „méz” szavakat utasítanánk vissza, pedig azokat is el kell fogadni.

Az ábra egy nemdeterminisztikus véges automatát mutat (nondeterministic finite state automaton, NFA), amelyiknél egy adott állapotból több irányba is továbbmehetünk ugyanazon esemény hatására. Egy ilyen automata működését elképzelhetjük úgy, hogy az nem egy, hanem egyszerre több állapotban van.

Lássuk, mit jelent ez! A kezdő állapot egyértelmű. Jelöljük meg ezt egy színnel, egy ún. tokennel!

Ha nem m betű érkezik elsőként, meg is állunk. Viszont ha igen, akkor továbbmegyünk mindhárom irányba, ahova m-mel jelölt nyíl vezet. Ilyenkor a token osztódik: most három tokenünk van, mindhárom tippünk bejöhet még:

Hogy mi a szó többi része, az majd kiderül. Tegyük fel, hogy ezután egy é betű érkezik. Ekkor az alsó úton, a „mos” szó felé haladó illeszkedés elakad. Azt a tokent eldobjuk. Viszont ez nem gond, mert még van olyan út, ami végül találathoz vezethet. Innentől két tokennel dolgozunk tovább:

Ebből az állapotból akár h betűvel, akár z betűvel az elfogadáshoz tudunk jutni: mindkét esetben az egyik tokent ugyan eldobjuk, de a másik beér a célba. Ha más karaktert kapunk, pl. egy g betűt („még”), akkor elveszik az összes token, ami visszautasítást jelent.

Összefoglalva a működés lényegét: a nemdeterminisztikus automata egyszerre több állapotban is lehet. Ha a bemenet hatására több irányba lehet indulni, az állapotot jelző token token többszöröződik. Ha az illesztés valamelyik úton elakad, akkor azt a tokent eldobjuk.

Másik lehetőségünk, hogy a nemdeterminisztikus automatát determinisztikus automatává (deterministic finite state automaton, DFA) alakítjuk. Matematikailag bizonyított, hogy ez mindig megtehető; a művelet néha az állapotok számának csökkenésével, néha pedig növekedésével jár (sajnos akár igen nagymértékűvel). Ebben a példban szerencsére csökken az állapotok száma:

Az ábráról leolvasható, hogy a ^m(é[hz]|os)$ reguláris kifejezés pontosan ugyanazokra a szavakra illeszkedik, mint az eredeti, ^(méh|méz|mos)$ kifejezés.

Az előadáson megismertek alapján:

• Egyesével karaktereket írni, olvasni. (sys)
• Klasszikus állapotgépeket tervezni állapottáblával.
• Dokumentáció segítségével alapvető reguláris kifejezéseket használni.