Automatentheorie
behandelt abstrakte Automaten, gedankliche Konzepte von Maschinen zur Informationsverarbeitung. Die A. diente ursprünglich vor allem dazu, den Begriffen der Berechenbarkeit und des Algorithmus eine strenge und doch anschauliche Fassung zu geben, heute bereits dazu, feinere Unterscheidungen in der Leistungsfähigkeit verschiedener Automatentypen zu treffen. Wichtig ist dabei meist zu zeigen, welche Art von Aufgaben mit welchem Automatentyp nicht bewältigt werden kann.
VP
LIT:
- G. Hotz/H. Walter: Automatentheorie und formale Sprachen. Bd. I. Mannheim/Zrich 1968.