Automaten und Grammatiken sind grundlegende Konzepte der theoretischen Informatik, die...
Informatik2,680 views·Updated Jun 25, 2026·2 pagesAutomaten und Grammatiken - Informatik Abi 2022 Zusammenfassung
Jule@jule156
1
of 2
Endliche Automaten und Mealy-Automaten
Deterministische endliche Automaten (DEA) funktionieren nach einem klaren Prinzip: Für jeden Zustand und jede Eingabe ist eindeutig festgelegt, wohin der Automat als nächstes wechselt. Das bedeutet, es darf keine mehrfachen Pfeile mit gleicher Beschriftung oder leere Übergänge geben.
Ein DEA besteht aus einem 5-Tupel: endliche Menge an Zuständen, Eingabealphabet, totale Überführungsfunktion, Anfangszustand und endliche Menge an Endzuständen. Diese Struktur macht den Automaten vorhersagbar und eindeutig.
Mealy-Automaten erweitern das Konzept um Ausgaben. Hier wird jedem Übergang nicht nur eine Eingabe, sondern auch eine Ausgabe zugeordnet . Der Automat benötigt dabei keinen Endzustand, da er kontinuierlich Ausgaben produziert.
Wichtig: Endliche Automaten haben klare Grenzen - sie können keine beliebig große Datenmenge speichern oder bereits erfolgte Ein-/Ausgaben merken. Probleme wie das Erkennen korrekt geschachtelter Klammern sind damit nicht lösbar.
2
of 2
Kellerautomaten und formale Grammatiken
Kellerautomaten lösen die Beschränkungen endlicher Automaten durch einen zusätzlichen Stapelspeicher nach dem LIFO-Prinzip (Last In, First Out). Sie können jetzt Informationen zwischenspeichern und später wieder abrufen - perfekt für Probleme wie geschachtelte Klammern oder Wörter der Form a^n b^n.
Der Kellerspeicher arbeitet mit drei Operationen: push(x) legt ein Zeichen ab, pop() entfernt das oberste Zeichen, und nop() verändert nichts. Das Startsymbol # zeigt an, wann der Speicher leer ist. Diese Erweiterung macht aus dem 5-Tupel ein 7-Tupel.
Formale Grammatiken erzeugen Sprachen durch Ersetzungsregeln. Eine Grammatik G besteht aus Nichtterminalen (Platzhalter), Terminalen (echte Buchstaben), einem Startsymbol und Produktionsregeln. So entstehen alle gültigen Wörter einer Sprache systematisch.
Merktipp: Kellerautomaten können zählen und vergleichen - sie merken sich die Anzahl der a's und prüfen, ob genauso viele b's folgen. Das macht sie viel mächtiger als einfache endliche Automaten.
We thought you’d never ask...
What is the Knowunity AI companion?
Our AI companion is specifically built for the needs of students. Based on the millions of content pieces we have on the platform we can provide truly meaningful and relevant answers to students. But its not only about answers, the companion is even more about guiding students through their daily learning challenges, with personalised study plans, quizzes or content pieces in the chat and 100% personalisation based on the students skills and developments.
Where can I download the Knowunity app?
You can download the app in the Google Play Store and in the Apple App Store.
Is Knowunity really free of charge?
That's right! Enjoy free access to study content, connect with fellow students, and get instant help – all at your fingertips.
Similar Content
Most popular content: Endliche Automaten
5InformatikInformatik Abitur 2024: Themenübersicht
Umfassende Themenübersicht für das Abitur 2024 im Fach Informatik. Dieser Lernzettel deckt wichtige Konzepte wie Programmierung in Java, Algorithmen, Datenstrukturen, Datenbanken, Cybersecurity und Verschlüsselungsmethoden ab. Ideal für Schüler, die sich auf das erhöhte Anforderungsniveau vorbereiten. Enthält auch Informationen zu relationalen Datenbanken, SQL-Abfragen und kryptologischen Verfahren.
132,84958
InformatikInformatik Abitur 2022: Schlüsselkonzepte
Dieser Lernzettel bietet eine umfassende Übersicht über zentrale Themen für das Informatik-Abitur 2022, einschließlich Algorithmen, Datenstrukturen, Kryptologie, Datenbanken und Netzwerktechnologien. Ideal für die Prüfungsvorbereitung im Leistungskurs Informatik.
1310,778242
InformatikFormale Sprachen und Automaten
Entdecken Sie die Grundlagen formaler Sprachen, einschließlich endlicher Automaten (DEA, NEA), der Chomsky-Hierarchie und der Anwendung von regulären Ausdrücken. Diese Zusammenfassung bietet einen klaren Überblick über Grammatik, Syntaxdiagramme und die Umwandlung zwischen verschiedenen Automatentypen. Ideal für Informatikstudenten im Grundkurs.
121,13321
InformatikEndliche Automaten und Grammatik
Erforschen Sie die Konzepte der deterministischen (DEA) und nicht deterministischen endlichen Automaten (NEA) sowie die Grundlagen der formalen Grammatik. Diese Zusammenfassung bietet eine klare Erklärung der 5-Tupel-Struktur, Übergangsrelationen und akzeptierten Wörter. Ideal für Studierende der Informatik, die sich auf formale Sprachen und Automatentheorie vorbereiten.
111,34540
InformatikEndliche Automaten: DEA & NEA
Erforschen Sie die Grundlagen der endlichen Automaten, einschließlich deterministischer (DEA) und nichtdeterministischer (NEA) Automaten. Lernen Sie die Minimierung von DEA, die Potenzmengenkonstruktion und die Unterschiede zwischen Moore- und Mealy-Automaten. Ideal für Studierende der Informatik und Mathematik. Typ: Zusammenfassung.
1194024
Most popular content in Informatik
9InformatikInformatik GK Lernzettel Abitur 2025
- selbstständig erstellter Lernzettel
1278317
Q
InformatikQuiz für die Komponenten des Pc's💻
💻Hier lernst ind testest du dein wissen über die Pc Komponenten⌨️
65894
InformatikInformatik Abitur 2024: Themenübersicht
Umfassende Themenübersicht für das Abitur 2024 im Fach Informatik. Dieser Lernzettel deckt wichtige Konzepte wie Programmierung in Java, Algorithmen, Datenstrukturen, Datenbanken, Cybersecurity und Verschlüsselungsmethoden ab. Ideal für Schüler, die sich auf das erhöhte Anforderungsniveau vorbereiten. Enthält auch Informationen zu relationalen Datenbanken, SQL-Abfragen und kryptologischen Verfahren.
132,84958
C
InformatikComputer
Lerne alles über Computer und ihre Funktionsweise mit diesen fesselnden Flashcards. Perfekt für Schüler der 5. Klasse, die Computer Science entdecken möchten.
55360
InformatikInformatik Abitur 2024: Datenstrukturen & Datenbanken
Umfassender Lernzettel für das Informatik-Abitur 2024, der sich auf lineare Datenstrukturen, relationale Datenbanken, SQL-Abfragen und Automaten konzentriert. Ideal zur Vorbereitung auf Prüfungen mit Schwerpunkten auf Sortieralgorithmen, Datenbankmodellierung und Java-Programmierung.
112,52447
InformatikInformatik Abitur 2025 NRW
Informatik Übersicht zu den Themen die im mündlichen Abitur drankommen. Ist also vielleicht nicht zu 100% vollständig.
124599
InformatikWENN und SVERWEIS
Erklärung sverweis und wenn Funktion bei exel
116233
InformatikPython Lernzettel Informatik
Python Lernzettel (mathematische Operatoren, Variablen, Datentypen, Skripte, Boolesche Operatoren)
118718
InformatikInformatik Grundlagen: Datenstrukturen & Algorithmen
Dieser Lernzettel bietet eine umfassende Übersicht über grundlegende Konzepte der Informatik, einschließlich Objekte und Klassen, lineare und nicht-lineare Datenstrukturen, Sortier- und Suchalgorithmen, Bäume, Struktogramme, relationale Datenbanken, SQL-Abfragen, formale Sprachen und Automaten sowie Netzwerktopologien. Ideal für die Vorbereitung auf das Abitur in NRW.
131,40031
Most popular content
9
DeutschDer zerbrochene Krug
Szenenzusammenfassunfen, Figurenkonstellationen, Aufbau des Stücks, Sprache und Stilbesonderheiten, Aussageabsicht, Thematik, Interpretation
1148,034728
DeutschDer zerbrochene Krug von Heinrich von Kleist
Hier steht so ziemlich alles drinnen von Zusammenfassungen der einzelnen Auftritte bis hin zu den einzelnen Perosn und noch einiges mehr
1254,772921
DeutschDer zerbrochne Krug
Ausführliche Lernzettel zu: Basisdaten, Handlung, ausführliche Zusammenfassungen der Auftritte, zentrale Themen, Symbolische Bedeutung, Merkmale der Komödie
1214,330253
DeutschHeimsuchung_JennyErpenbeck_Abitur
Zusammenfassungen für jedes Kapitel, Analysen und Zitate
1314,076277
MatheZP10 Mathe Zusammenfassung NRW
Lernzettel für die ZP10 Mathe in NRW mit allen Themen außer Sinusfunktionen.
1061,9114,842
DeutschDer zerbrochene Krug: Analyse
Diese umfassende Analyse von 'Der zerbrochene Krug' von Heinrich von Kleist bietet eine detaillierte Kapitelzusammenfassung, Charakterisierungen, historische Kontexte, sowie den Aufbau und die sprachlichen Merkmale des Dramas. Ideal für Studierende, die sich auf Prüfungen vorbereiten oder tiefere Einblicke in Kleists Werk gewinnen möchten.
1199,8391,255
EnglischEnglisch LK Abitur 2025
Komplette Englisch LK Abi Zusammenfassung 2025
1315,040394
DeutschSchreibkompetenzen Deutsch LK
Diese umfassende Zusammenstellung bereitet auf das Abitur 2024 vor und deckt alle relevanten Schreibkompetenzen ab: von der Analyse pragmatischer Texte über die Erörterung literarischer Werke bis hin zur Interpretation von Epik, Lyrik und Dramatik. Zudem werden Techniken des materialgestützten Schreibens, der Redeanalyse sowie journalistische Textsorten und rhetorische Mittel behandelt. Ideal für eine gezielte und effektive Prüfungsvorbereitung.
138,207165
DeutschJenny Erpenbeck "Heimsuchung"
Übersicht und Struktur des Romans
117,998168
Can't find what you're looking for? Explore other subjects.
Students love us — and so will you.
4.6/5App Store
4.7/5Google Play
The app is very easy to use and well designed. I have found everything I was looking for so far and have been able to learn a lot from the presentations! I will definitely use the app for a class assignment! And of course it also helps a lot as an inspiration.
Stefan SiOS user
This app is really great. There are so many study notes and help [...]. My problem subject is French, for example, and the app has so many options for help. Thanks to this app, I have improved my French. I would recommend it to anyone.
Samantha KlichAndroid user
Wow, I am really amazed. I just tried the app because I've seen it advertised many times and was absolutely stunned. This app is THE HELP you want for school and above all, it offers so many things, such as workouts and fact sheets, which have been VERY helpful to me personally.
AnnaiOS user
Informatik2,680 views·Updated Jun 25, 2026·2 pagesAutomaten und Grammatiken - Informatik Abi 2022 Zusammenfassung
Jule@jule156
Automaten und Grammatiken sind grundlegende Konzepte der theoretischen Informatik, die zeigen, wie Computer Sprachen und Muster erkennen können. Du lernst hier verschiedene Automatentypen kennen - von einfachen endlichen Automaten bis zu erweiterten Kellerautomaten - und verstehst, wie formale Grammatiken Sprachen...
1
of 2
Sign up to see the content. It's free!
- Access to all documents
- Improve your grades
- Join milions of students
Endliche Automaten und Mealy-Automaten
Deterministische endliche Automaten (DEA) funktionieren nach einem klaren Prinzip: Für jeden Zustand und jede Eingabe ist eindeutig festgelegt, wohin der Automat als nächstes wechselt. Das bedeutet, es darf keine mehrfachen Pfeile mit gleicher Beschriftung oder leere Übergänge geben.
Ein DEA besteht aus einem 5-Tupel: endliche Menge an Zuständen, Eingabealphabet, totale Überführungsfunktion, Anfangszustand und endliche Menge an Endzuständen. Diese Struktur macht den Automaten vorhersagbar und eindeutig.
Mealy-Automaten erweitern das Konzept um Ausgaben. Hier wird jedem Übergang nicht nur eine Eingabe, sondern auch eine Ausgabe zugeordnet . Der Automat benötigt dabei keinen Endzustand, da er kontinuierlich Ausgaben produziert.
Wichtig: Endliche Automaten haben klare Grenzen - sie können keine beliebig große Datenmenge speichern oder bereits erfolgte Ein-/Ausgaben merken. Probleme wie das Erkennen korrekt geschachtelter Klammern sind damit nicht lösbar.
2
of 2Sign up to see the content. It's free!
- Access to all documents
- Improve your grades
- Join milions of students
Kellerautomaten und formale Grammatiken
Kellerautomaten lösen die Beschränkungen endlicher Automaten durch einen zusätzlichen Stapelspeicher nach dem LIFO-Prinzip (Last In, First Out). Sie können jetzt Informationen zwischenspeichern und später wieder abrufen - perfekt für Probleme wie geschachtelte Klammern oder Wörter der Form a^n b^n.
Der Kellerspeicher arbeitet mit drei Operationen: push(x) legt ein Zeichen ab, pop() entfernt das oberste Zeichen, und nop() verändert nichts. Das Startsymbol # zeigt an, wann der Speicher leer ist. Diese Erweiterung macht aus dem 5-Tupel ein 7-Tupel.
Formale Grammatiken erzeugen Sprachen durch Ersetzungsregeln. Eine Grammatik G besteht aus Nichtterminalen (Platzhalter), Terminalen (echte Buchstaben), einem Startsymbol und Produktionsregeln. So entstehen alle gültigen Wörter einer Sprache systematisch.
Merktipp: Kellerautomaten können zählen und vergleichen - sie merken sich die Anzahl der a's und prüfen, ob genauso viele b's folgen. Das macht sie viel mächtiger als einfache endliche Automaten.
We thought you’d never ask...
What is the Knowunity AI companion?
Our AI companion is specifically built for the needs of students. Based on the millions of content pieces we have on the platform we can provide truly meaningful and relevant answers to students. But its not only about answers, the companion is even more about guiding students through their daily learning challenges, with personalised study plans, quizzes or content pieces in the chat and 100% personalisation based on the students skills and developments.
Where can I download the Knowunity app?
You can download the app in the Google Play Store and in the Apple App Store.
Is Knowunity really free of charge?
That's right! Enjoy free access to study content, connect with fellow students, and get instant help – all at your fingertips.
Similar Content
Most popular content: Endliche Automaten
5InformatikInformatik Abitur 2024: Themenübersicht
Umfassende Themenübersicht für das Abitur 2024 im Fach Informatik. Dieser Lernzettel deckt wichtige Konzepte wie Programmierung in Java, Algorithmen, Datenstrukturen, Datenbanken, Cybersecurity und Verschlüsselungsmethoden ab. Ideal für Schüler, die sich auf das erhöhte Anforderungsniveau vorbereiten. Enthält auch Informationen zu relationalen Datenbanken, SQL-Abfragen und kryptologischen Verfahren.
132,84958
InformatikInformatik Abitur 2022: Schlüsselkonzepte
Dieser Lernzettel bietet eine umfassende Übersicht über zentrale Themen für das Informatik-Abitur 2022, einschließlich Algorithmen, Datenstrukturen, Kryptologie, Datenbanken und Netzwerktechnologien. Ideal für die Prüfungsvorbereitung im Leistungskurs Informatik.
1310,778242
InformatikFormale Sprachen und Automaten
Entdecken Sie die Grundlagen formaler Sprachen, einschließlich endlicher Automaten (DEA, NEA), der Chomsky-Hierarchie und der Anwendung von regulären Ausdrücken. Diese Zusammenfassung bietet einen klaren Überblick über Grammatik, Syntaxdiagramme und die Umwandlung zwischen verschiedenen Automatentypen. Ideal für Informatikstudenten im Grundkurs.
121,13321
InformatikEndliche Automaten und Grammatik
Erforschen Sie die Konzepte der deterministischen (DEA) und nicht deterministischen endlichen Automaten (NEA) sowie die Grundlagen der formalen Grammatik. Diese Zusammenfassung bietet eine klare Erklärung der 5-Tupel-Struktur, Übergangsrelationen und akzeptierten Wörter. Ideal für Studierende der Informatik, die sich auf formale Sprachen und Automatentheorie vorbereiten.
111,34540
InformatikEndliche Automaten: DEA & NEA
Erforschen Sie die Grundlagen der endlichen Automaten, einschließlich deterministischer (DEA) und nichtdeterministischer (NEA) Automaten. Lernen Sie die Minimierung von DEA, die Potenzmengenkonstruktion und die Unterschiede zwischen Moore- und Mealy-Automaten. Ideal für Studierende der Informatik und Mathematik. Typ: Zusammenfassung.
1194024
Most popular content in Informatik
9InformatikInformatik GK Lernzettel Abitur 2025
- selbstständig erstellter Lernzettel
1278317
Q
InformatikQuiz für die Komponenten des Pc's💻
💻Hier lernst ind testest du dein wissen über die Pc Komponenten⌨️
65894
InformatikInformatik Abitur 2024: Themenübersicht
Umfassende Themenübersicht für das Abitur 2024 im Fach Informatik. Dieser Lernzettel deckt wichtige Konzepte wie Programmierung in Java, Algorithmen, Datenstrukturen, Datenbanken, Cybersecurity und Verschlüsselungsmethoden ab. Ideal für Schüler, die sich auf das erhöhte Anforderungsniveau vorbereiten. Enthält auch Informationen zu relationalen Datenbanken, SQL-Abfragen und kryptologischen Verfahren.
132,84958
C
InformatikComputer
Lerne alles über Computer und ihre Funktionsweise mit diesen fesselnden Flashcards. Perfekt für Schüler der 5. Klasse, die Computer Science entdecken möchten.
55360
InformatikInformatik Abitur 2024: Datenstrukturen & Datenbanken
Umfassender Lernzettel für das Informatik-Abitur 2024, der sich auf lineare Datenstrukturen, relationale Datenbanken, SQL-Abfragen und Automaten konzentriert. Ideal zur Vorbereitung auf Prüfungen mit Schwerpunkten auf Sortieralgorithmen, Datenbankmodellierung und Java-Programmierung.
112,52447
InformatikInformatik Abitur 2025 NRW
Informatik Übersicht zu den Themen die im mündlichen Abitur drankommen. Ist also vielleicht nicht zu 100% vollständig.
124599
InformatikWENN und SVERWEIS
Erklärung sverweis und wenn Funktion bei exel
116233
InformatikPython Lernzettel Informatik
Python Lernzettel (mathematische Operatoren, Variablen, Datentypen, Skripte, Boolesche Operatoren)
118718
InformatikInformatik Grundlagen: Datenstrukturen & Algorithmen
Dieser Lernzettel bietet eine umfassende Übersicht über grundlegende Konzepte der Informatik, einschließlich Objekte und Klassen, lineare und nicht-lineare Datenstrukturen, Sortier- und Suchalgorithmen, Bäume, Struktogramme, relationale Datenbanken, SQL-Abfragen, formale Sprachen und Automaten sowie Netzwerktopologien. Ideal für die Vorbereitung auf das Abitur in NRW.
131,40031
Most popular content
9DeutschDer zerbrochene Krug
Szenenzusammenfassunfen, Figurenkonstellationen, Aufbau des Stücks, Sprache und Stilbesonderheiten, Aussageabsicht, Thematik, Interpretation
1148,034728
DeutschDer zerbrochene Krug von Heinrich von Kleist
Hier steht so ziemlich alles drinnen von Zusammenfassungen der einzelnen Auftritte bis hin zu den einzelnen Perosn und noch einiges mehr
1254,772921
DeutschDer zerbrochne Krug
Ausführliche Lernzettel zu: Basisdaten, Handlung, ausführliche Zusammenfassungen der Auftritte, zentrale Themen, Symbolische Bedeutung, Merkmale der Komödie
1214,330253
DeutschHeimsuchung_JennyErpenbeck_Abitur
Zusammenfassungen für jedes Kapitel, Analysen und Zitate
1314,076277
MatheZP10 Mathe Zusammenfassung NRW
Lernzettel für die ZP10 Mathe in NRW mit allen Themen außer Sinusfunktionen.
1061,9114,842
DeutschDer zerbrochene Krug: Analyse
Diese umfassende Analyse von 'Der zerbrochene Krug' von Heinrich von Kleist bietet eine detaillierte Kapitelzusammenfassung, Charakterisierungen, historische Kontexte, sowie den Aufbau und die sprachlichen Merkmale des Dramas. Ideal für Studierende, die sich auf Prüfungen vorbereiten oder tiefere Einblicke in Kleists Werk gewinnen möchten.
1199,8391,255
EnglischEnglisch LK Abitur 2025
Komplette Englisch LK Abi Zusammenfassung 2025
1315,040394
DeutschSchreibkompetenzen Deutsch LK
Diese umfassende Zusammenstellung bereitet auf das Abitur 2024 vor und deckt alle relevanten Schreibkompetenzen ab: von der Analyse pragmatischer Texte über die Erörterung literarischer Werke bis hin zur Interpretation von Epik, Lyrik und Dramatik. Zudem werden Techniken des materialgestützten Schreibens, der Redeanalyse sowie journalistische Textsorten und rhetorische Mittel behandelt. Ideal für eine gezielte und effektive Prüfungsvorbereitung.
138,207165
DeutschJenny Erpenbeck "Heimsuchung"
Übersicht und Struktur des Romans
117,998168
Can't find what you're looking for? Explore other subjects.
Students love us — and so will you.
4.6/5App Store
4.7/5Google Play
The app is very easy to use and well designed. I have found everything I was looking for so far and have been able to learn a lot from the presentations! I will definitely use the app for a class assignment! And of course it also helps a lot as an inspiration.
Stefan SiOS user
This app is really great. There are so many study notes and help [...]. My problem subject is French, for example, and the app has so many options for help. Thanks to this app, I have improved my French. I would recommend it to anyone.
Samantha KlichAndroid user
Wow, I am really amazed. I just tried the app because I've seen it advertised many times and was absolutely stunned. This app is THE HELP you want for school and above all, it offers so many things, such as workouts and fact sheets, which have been VERY helpful to me personally.
AnnaiOS user