Automaton

Schrijver: Leandro Alegsa

28-02-2021

Een automaat (een automaat, meerdere automaten) is een begrip uit de wiskunde. Soms wordt het begrip toestandsautomaat genoemd. Het is als een abstracte machine.

Zo'n machine kan input krijgen, die ofwel wordt afgewezen, ofwel wordt aanvaard. Het is als een verkoopautomaat. Wanneer iets wordt gekocht, moeten er munten (of geld) in de machine worden gedaan. Als dit de juiste munten zijn, worden ze aanvaard, en wordt het gevraagde voorwerp gedropt zodat het kan worden verwijderd. Als de munten verkeerd zijn, worden ze geweigerd.

Intern heeft de automaat verschillende toestanden waarin hij kan verkeren. Door hem input te geven kan hij van toestand veranderen (of niet). Op die manier doorloopt de automaat alle invoer, waarbij hij één item (dat wiskundigen een symbool noemen) per keer consumeert. Wanneer er geen symbool meer over is, bevindt de automaat zich in een bepaalde toestand. Dit kan een eindtoestand zijn. In dit geval wordt de invoer aanvaard. Anders wordt de invoer verworpen.

Als de machine een aftelbaar, eindig aantal toestanden heeft, wordt zij eindige toestandsmachine genoemd. Een diagram dat alle toestanden en overgangen van zo'n machine weergeeft, wordt eindig toestandsdiagram genoemd.

Een gebruikelijke voorstelling van een automaat in de computerwetenschap. Deze automaat "aanvaardt" alle opeenvolgingen van de letters a en b die beginnen met een a en eindigen met een b.

Problemen

Net als in het echte leven zijn er automaten die te ingewikkeld zijn om te begrijpen. De wiskundige en de informaticus vragen zich daarom af of een bepaalde automaat minimaal is. Als het niet minimaal is, moet er een andere automaat zijn met minder toestanden die hetzelfde kan doen. Een voorbeeld van een automaat is de turingmachine.

Vragen en antwoorden

V: Wat is een automaat?

A: Een automaat is een concept uit de wiskunde dat lijkt op een abstracte machine en dat input kan krijgen die ofwel wordt afgewezen ofwel wordt aanvaard.

V: Wat is een andere term voor een automaat?

A: Soms wordt het concept een toestandsmachine genoemd.

V: Kunt u een automaat vergelijken met een verkoopautomaat?

A: Ja, het is als een verkoopautomaat waar munten of geld in de automaat moeten worden gestoken, en als het de juiste munten zijn, wordt het gevraagde artikel gedropt zodat het kan worden verwijderd.

V: Wat gebeurt er wanneer input wordt gegeven aan een automaat?

A: De automaat doorloopt alle invoer, verbruikt één voorwerp per keer, en heeft intern verschillende toestanden waarin hij kan verkeren. Het geven van input kan zijn toestand al dan niet veranderen.

V: Wat gebeurt er als er geen symbolen meer zijn voor de automaat?

A: Als er geen symbolen meer zijn, verkeert de automaat in een bepaalde toestand, die een eindtoestand kan zijn. Als dit het geval is, wordt de invoer aanvaard; anders wordt de invoer verworpen.

V: Wat is een eindige toestandsmachine?

A: Als de machine een telbaar, eindig aantal toestanden heeft, wordt hij een eindige toestandsmachine genoemd.

V: Wat is een eindig toestandsdiagram?

A: Een diagram dat alle toestanden en overgangen van een dergelijke machine weergeeft, heet een eindig toestandsdiagram.