Automatentheorie

Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen Automaten lösbaren Problemen beschäftigt.

Sie ist ein wichtiges Werkzeug der Berechenbarkeitstheorie und Komplexitätstheorie. Praktische Anwendung findet sie beim Entwurf von lexikalischen Scannern und Parsern im Compilerbau sowie für den Entwurf von Programmiersprachen.

Die Automatentheorie befasst sich mit formalen Sprachen und formalen Grammatiken, die u. a. durch die Chomsky-Hierarchie typisiert werden, und mit Modellen für Automaten, die solche Sprachen verarbeiten können, insbesondere endliche Automaten, Kellerautomaten, Zellularautomaten und Turingmaschinen.

Siehe auch

Literatur

Weblinks

Commons: Automatentheorie – Sammlung von Bildern, Videos und Audiodateien
Wiktionary: Automatentheorie – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Auf dieser Seite verwendete Medien

Science-symbol-13a.svg
Autor/Urheber: Psychoslave, Lizenz: CC BY-SA 3.0
Symbol for cybernetics and - if applicable - other structural sciences.
vectorisation of Science-symbol-13a.png (From wikipedia en:Image:Science-symbol-13a.png and de:Bild:Science-symbol-13a.png Autor: de:Benutzer:jwdietrich2 Category:Science Category:Symbols )