Formale Sprachen und Automatentheorie: Online-Quiz für Informatik-Studenten

Question 1

Welche Aussage über reguläre Ausdrücke ist korrekt?

Accepted Answer

Reguläre Ausdrücke sind eine umfangreiche Sprache zur Zeichenfolgenbeschreibung.

Answer

Reguläre Ausdrücke dienen ausschließlich zum Suchen und Ersetzen von Text.

Answer

Reguläre Ausdrücke sind leicht zu erlernende und einfache Sprachen.

Answer

Reguläre Ausdrücke sind nur zum Parsen von HTML verwendbar.

Question 2

Welcher endliche Automat akzeptiert die Sprache aller Zeichenfolgen, die mit einem Kleinbuchstaben beginnen und mit einem Großbuchstaben enden?

Accepted Answer

![a-z][A-Z]

Answer

[A-Z][a-z]

Answer

![A-Za-z]

Answer

[A-Za-z]

Question 3

Welcher Pushdown-Automat akzeptiert die Sprache aller Zeichenfolgen mit ausgeglichener Anzahl von Klammern?

Accepted Answer

PDA mit Stapelsymbolen { (, ) }, Übergängen { ( -> ((), ) -> (), ε -> ε} und Startzustand q0

Answer

PDA mit Stapelsymbolen { (, ) }, Übergängen { ( -> (), ) -> ((), ε -> ε} und Startzustand q0

Answer

PDA mit Stapelsymbolen { (, ) }, Übergängen { ( -> (), ) -> (), ε -> ε} und Startzustand q0

Question 4

Welche Aussage über Pushdown-Automaten ist korrekt?

Accepted Answer

Pushdown-Automaten sind in zahlreichen Anwendungen von Bedeutung.

Answer

Pushdown-Automaten sind weniger leistungsfähig als endliche Automaten.

Answer

Pushdown-Automaten dienen ausschließlich dem Parsen kontextfreier Grammatiken.

Answer

Pushdown-Automaten sind einfach zu konstruieren und zu analysieren.

Question 5

Welcher reguläre Ausdruck beschreibt die Menge aller Zeichenfolgen aus beliebig vielen Ziffern?

Accepted Answer

^[0-9]*$

Answer

^d$

Answer

^[0-9]+$

Answer

^\d+$

Question 6

Welcher endliche Automat akzeptiert die Sprache aller Zeichenfolgen, die mit einem beliebigen Zeichen beginnen und mit einem beliebigen Zeichen enden?

Accepted Answer

[A-Za-z]

Answer

![a-z][a-z]

Answer

[a-z][a-z]

Answer

![A-Za-z]

Question 7

Welche Aussage über formale Sprachen ist korrekt?

Accepted Answer

Formale Sprachen finden breite Anwendung in der Informatik.

Answer

Formale Sprachen sind abstrakte Repräsentationen natürlicher Sprachen.

Answer

Formale Sprachen sind stets endlich.

Answer

Formale Sprachen sind nur für theoretische Zwecke relevant.

Question 8

Was versteht man unter einer regulären Sprache?

Accepted Answer

Eine Sprache, die durch einen regulären Ausdruck beschrieben werden kann

Answer

Eine Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann

Answer

Eine Sprache, die durch eine rekursive Grammatik beschrieben werden kann

Answer

Eine Sprache, die durch eine deterministische Grammatik beschrieben werden kann

Question 9

Was bedeutet ein EPSILON-Übergang in einem nichtdeterministischen endlichen Automaten?

Accepted Answer

Ein Übergang, der keine Eingabe erfordert.

Answer

Ein Übergang, der in jeden Zustand führen kann.

Answer

Ein Übergang, der nur in den Anfangszustand führt.

Answer

Ein Übergang, der nur in den Endzustand führt.

Question 10

Welche der folgenden Aussagen über Turingmaschinen ist falsch?

Accepted Answer

Sie können nur deterministisch sein.

Answer

Sie können jede berechenbare Funktion berechnen.

Answer

Sie haben ein unbegrenztes Band.

Answer

Sie können als Modell für einen Computer verwendet werden.

Question 11

Welche Funktion erfüllt ein Kontextstapel in einem Pushdown-Automaten?

Accepted Answer

Speichern des Verlaufs der besuchten Zustände

Answer

Speichern der verarbeiteten Eingabe

Answer

Speichern der verbleibenden Eingabe

Answer

Speichern der erzeugten Ausgabe

Question 12

Welcher Automatentyp ist am besten geeignet, die Sprache {a^n | n>=0} zu akzeptieren?

Accepted Answer

Endlicher Automat (FA)

Answer

Pushdown-Automat (PDA)

Answer

Turing-Maschine (TM)

Answer

Keiner der genannten

Question 13

Welche Operation auf formalen Sprachen ist assoziativ?

Accepted Answer

Vereinigung (U)

Answer

Verkettung (.)

Answer

Kleene-Stern (*)

Answer

Komplement (-)

Question 14

Welche der folgenden Sätze ist eine Chomsky-Normalform für die Sprache {a^n b^n | n>=0}?

Accepted Answer

S -> aSb | ε

Answer

S -> ab | aS | bS | ε

Answer

S -> a | b | aSb | ε

Answer

S -> aS | bS | ε

Question 15

Welcher Algorithmus kann verwendet werden, um zu prüfen, ob ein Wort zu einer kontextfreien Sprache gehört?

Accepted Answer

CYK-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Question 16

Welcher der folgenden regulären Ausdrücke beschreibt die Sprache aller Zeichenfolgen, die mit "a" beginnen, mit "b" enden und keine anderen Zeichen enthalten?

Accepted Answer

ab

Answer

a.*b

Answer

a+b*

Answer

(ab)*

Question 17

Welcher der folgenden endlichen Automaten akzeptiert die Sprache aller Zeichenfolgen, die eine ungerade Anzahl von Einsen enthalten, während die Anzahl der Nullen beliebig sein darf?

Accepted Answer

Ein endlicher Automat mit drei Zuständen

Answer

Ein endlicher Automat mit zwei Zuständen

Answer

Ein Pushdown-Automat mit zwei Stapelsymbolen

Answer

Ein Turing-Maschine mit einem Band

Question 18

Welche Eigenschaft ist charakteristisch für einen Pushdown-Automaten?

Accepted Answer

Er verfügt über einen Stapelspeicher für die Zwischenspeicherung von Symbolen

Answer

Er kann nur endlich viele Zustände haben

Answer

Er kann nur Symbole lesen, aber nicht schreiben

Answer

Er kann unendlich viele Zeichenfolgen akzeptieren

Question 19

Welche der folgenden Aussagen über endliche Automaten ist korrekt?

Accepted Answer

Sie können sowohl deterministisch als auch nichtdeterministisch sein

Answer

Sie können ausschließlich deterministisch sein

Answer

Sie können ausschließlich nichtdeterministisch sein

Answer

Sie können nur reguläre Sprachen akzeptieren

Question 20

Was ist ein endlicher Automat?

Accepted Answer

Ein mathematisches Modell für eine Maschine mit einer begrenzten Anzahl an Zuständen.

Answer

Ein Programm für die Ausführung einer bestimmten Aufgabe.

Answer

Ein Datentyp zum Speichern von Zeichenfolgen.

Answer

Ein Algorithmus zum Aufspüren von Mustern in Zeichenfolgen.

Question 21

Welche Sprache wird durch den regulären Ausdruck '(a|b)*' beschrieben?

Accepted Answer

Alle Zeichenfolgen, die nur aus den Zeichen 'a' und 'b' aufgebaut sind

Answer

Die leere Zeichenfolge

Answer

Alle Zeichenfolgen mit einer geraden Anzahl an Zeichen

Answer

Alle Zeichenfolgen, die mit 'a' beginnen

Question 22

Was versteht man unter einem Pushdown-Automaten?

Accepted Answer

Ein endlicher Automat mit einem Stapelspeicher.

Answer

Ein Programm mit der Möglichkeit rekursiver Aufrufe.

Answer

Ein Datentyp zum Speichern hierarchischer Datenstrukturen.

Answer

Ein Algorithmus zum Generieren aller möglichen Zeichenfolgen einer Sprache.

Question 23

Was ist der wesentliche Unterschied zwischen einem regulären Ausdruck und einer kontextfreien Grammatik?

Accepted Answer

Reguläre Ausdrücke können keine rekursiven Regeln beschreiben.

Answer

Kontextfreie Grammatiken können keine unendlichen Sprachen beschreiben.

Answer

Reguläre Ausdrücke sind ausschließlich zur Beschreibung deterministischer Automaten geeignet.

Answer

Kontextfreie Grammatiken sind ausschließlich zur Beschreibung nichtdeterministischer Automaten geeignet.

Question 24

Wie hängen formale Sprachen und Grammatiken zusammen?

Accepted Answer

Formale Sprachen sind Sammlungen von Zeichenfolgen, während Grammatiken Regeln liefern, um diese Zeichenfolgen zu bilden.

Answer

Grammatiken sind formale Sprachen, die andere formale Sprachen beschreiben.

Answer

Formale Sprachen und Grammatiken sind nicht miteinander verbunden.

Question 25

Welcher der folgenden regulären Ausdrücke beschreibt die Sprache aller Zeichenfolgen, die mit einem Kleinbuchstaben beginnen?

Accepted Answer

^[a-z](.*)$

Answer

^(a)(.*)$

Answer

^([A-Za-z])(.*)$

Answer

^(A)(.*)$

Question 26

Welche der folgenden Aussagen beschreibt korrekt die Akzeptanzfähigkeit endlicher Automaten (EA) und Pushdown-Automaten (PDA)?

Accepted Answer

PDA können alle Sprachen akzeptieren, die EA akzeptieren können.

Accepted Answer

EA akzeptieren nur Sprachen, die durch reguläre Ausdrücke beschrieben werden.

Accepted Answer

PDA akzeptieren nur Sprachen, die durch kontextfreie Grammatiken beschrieben werden.

Answer

EA können alle Sprachen akzeptieren, die PDA akzeptieren können.

Question 27

Welcher reguläre Ausdruck beschreibt die Sprache aller Zeichenketten, die mit 'a' beginnen und mit 'b' enden?

Accepted Answer

^a(a|b)*(b)$

Answer

^(a)(b)$

Answer

^(a)(ab)*(b)$

Answer

^(a)*(b)$

Question 28

Welche der folgenden Aussagen über formale Sprachen ist falsch?

Accepted Answer

Jede formale Sprache hat einen endlichen Automaten, der sie akzeptiert.

Answer

Formale Sprachen können unendlich sein.

Answer

Formale Sprachen können durch Grammatiken definiert werden.

Question 29

Was ist das Ziel der Automatentheorie?

Accepted Answer

Formalisierung und Analyse des Rechnens

Answer

Entwicklung neuer Programmiersprachen

Answer

Optimierung von Datenbanken

Answer

Entwurf von künstlicher Intelligenz

Question 30

Welches Theorem ist grundlegend für die Automatentheorie?

Accepted Answer

Pumping-Lemma für reguläre Sprachen

Answer

Satz von Cayley-Hamilton

Answer

Satz von Fermat

Answer

Satz von Turing

Question 31

Welches Problem kann zur Charakterisierung kontextfreier Sprachen verwendet werden?

Accepted Answer

Erkennungsproblem

Answer

P-NP-Problem

Answer

Halteproblem

Answer

Entscheidungsproblem

Question 32

Was ist der Vorteil von Pushdown-Automaten gegenüber endlichen Automaten?

Accepted Answer

Sie können Sprachen mit beliebiger geschachtelter Struktur erkennen.

Answer

Sie sind effizienter in der Verarbeitung.

Answer

Sie können Fehler besser handhaben.

Question 33

Welche der folgenden Sprachen ist **nicht** kontextfrei?

Accepted Answer

{a^n b^m c^k | n, m, k ≥ 1 und n ≠ m}

Answer

{a^n b^m c^m | n, m ≥ 1}

Answer

{a^n b^n | n ≥ 1}

Answer

{a^n b^m c^k | n, m, k ≥ 1}

Question 34

Was ist die Chomsky-Normalform für eine kontextfreien Grammatik?

Accepted Answer

Eine Grammatik, bei der jede Produktionsregel entweder die Form A -> BC oder A -> a hat, wobei A, B und C Nichtterminale sind und a ein Terminal ist.

Answer

Eine Grammatik, bei der jede Produktionsregel die Form A -> aBC hat, wobei A, B und C Nichtterminale sind und a ein Terminal ist.

Question 35

Welcher der folgenden Sätze ist **wahr** für Pushdown-Automaten?

Accepted Answer

Sie können verschachtelte Strukturen akzeptieren.

Answer

Sie können nur reguläre Sprachen akzeptieren.

Answer

Sie sind äquivalent zu Turingmaschinen.

Answer

Sie können keine Sprachen mit rekursiven Strukturen akzeptieren.

Question 36

Was ist das Pumping-Lemma für reguläre Sprachen?

Accepted Answer

Wenn eine Sprache regulär ist, dann existiert eine ganze Zahl n, so dass jedes Wort der Sprache mit einer Länge größer als n in kleinere Wörter zerlegt werden kann, die bestimmten Bedingungen genügen.

Answer

Wenn eine Sprache regulär ist, dann existiert eine endliche Menge von Wörtern, die alle Wörter der Sprache erzeugen.

Question 37

Was ist eine Turingmaschine?

Accepted Answer

Ein mathematisches Modell eines Rechners, das aus einem unendlichen Band, einem Lese-/Schreibkopf und einem endlichen Satz von Befehlen besteht.

Answer

Ein physischer Computer, der für praktische Anwendungen verwendet wird.

Question 38

Welche der folgenden Aussagen über Turingmaschinen ist korrekt?

Accepted Answer

Sie sind universell, das heißt, sie können jeden Algorithmus simulieren.

Answer

Sie sind praktisch für den Einsatz in realen Anwendungen.

Answer

Sie können nur deterministische Probleme lösen.

Question 39

Welche der folgenden Sprachen wird durch den regulären Ausdruck (a|b)* beschrieben?

Accepted Answer

Die Menge aller Wörter über dem Alphabet {a, b}.

Answer

Die Menge aller Wörter, die mit 'a' beginnen.

Answer

Die Menge aller Wörter, die mit 'b' enden.

Answer

Die Menge aller Wörter mit gerader Länge.

Question 40

Welcher endliche Automat erkennt die Sprache {w | w ∈ {0, 1}*, w enthält eine gerade Anzahl von 0en}?

Accepted Answer

Ein Zustandsdiagramm mit zwei Zuständen: einem Anfangszustand und einem Akzeptanzzustand.

Answer

Ein Zustandsdiagramm mit einem Zustand.

Answer

Ein Zustandsdiagramm mit drei Zuständen.

Question 41

Welche der folgenden Aussagen ist falsch?

Accepted Answer

Ein endlicher Automat kann jede Sprache erkennen.

Answer

Eine Turingmaschine kann jede berechenbare Sprache erkennen.

Answer

Ein Pushdown-Automat kann jede kontextfreie Sprache erkennen.

Question 42

Welche Menge von Sprachen wird durch reguläre Ausdrücke definiert?

Accepted Answer

Reguläre Sprachen.

Answer

Kontextfreie Sprachen.

Answer

Rekursiv aufzählbare Sprachen.

Answer

Kontextsensitive Sprachen.

Question 43

Welcher Automatentyp ist der schwächste?

Accepted Answer

Endlicher Automat.

Answer

Pushdown-Automat.

Answer

Turingmaschine.

Answer

Linear beschränkter Automat.

Question 44

Welche der folgenden Aussagen über Turing-Maschinen ist nicht korrekt?

Accepted Answer

Eine Turing-Maschine kann niemals anhalten.

Answer

Eine Turing-Maschine verwendet ein unendliches Band.

Answer

Eine Turing-Maschine hat einen Lese-/Schreibkopf.

Answer

Eine Turing-Maschine kann alle berechenbaren Funktionen berechnen.

Question 45

Welche Aussage über reguläre Ausdrücke ist **korrekt**?

Accepted Answer

Sie beschreiben eine Menge von Zeichenfolgen.

Answer

Sie sind äquivalent zu kontextfreien Grammatiken.

Answer

Sie können nur deterministische Automaten beschreiben.

Answer

Sie sind generalisiert Turing-vollständig.

Question 46

Welcher Automatentyp **kann nicht** nicht-deterministische Übergänge aufweisen?

Accepted Answer

Deterministischer endlicher Automat (DFA)

Answer

Pushdown-Automat (PDA)

Answer

Turingmaschine

Answer

Nicht-deterministischer endlicher Automat (NFA)

Question 47

Welche Sprache **kann** von einem DFA akzeptiert werden?

Accepted Answer

Alle endlichen Sprachen

Answer

Alle kontextfreien Sprachen

Answer

Alle rekursiven Sprachen

Answer

Alle nicht-regulären Sprachen

Question 48

Was ist das Pumping-Lemma für reguläre Sprachen?

Accepted Answer

Für jede reguläre Sprache existiert eine Konstante k, so dass jede Zeichenfolge in der Sprache, die länger als k ist, in kleinere Teile zerlegt werden kann, die sich wiederholen.

Answer

Für jede kontextfreie Sprache existiert eine Konstante k, so dass jede Zeichenfolge in der Sprache, die länger als k ist, in kleinere Teile zerlegt werden kann, die sich wiederholen.

Question 49

Welche Sprache **kann** von einem PDA akzeptiert werden?

Accepted Answer

Alle kontextfreien Sprachen

Answer

Alle nicht-kontextfreien Sprachen

Answer

Alle regulären Sprachen

Answer

Alle rekursiven Sprachen

Question 50

Was besagt die Church-Turing-These?

Accepted Answer

Jedes intuitiv berechenbare Problem kann von einer Turingmaschine gelöst werden.

Answer

Nur rekursive Probleme können von einer Turingmaschine gelöst werden.

Answer

Jedes Problem, das von einer Turingmaschine gelöst werden kann, ist intuitiv berechenbar.

Question 51

Welche Eigenschaft trifft auf Turingmaschinen **zu**?

Accepted Answer

Sie sind universell, d.h. sie können jede andere Maschine simulieren.

Answer

Sie sind deterministisch.

Answer

Sie haben eine begrenzte Speicherkapazität.

Question 52

Welche Sprache ist **nicht** rekursiv?

Accepted Answer

Die Halteproblemsprache

Answer

Die Sprache der Primzahlen

Answer

Die Sprache der Palindrome

Question 53

Welcher der folgenden Automaten ist ein deterministischer Pushdown-Automat?

Accepted Answer

Automat mit Stapel, Zuständen, Eingabeband und deterministischen Übergängen

Answer

Automat mit Zuständen, Eingabeband und nicht-deterministischen Übergängen

Answer

Automat mit nur Zuständen und Übergängen

Answer

Automat mit Eingabeband und Lesekopf

Question 54

Welche der folgenden Aussagen über Turingmaschinen ist korrekt?

Accepted Answer

Sie können alle berechenbaren Probleme lösen.

Answer

Sie benötigen unendlich viel Speicherplatz.

Answer

Sie haben eine endliche Anzahl von Zuständen.

Answer

Sie sind immer deterministisch.

Question 55

Welche der folgenden Aussagen über die Entscheidbarkeit ist falsch?

Accepted Answer

Das Halteproblem ist entscheidbar.

Answer

Das Wortproblem für Gruppen ist entscheidbar.

Answer

Die Turing-Maschinen- Äquivalenz ist unentscheidbar.

Answer

Das Post-Korrespondenz-Problem ist unentscheidbar.

Question 56

Welcher der folgenden Algorithmen wird verwendet, um reguläre Ausdrücke zu parsen?

Accepted Answer

Thompson-Konstruktionsalgorithmus

Answer

A*-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Answer

Dijkstra-Algorithmus

Question 57

Welche der folgenden Mengen ist KEINE formale Sprache?

Accepted Answer

Menge der Primzahlen

Answer

Menge der regulären Ausdrücke

Answer

Menge der Kontextfreien Grammatiken

Answer

Menge der Chomsky-Typ-2-Grammatiken

Question 58

Welches Symbol in regulären Ausdrücken wird verwendet, um eine exklusive ODER-Verknüpfung darzustellen?

Accepted Answer

|

Answer

*

Answer

+

Answer

?

Question 59

Welches Problem ist nicht entscheidbar?

Accepted Answer

Halteproblem

Answer

Erreichbarkeitsproblem für endliche Automaten

Answer

Äquivalenzproblem für reguläre Ausdrücke

Answer

Leereheitsproblem für kontextfreie Grammatiken

Question 60

Welche der folgenden Aussagen trifft auf Turingmaschinen NICHT zu?

Accepted Answer

Sie sind deterministisch.

Answer

Sie sind universal.

Answer

Sie können alle berechenbaren Funktionen berechnen.

Answer

Sie haben ein unendliches Band.

Question 61

Welches Modell erweitert die Fähigkeiten endlicher Automaten?

Accepted Answer

Nichtdeterministischer endlicher Automat

Answer

Endlicher Automat mit Ausgabe

Answer

Mealy-Automat

Answer

Moore-Automat

Question 62

Konstruiere den regulären Ausdruck, der die Sprache aller Wörter beschreibt, die mit 'a' beginnen und mit 'b' enden.

Accepted Answer

a.*b

Answer

ab*

Answer

(a|b)*

Answer

a+b+

Question 63

Welche Aussage über Pushdown-Automaten ist zutreffend?

Accepted Answer

Pushdown-Automaten können Sprachen erkennen, die nicht durch endliche Automaten erkannt werden können.

Answer

Pushdown-Automaten können jede beliebige Sprache erkennen.

Answer

Pushdown-Automaten sind eine Unterklasse von endlichen Automaten.

Question 64

Was ist die Chomsky-Hierarchie?

Accepted Answer

Eine Klassifizierung von formalen Sprachen basierend auf ihrer Erzeugungskraft.

Answer

Eine Theorie, die beschreibt, wie natürliche Sprachen entstehen.

Answer

Ein Algorithmus zur Konstruktion von Automaten.

Answer

Eine Methode zur Analyse von Grammatiken.