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

Question 1

Was ist die korrekte Aussage über die Eigenschaften regulärer Ausdrücke?

Accepted Answer

Reguläre Ausdrücke sind eine formale Sprache zur Beschreibung von Mustern in Zeichenketten.

Answer

Reguläre Ausdrücke können nicht-deterministische Automaten nicht beschreiben.

Answer

Reguläre Ausdrücke umfassen alle kontextfreien Grammatiken.

Answer

Reguläre Ausdrücke können alle natürlichen Zahlen beschreiben.

Question 2

Welche der folgenden Maschinen ist die mächtigste?

Accepted Answer

Turingmaschine

Answer

Endlicher Automat

Answer

Pushdown-Automat

Answer

Kellerautomat

Question 3

Welche der folgenden Turingmaschinen erkennt die Sprache aller Zeichenketten, die mit einem a beginnen und mit einem b enden?

Accepted Answer

Eine Maschine, die den Eingabekopf nach rechts bewegt, nach a sucht und dann nach links bewegt, nach b sucht

Answer

Eine Maschine, die den Eingabekopf nach links bewegt, nach b sucht und dann nach rechts bewegt, nach a sucht

Answer

Eine Maschine, die den Eingabekopf auf das erste Zeichen setzt, prüft, ob es a ist, dann prüft, ob das letzte Zeichen b ist

Answer

Eine Maschine, die den Eingabekopf auf die Mitte der Zeichenkette setzt und prüft, ob beide äußeren Zeichen a bzw. b sind

Question 4

Welche der folgenden Maschinen entspricht der Definition einer Turingmaschine?

Accepted Answer

Eine Maschine mit einem unendlichen Band

Answer

Eine Maschine mit einem endlichen Zustandsspeicher

Answer

Eine Maschine mit mehreren Bändern

Answer

Eine Maschine mit einem Stack

Question 5

Welche der folgenden Aussagen beschreibt die durch den regulären Ausdruck (ab)*a generierte Sprache?

Accepted Answer

Alle Zeichenfolgen, die mit 'a' enden

Answer

Alle Zeichenfolgen, die mindestens ein 'a' enthalten

Answer

Alle Zeichenfolgen, die 'ab' enthalten

Answer

Alle Zeichenfolgen, die nur aus 'a' und 'b' bestehen

Question 6

Welche der folgenden Aussagen über kontextfreie Grammatiken ist korrekt?

Accepted Answer

Kontextfreie Grammatiken können alle regulären Sprachen erzeugen.

Answer

Kontextfreie Grammatiken können alle Sprachen erzeugen.

Answer

Kontextfreie Grammatiken können nur endliche Sprachen erzeugen.

Answer

Kontextfreie Grammatiken können nur unendliche Sprachen erzeugen.

Question 7

Welche der folgenden Sprachen ist nicht rekursiv aufzählbar?

Accepted Answer

Die Menge aller Turingmaschinen, die anhalten

Answer

Die Menge aller Primzahlen

Answer

Die Menge aller korrekt geklammerten Ausdrücke

Answer

Die Menge aller endlichen Zeichenfolgen

Question 8

Welche der folgenden Aussagen über Turingmaschinen ist falsch?

Accepted Answer

Turingmaschinen sind immer deterministisch.

Answer

Turingmaschinen können jede berechenbare Funktion berechnen.

Answer

Turingmaschinen sind universell.

Answer

Turingmaschinen können unendliche Eingaben verarbeiten.

Question 9

Welches der folgenden Beispiele ist eine reguläre Sprache?

Accepted Answer

{w | w enthält eine gerade Anzahl an Vorkommen des Buchstabens 'a'}

Answer

{w | w enthält die Zeichenfolge 'abba' genau einmal}

Answer

{w | w ist ein Palindrom}

Question 10

Welche der folgenden Sprachen ist nicht kontextfrei?

Accepted Answer

