Toestandsautomaten en reguliere expressies
Last updated
Last updated
Je hebt vast wel eens gehoord van reguliere expressies. Je kunt ze bijvoorbeeld gebruiken om bepaalde patronen te herkennen in tekst. Stel je maar eens voor dat je het volgende wilt zoeken in een stuk tekst:
hoi
hoooooi
hoooooooooooooooooooooi
Kortom alles wat begint met een h, dan aan aantal o's (minimaal 1) en dan een i. Je kunt in je programma dan eerst zoeken naar hoi, dan naar hooi, dan naar hoooi etc. maar als ervaren programmeur voel je al dat dat niet handig is. Hier komen reguliere expressies om de hoek kijken.
Kijk maar naar het volgende toestandsdiagram:
We beginnen in de toestand start en we willen graag in toestand 3 komen. Dit is de eindtoestand en in dit geval de acceptatietoestand. Als we een string bekijken en we komen daarbij in de acceptatietoestand, dan is dat een 'geldige' string. Anders gezegd:
Om een variatie op 'hoi' te herkennen, moeten we in toestand 3 komen.
We beginnen in start
De eerste letter is een 'h' dus we gaan naar toestand 1
De tweede letter is een 'o' dus we gaan naar toestand 2
De derde letter is een 'i' dus we gaan naar toestand 3
Het woord is geaccepteerd!
We beginnen in start
De eerste letter is een 'h' dus we gaan naar toestand 1
De tweede letter is een 'o' dus we gaan naar toestand 2
Iedere letter 'o' zorgt ervoor dat we in toestand 2 blijven.
De laatste letter is een 'i' dus we gaan naar toestand 3
Het woord is geaccepteerd!
We beginnen in start
De eerste letter is een 'h' dus we gaan naar toestand 1
De tweede letter is een 'o' dus we gaan naar toestand 2
Vanuit toetstand 2 is er geen overgang voor de letter 'p'.
We kunnen nooit in toestand 3 komen dus het zal niet geaccapteerd worden!