Zum Inhalt springen
L

Wikipedia · einfach zusammengefasst · Stand

Automatentheorie

Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen …

Lesen · 2 Abschnitte Original auf Wikipedia
Inhalt2 Abschnitte
  1. 1. Gegenstand und Bedeutung
  2. 2. Formale Sprachen und Automatenmodelle

Gegenstand und Bedeutung

Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik. Sie untersucht Automaten, also Modellrechner, sowie die Probleme, die diese Automaten lösen können. Sie ist ein wichtiges Werkzeug der Berechenbarkeitstheorie und der Komplexitätstheorie.

Praktisch wird sie unter anderem beim Entwurf von lexikalischen Scannern und Parsern im Compilerbau eingesetzt. Außerdem ist sie für den Entwurf von Programmiersprachen bedeutsam.

Formale Sprachen und Automatenmodelle

Ein zentraler Gegenstand sind formale Sprachen und formale Grammatiken. Formale Sprachen können durch Grammatiken beschrieben werden; ihre Typen werden unter anderem mit der Chomsky-Hierarchie eingeordnet.

Die Theorie betrachtet Automatenmodelle, die solche Sprachen verarbeiten können. Dazu gehören endliche Automaten, Kellerautomaten, Zellularautomaten und Turingmaschinen.

Lernvideos zu Automatentheorie

10:25 Automatentheorie: Einstieg & DEA frankjuchim · 14.000 Aufrufe 15:07 Automatentheorie: Kellerautomaten frankjuchim · 13.104 Aufrufe

Weiterlesen

Theoretische Informatik Ihre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitätstheorie, aber auch die Logik und formale … Automat (Informatik) Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners. Problem Inhaltsverzeichnis · 1 Allgemeines · 2 Definitionen · 3 Problemklassen. 3.1 Lösbarkeit; 3.2 Zerlegbarkeit; 3.3 Verwandtheit · 4 Wissenschaften. 4.1 Denkpsychologie … Berechenbarkeitstheorie Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik ... Ein weiteres Problem ist das Halteproblem. Es … Komplexitätstheorie Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die … Programmiersprache Bei deklarativen Programmiersprachen ist der Ausführungsalgorithmus schon vorab festgelegt und wird nicht im Quelltext ausformuliert/beschrieben, sondern es … Formale Sprache Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu natürlichen Sprachen oft nicht die Kommunikation im Vordergrund steht, … Formale Grammatik Formale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert. Chomsky-Hierarchie Sie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die … Endlicher Automat Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein Modell eines Verhaltens, bestehend aus … Kellerautomat Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, … Turingmaschine Eine Turingmaschine ist ein mathematisches Modell der theoretischen Informatik, das eine abstrakte Maschine definiert. Bei diesem Rechnermodell werden nach …