{w | w ist eine Primzahl}

Answer

{w | w ist ein Palindrom}

Answer

{w | w enthält eine gerade Anzahl an Vorkommen des Buchstabens 'a'}

Question 11

Was ist das Halteproblem?

Accepted Answer

Das Problem zu bestimmen, ob eine gegebene Turingmaschine bei einem gegebenen Eingabeband anhält

Answer

Das Problem zu bestimmen, ob eine gegebene Turingmaschine eine gegebene Sprache akzeptiert

Answer

Das Problem zu bestimmen, ob zwei gegebene Turingmaschinen äquivalent sind

Question 12

Welche der folgenden Eigenschaften trifft auf reguläre Ausdrücke zu?

Accepted Answer

Sie können zur Überprüfung von E-Mail-Adressen verwendet werden.

Answer

Sie können unendlich große Sprachen beschreiben.

Answer

Sie dürfen nur Großbuchstaben enthalten.

Answer

Sie können zur Darstellung von Bäumen verwendet werden.

Question 13

Welche der folgenden Maschinen ist eine Turingmaschine?

Accepted Answer

Eine Maschine mit unendlichem Band und Lese-/Schreibkopf

Answer

Eine Maschine mit endlichem Zustand

Answer

Eine Maschine mit Stapel

Answer

Eine Maschine mit deterministischem Verhalten

Question 14

Welche der folgenden Sprachen ist durch eine Turingmaschine nicht erkennbar?

Accepted Answer

{w | w ist eine Primzahl}

Answer

{w | w ist ein Palindrom}

Answer

{w | w enthält eine gerade Anzahl von a's}

Answer

{w | w ist eine gültige E-Mail-Adresse}

Question 15

Welche der folgenden Aussagen über das Halteproblem ist zutreffend?

Accepted Answer

Es ist für keine Turingmaschine lösbar.

Answer

Es ist für alle Turingmaschinen lösbar.

Answer

Es ist für einige Turingmaschinen lösbar.

Answer

Es ist nur für deterministische Turingmaschinen lösbar.

Question 16

Welche zentrale Bedeutung hat die Chomsky-Hierarchie für das Verständnis formaler Sprachen?

Accepted Answer

Sie klassifiziert Grammatiktypen nach ihrer Ausdrucksstärke.

Answer

Sie beschreibt die syntaktische Struktur natürlicher Sprachen.

Answer

Sie liefert Algorithmen zur effizienten Verarbeitung formaler Sprachen.

Answer

Sie bildet die Grundlage für die Entwicklung von Übersetzern und Compilern.

Question 17

Welche der folgenden Aussagen beschreibt reguläre Ausdrücke präzise?

Accepted Answer

Sie definieren Zeichenfolgen, die einem bestimmten Muster entsprechen.

Answer

Sie erkennen nur Zeichenfolgen, die mit einem bestimmten Zeichen starten.

Answer

Sie beschreiben Zeichenfolgen, die ein beliebiges Zeichen enthalten können.

Answer

Sie erkennen nur Zeichenfolgen, die mit einem bestimmten Zeichen enden.

Question 18

Welche der angegebenen Grammatiken ist explizit kontextfrei?

Accepted Answer

S -> aSb oder ε

Answer

S -> aS oder bS oder ε

Answer

S -> abS oder baS oder ε

Answer

S -> aaa oder bbb oder ε

Question 19

Welches der aufgeführten Probleme gilt als unlösbar?

Accepted Answer

Das Halteproblem

Answer

Das Primzahlproblem

Answer

Das Sortierproblem

Answer

Das Schachproblem

Question 20

Welche Maschinenklasse kann nicht-kontextfreie Sprachen erkennen?

Accepted Answer

Turingmaschinen

Answer

Endliche Automaten

Answer

Kellerautomaten

Answer

Linear beschränkte Automaten

Question 21

Welche der folgenden Aussagen beschreibt reguläre Ausdrücke korrekt?

Accepted Answer

Sie charakterisieren Sprachen, die von endlichen Automaten erkannt werden können.

Answer

Sie sind eine Obermenge der kontextfreien Grammatiken.

Answer

Sie beschreiben ausschließlich endliche Sprachen.

Answer

Sie können die Sprache {a^n b^n | n >= 0} nicht beschreiben.

Question 22

Welche der folgenden Turingmaschinen erkennt die Sprache {w | w enthält eine gerade Anzahl von a's}?

Accepted Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie an einer geraden Anzahl von a's vorbeikommt.

Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie an einer ungeraden Anzahl von a's vorbeikommt.

Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie an einer beliebigen Anzahl von a's vorbeikommt.

Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie an einer beliebigen Anzahl von b's vorbeikommt.

Question 23

Welche der folgenden Operationen auf formalen Sprachen ist nicht abgeschlossen?

Accepted Answer

Differenz

Answer

Vereinigung

Answer

Schnittmenge

Answer

Konkatenation

Question 24

Welche der folgenden Grammatiken erzeugt die Sprache {a^n b^n | n >= 0}?

Accepted Answer

S -> aSb | ε

Answer

S -> aS | bS | ε

Answer

S -> ab | ba

Answer

S -> a | b

Question 25

Welche der folgenden Turingmaschinen erkennt die Sprache {w | w enthält mindestens ein a}?

Accepted Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie ein a liest.

Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie ein b liest.

Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie ein beliebiges Zeichen liest.

Answer

Eine Maschine, die in den Zustand q_akzeptiert wechselt, wenn sie keine Zeichen liest.

Question 26

Welche der folgenden Aussagen über das Halteproblem ist korrekt?

Accepted Answer

Es ist unentscheidbar.

Answer

Es ist entscheidbar in polynomieller Zeit.

Answer

Es ist entscheidbar in exponentieller Zeit.

Answer

Es ist entscheidbar für alle Turingmaschinen.

Question 27

Welche Aussage über das Halteproblem ist korrekt?

Accepted Answer

Das Halteproblem ist unentscheidbar.

Answer

Das Halteproblem ist entscheidbar.

Answer

Das Halteproblem ist semi-entscheidbar.

Answer

Das Halteproblem ist NP-vollständig.

Question 28

Welche der folgenden Sprachen ist regulär?

Accepted Answer

{w | w enthält eine gerade Anzahl von '1'}

Answer

{w | w enthält mindestens zwei Vorkommen von '0'}

Answer

{w | w enthält ein Palindrom}

Answer

{w | w ist eine Primzahl}

Question 29

Welche der folgenden Maschinen kann alle rekursiv aufzählbaren Sprachen erkennen?

Accepted Answer

Turingmaschine

Answer

Endlicher Automat

Answer

Pushdown-Automat

Answer

Linear beschränkter Automat

Question 30

Was ist die PDLL-Eigenschaft?

Accepted Answer

Eine Sprache ist kontextfrei, wenn sie durch eine Grammatik generiert werden kann, die nur Produktionsregeln ohne Linksrekursion enthält.

Answer

Eine Sprache ist kontextfrei, wenn sie durch eine Grammatik generiert werden kann, die nur reguläre Ausdrücke enthält.

Answer

Eine Sprache ist kontextfrei, wenn sie durch einen endlichen Automaten erkannt werden kann.

Answer

Eine Sprache ist kontextfrei, wenn sie durch eine Turingmaschine berechnet werden kann.

Question 31

Was ist ein deterministischer endlicher Automat?

Accepted Answer

Ein Automat, der für jede Eingabe nur einen möglichen Übergang hat.

Answer

Ein Automat, der für jede Eingabe mehrere mögliche Übergänge hat.

Answer

Ein Automat, der mehrere Bänder hat.

Answer

Ein Automat, der unendlich viele Zustände hat.

Question 32

Was ist die Chomsky-Normalform?

Accepted Answer

Eine Form einer kontextfreien Grammatik, in der jede Produktionsregel entweder die Form A -> BC oder A -> a hat.

Answer

Eine Form einer regulären Grammatik, in der jede Produktionsregel die Form A -> a oder A -> AB hat.

Answer

Eine Form einer Turingmaschine, in der jeder Zustand nur einen möglichen Übergang hat.

Answer

Eine Form eines endlichen Automaten, in dem jeder Zustand nur einen möglichen Übergang hat.

Question 33

Welche der folgenden Sprachen passt zum regulären Ausdruck (a|b)*?

Accepted Answer

Alle Zeichenfolgen, die nur aus den Zeichen a und b bestehen

Answer

Alle Zeichenfolgen, die mit a beginnen und nur aus den Zeichen a und b bestehen

Answer

Alle Zeichenfolgen, die mit a enden und nur aus den Zeichen a und b bestehen

Answer

Alle Zeichenfolgen, die mindestens ein a enthalten

Question 34

Welche der folgenden Grammatiken erzeugt die Sprache aller Zeichenfolgen, die mit a beginnen und mit b enden?

Accepted Answer

S -> aSb | ε

Answer

S -> aS | b

Answer

S -> a | bS

Answer

S -> a | b

Question 35

Welches der folgenden Probleme kann von einer Turingmaschine nicht gelöst werden?

Accepted Answer

Das Halteproblem

Answer

Das Entscheidungsproblem für aussagenlogische Formeln

Answer

Das Schachproblem

Answer

Das Primzahlproblem

Question 36

Welches der folgenden Konzepte ist ein grundlegender Baustein formaler Sprachen?

Accepted Answer

Alphabet

Answer

Syntax

Answer

Semantik

Answer

Pragmatik

Question 37

Welches der folgenden Werke gilt als grundlegendes Werk der Informatiktheorie?

Accepted Answer

Von der berechenbaren Zahl

Answer

Die logischen Grundlagen der Mathematik

Answer

Die physikalischen Grundlagen der Quantenmechanik

Answer

Die Theorie der allgemeinen Relativität

Question 38

Welcher reguläre Ausdruck akzeptiert alle Zeichenfolgen, die mit 'a' beginnen?

Accepted Answer

a.*

Answer

a+

Answer

a$

Answer

.*a

Question 39

Welche der folgenden Grammatiken ist kontextfrei?

Accepted Answer

S → aSb | ε

Answer

S → aS | bSb

Answer

S → aS | bS

Answer

S → aaS | bbS

Question 40

Welche Aussage über Chomsky-Hierarchien ist falsch?

Accepted Answer

Rekursiv aufzählbare Sprachen sind eine Teilmenge der kontextsensitiven Sprachen.

Answer

Reguläre Sprachen sind eine Teilmenge der kontextfreien Sprachen.

Answer

Kontextfreie Sprachen sind eine Teilmenge der rekursiv aufzählbaren Sprachen.

Answer

Kontextsensitive Sprachen sind eine Teilmenge der Typ-0-Sprachen.

Question 41

Welches Lemma kann verwendet werden, um zu beweisen, dass eine Sprache nicht regulär ist?

Accepted Answer

Pumping-Lemma für reguläre Sprachen

Answer

Pumping-Lemma für kontextfreie Sprachen

Answer

Pumping-Lemma für rekursiv aufzählbare Sprachen

Answer

Pumping-Lemma für kontextsensitive Sprachen

Question 42

Welcher Automatentyp kann Nicht-Kontext-Freie-Sprachen akzeptieren?

Accepted Answer

Nicht-deterministischer Kellerautomat

Answer

Deterministischer endlicher Automat

Answer

Kellerautomat mit leerem Keller

Answer

Kellerautomat mit nicht leerem Keller

Question 43

Welche der folgenden Aussagen über Typ-0-Sprachen ist korrekt?

Accepted Answer

Sie sind genau die Sprachen, die von Turingmaschinen akzeptiert werden.

Answer

Sie sind genau die Sprachen, die von rekursiven Funktionen berechnet werden können.

Answer

Sie sind genau die Sprachen, die von kontextsensitiven Grammatiken erzeugt werden.

Answer

Sie sind genau die Sprachen, die von kontextfreien Grammatiken erzeugt werden.

Question 44

Welche der folgenden Aussagen über Turingmaschinen ist falsch?

Accepted Answer

Turingmaschinen sind immer terminierend.

Answer

Turingmaschinen haben ein unbegrenztes Band.

Answer

Turingmaschinen haben einen endlichen Satz von Zuständen.

Answer

Turingmaschinen können jede berechenbare Funktion berechnen.

Question 45

Welcher Automat akzeptiert die Sprache L = {w | w enthält die Zeichenfolge 'ab'}?

Accepted Answer

Nichtdeterministischer endlicher Automat

Answer

Pushdown-Automat

Answer

Deterministischer Kellerautomat

Question 46

Welche der folgenden Aussagen beschreibt eine reguläre Sprache präzise?

Accepted Answer

Eine Sprache, die durch einen endlichen Automaten erkannt werden kann oder äquivalent ist zu einem regulären Ausdruck.

Answer

Eine Sprache, die durch eine Turingmaschine entschieden werden kann.

Answer

Eine Sprache, die durch eine context-free Grammatik generiert werden kann.

Question 47

Welcher Automatentyp erkennt reguläre Sprachen?

Accepted Answer

Endlicher Automat (FA)

Answer

Pushdown-Automat (PDA)

Answer

Lineare beschränkte Turingmaschine (LBA)

Answer

Turingmaschine (TM)

Question 48

Welche der folgenden Grammatiken ist eine kontextfreie Grammatik?

Accepted Answer

Eine Grammatik, deren Ableitungsregeln die Form A -> α haben, wobei A ein Nichtterminalsymbol und α eine Folge von Symbolen (Terminalsymbole und Nichtterminalsymbole) ist.

Answer

Eine Grammatik, deren Ableitungsregeln die Form A -> ε haben, wobei ε die leere Zeichenfolge ist.

Answer

Eine Grammatik, deren Ableitungsregeln die Form A -> B haben, wobei A und B Nichtterminalsymbole sind.

Question 49

Welcher Automatentyp erkennt kontextfreie Sprachen?

Accepted Answer

Pushdown-Automat (PDA)

Answer

Lineare beschränkte Turingmaschine (LBA)

Answer

Turingmaschine (TM)

Answer

Endlicher Automat (FA)

Question 50

Welcher der folgenden Sätze über Sprachklassen ist korrekt?

Accepted Answer

Die Menge aller nicht entscheidbaren Sprachen ist unendlich.

Answer

Die Menge aller entscheidbaren Sprachen ist endlich.

Answer

Die Menge aller rekursiv aufzählbaren Sprachen ist endlich.

Question 51

Welche der folgenden Anwendungen basiert auf der Theorie formaler Sprachen und Automaten?

Accepted Answer

Compilerbau

Answer

Webentwicklung

Answer

Betriebssystemdesign

Answer

Datenbank-Optimierung

Question 52

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

Accepted Answer

c

Answer

ab

Answer

abb

Answer

ε

Question 53

Welche Eigenschaft ist **nicht** für eine Turingmaschine charakteristisch?

Accepted Answer

Sie verfügt über einen begrenzten Speicher.

Answer

Sie kann unendlich lange Berechnungen durchführen.

Question 54

Welche der folgenden Sprachen ist nicht kontextfrei?

Accepted Answer

{a^n b^n c^n | n ≥ 0}

Answer

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

Answer

{a^n b^m | n, m ≥ 0}