Formale Sprachen und Automaten: Online-Quizzes für die Fachoberschule

Question 1

Welcher Operator in regulären Ausdrücken ermöglicht die Auswahl zwischen zwei Ausdrücken?

Accepted Answer

|

Answer

*

Answer

.

Question 2

Was ist die Bedeutung des Halteproblems und welche Konsequenzen hat es für die Berechenbarkeit?

Accepted Answer

Das Halteproblem ist unlösbar und zeigt, dass es unmöglich ist, ein allgemeines Verfahren zu entwickeln, das für alle Programme feststellt, ob sie terminieren.

Answer

Das Halteproblem ist lösbar, erfordert aber in der Praxis einen sehr hohen Rechenaufwand.

Answer

Das Halteproblem ist nur für bestimmte Programmiersprachen unlösbar.

Answer

Das Halteproblem hat keine praktischen Auswirkungen auf die Informatik und ist nur von theoretischem Interesse.

Question 3

Welche Aussage über die Lösbarkeit von Problemen durch Automaten ist korrekt?

Accepted Answer

Alle von einem endlichen Automaten lösbaren Probleme sind auch von einer Turingmaschine lösbar.

Answer

Alle von einer Turingmaschine lösbaren Probleme sind auch von einem endlichen Automaten lösbar.

Question 4

Wie hängen reguläre Ausdrücke und Automaten zusammen?

Accepted Answer

Reguläre Ausdrücke sind eine formale Sprache zur Beschreibung endlicher Automaten.

Answer

Automaten sind eine formale Sprache zur Beschreibung regulärer Ausdrücke.

Answer

Reguläre Ausdrücke und Automaten sind nicht miteinander verbunden.

Question 5

Inwiefern prägen formale Sprachen und Automatentheorie die Entwicklung von Programmiersprachen und Compilern?

Accepted Answer

Formale Sprachen und Automatentheorie helfen, die syntaktische Richtigkeit von Programmen zu prüfen.

Accepted Answer

Formale Sprachen und Automatentheorie haben die Entwicklung von Compilern revolutioniert, da sie die automatische Übersetzung von Programmen in Maschinencode ermöglichen.

Answer

Formale Sprachen und Automatentheorie haben keinen Einfluss auf die Entwicklung von Programmiersprachen und Compilern.

Answer

Formale Sprachen und Automatentheorie dienen nur der Entwicklung theoretischer Konzepte.

Question 6

Erläutert die praktische Bedeutung von **regulären Ausdrücken** und nennt konkrete Einsatzgebiete in Bereichen wie Texterkennung, Datenprüfung und Programmierung.

Accepted Answer

Reguläre Ausdrücke werden in Programmiersprachen zur Suche und Verarbeitung von Text verwendet.

Answer

Reguläre Ausdrücke haben keine praktische Anwendung.

Answer

Reguläre Ausdrücke werden hauptsächlich zur Überprüfung von E-Mail-Adressen verwendet.

Answer

Reguläre Ausdrücke können komplexe grammatikalische Strukturen natürlicher Sprachen analysieren.

Question 7

Was ist die Komplexitätsklasse NP und welche Rolle spielt sie bei ungelösten Problemen in der Informatik?

Accepted Answer

NP ist die Klasse der Probleme, die in polynomialer Zeit durch eine nichtdeterministische Turingmaschine gelöst werden können.

Accepted Answer

Das P-NP-Problem fragt, ob NP gleich P ist oder nicht.

Answer

NP ist eine Teilmenge der Klasse P, da nichtdeterministische Turingmaschinen immer schneller sind als deterministische Turingmaschinen.

Question 8

Welche Sprache kann von einer kontextfreien Grammatik, aber nicht von einem endlichen Automaten akzeptiert werden? Begründen Sie Ihre Antwort.

Accepted Answer

Die Sprache aller Palindrome

Answer

Die Sprache aller Primzahlen

Answer

Die Sprache aller durch 3 teilbaren Zahlen

Answer

Die Sprache aller Zahlen größer als 10

Question 9

Beschreibe die wichtigsten Unterschiede zwischen endlichen Automaten (FA) und Pushdown-Automaten (PDA) hinsichtlich ihrer Akzeptanzfähigkeit und ihrer formalen Definitionen.

Accepted Answer

FAs können nur reguläre Sprachen akzeptieren, während PDAs auch kontextfreie Sprachen akzeptieren können.

Accepted Answer

FAs werden formal durch eine 5-Tupel-Definition beschrieben, während PDAs durch eine 6-Tupel-Definition definiert sind.

Answer

FAs können unendliche Eingaben verarbeiten, während PDAs nur endliche Eingaben verarbeiten können.

Answer

PDAs haben einen endlichen Zustandsraum, während FAs einen unendlichen Zustandsraum haben.

Question 10

Was beschreibt ein regulärer Ausdruck?

Accepted Answer

Eine Menge von Zeichenfolgen

Answer

Eine einzige Zeichenfolge

Answer

Nur Großbuchstaben

Answer

Nur Buchstaben und Ziffern

Question 11

Welche Eigenschaften treffen auf endliche Automaten zu?

Accepted Answer

Sie besitzen eine begrenzte Anzahl von Zuständen.

Accepted Answer

Sie haben einen Anfangszustand.

Accepted Answer

Sie können mehrere Endzustände haben.

Answer

Sie dürfen keine Zyklen im Zustandsübergangsdiagramm enthalten.

Question 12

Welche Aussage beschreibt die Beziehung zwischen Turingmaschinen und universellen Turingmaschinen korrekt?

Accepted Answer

Universelle Turingmaschinen können alle anderen Turingmaschinen simulieren.

Answer

Turingmaschinen sind eine Untergruppe universeller Turingmaschinen.

Answer

Universelle Turingmaschinen arbeiten auf unendlich großen Bändern.

Answer

Turingmaschinen und universelle Turingmaschinen sind nicht miteinander verbunden.

Question 13

Welche der folgenden Grammatiken erzeugt die Sprache aller Palindrome (Zeichenfolgen, die rückwärts gelesen gleich sind)?

Accepted Answer

S -> aSa | bSb | ε

Answer

S -> aS | bS | ε

Answer

S -> aa | bb | ε

Answer

S -> ab | ba | ε

Question 14

Welcher Automattyp erkennt genau die regulären Sprachen?

Accepted Answer

Deterministischer endlicher Automat (DFA)

Answer

Nicht-deterministischer endlicher Automat (NFA)

Answer

Deterministischer Kellerautomat (PDA)

Answer

Nicht-deterministischer Kellerautomat (NPDA)

Question 15

Welche der folgenden Aussagen über Turingmaschinen ist zutreffend?

Accepted Answer

Sie sind universell, d. h. sie können jede berechenbare Funktion berechnen.

Answer

Sie sind nicht in der Lage, das Halteproblem zu lösen.

Answer

Sie sind immer deterministisch.

Answer

Sie haben eine unendliche Anzahl von Zuständen.

Question 16

Welche der folgenden Aussagen über das Halteproblem ist zutreffend?

Accepted Answer

Es ist ein unentscheidbares Problem.

Answer

Es ist ein entscheidbares Problem.

Answer

Es ist für deterministische Turingmaschinen entscheidbar.

Answer

Es ist für nicht-deterministische Turingmaschinen entscheidbar.

Question 17

Welcher der folgenden Automatentypen ist deterministisch?

Accepted Answer

DFA mit 3 Zuständen, 2 Eingabesymbolen und 1 Akzeptanzzustand

Answer

PDA mit 1 Stapelsymbol

Answer

NFA mit 2 Zuständen, 3 Eingabesymbolen und 1 Akzeptanzzustand

Question 18

Welche der folgenden Aussagen über Turingmaschinen ist korrekt?

Accepted Answer

Sie können jede berechenbare Funktion berechnen.

Answer

Sie sind immer deterministisch.

Answer

Sie haben ein endliches Band.

Answer

Sie können nur Probleme lösen, die in polynomialer Zeit lösbar sind.

Question 19

Welcher Begriff beschreibt die Eigenschaft einer Sprache, die von einem nichtdeterministischen endlichen Automaten akzeptiert werden kann?

Accepted Answer

Nichtdeterministisch regulär

Answer

Deterministisch regulär

Answer

Rekursiv aufzählbar

Answer

Kontextfrei

Question 20

Welche Technik kann verwendet werden, um einen regulären Ausdruck in einen endlichen Automaten umzuwandeln?

Accepted Answer

Kleenescher Algorithmus

Answer

Greibach-Normalform

Answer

Chomsky-Normalform

Answer

Pumping-Lemma

Question 21

Welcher Begriff beschreibt die Fähigkeit eines Automaten, eine Eingabe in allen möglichen Pfaden zu verarbeiten?

Accepted Answer

Nichtdeterminismus

Answer

Parallelität

Answer

Determinismus

Answer

Rekursion

Question 22

Welche Aussage über formale Sprachen ist korrekt?

Accepted Answer

Sie sind eine mathematische Repräsentation von Sprachen.

Answer

Sie basieren immer auf dem Alphabet {0, 1}.

Answer

Sie werden nur in der Linguistik verwendet.

Question 23

Welcher der folgenden regulären Ausdrücke beschreibt die Menge aller Binärfolgen, die mit einer 0 enden?

Accepted Answer

0.*$

Answer

01*00

Answer

10*0

Answer

00*1

Question 24

Welche der folgenden Sprachen ist nicht kontextfrei?

Accepted Answer

{w ∈ {a,b}* | w enthält mindestens zwei gleiche aufeinanderfolgende Zeichen}

Answer

{w ∈ {a,b}* | w enthält eine gerade Anzahl von a}

Answer

{w ∈ {a,b}* | w enthält mindestens ein a}

Question 25

Welche der folgenden Aussagen über reguläre Ausdrücke ist zutreffend?

Accepted Answer

Jeder reguläre Ausdruck kann durch einen endlichen Automaten dargestellt werden.

Answer

Jeder reguläre Ausdruck kann durch eine Turingmaschine dargestellt werden.

Answer

Jeder reguläre Ausdruck kann durch eine kontextfreie Grammatik dargestellt werden.

Question 26

Welcher der folgenden finiten Automaten akzeptiert die Sprache L = {w ∈ {a,b}* | w enthält mindestens ein a und mindestens ein b}?

Accepted Answer

Zustände: {q0, q1, q2}
Startzustand: q0
Akzeptanzzustände: {q2}
Übergangsfunktion:
q0 -> q0 (bei a)
q0 -> q1 (bei b)
q1 -> q2 (bei a)
q1 -> q1 (bei b)
q2 -> q2 (bei a)
q2 -> q2 (bei b)

Answer

Zustände: {q0, q1, q2}
Startzustand: q0
Akzeptanzzustände: {q2}
Übergangsfunktion:
q0 -> q0 (bei a)
q0 -> q1 (bei b)
q1 -> q1 (bei a)
q1 -> q2 (bei b)
q2 -> q2 (bei a)
q2 -> q0 (bei b)

Question 27

Welche der folgenden Aussagen über reguläre Ausdrücke ist FALSCH?

Accepted Answer

Reguläre Ausdrücke können nicht zur Validierung von E-Mail-Adressen verwendet werden.

Answer

Reguläre Ausdrücke können in verschiedenen Programmiersprachen verwendet werden.

Answer

Reguläre Ausdrücke können verwendet werden, um Muster in Texten zu finden.

Question 28

Welche Grammatik beschreibt die Sprache aller Wörter, die mit "a" beginnen und mit "b" enden?

Accepted Answer

S -> aA
A -> aA | b

Answer

S -> aSb

Answer

S -> aS | b

Answer

S -> a | bS

Question 29

Welche Art von Automaten kann die Sprache aller Wörter mit einer geraden Anzahl von "a"s erkennen?

Accepted Answer

Endlicher Automat

Answer

Turingmaschine

Answer

Kellerautomat

Answer

Pushdown-Automat

Question 30

Welche Aussage beschreibt die Turingmaschine am besten?

Accepted Answer

Ein theoretisches Modell eines Computers mit unbegrenztem Speicher und einem einfachen Satz von Anweisungen.

Answer

Ein praktischer Computer, der komplexe Algorithmen ausführen kann.

Question 31

Welche der folgenden Sprachen ist NICHT regulär?

Accepted Answer

Die Sprache aller Wörter, die die gleiche Anzahl von "a"s und "b"s enthalten.

Answer

Die Sprache aller Wörter, die mit "a" beginnen.

Answer

Die Sprache aller Wörter, die höchstens drei "b"s enthalten.

Question 32

Welcher Ausdruck beschreibt die Menge aller Wörter, die mit einem 'a' beginnen und mit einem 'b' enden, wobei 'a' und 'b' beliebige Zeichen sein können?

Accepted Answer

a.b*

Answer

a+b+

Answer

a*b*

Answer

(a|b)*

Question 33

Welche Aussage über die Chomsky-Hierarchie ist RICHTIG?

Accepted Answer

Die Chomsky-Hierarchie klassifiziert formale Sprachen nach der Komplexität ihrer Grammatiken.

Answer

Die Chomsky-Hierarchie wurde entwickelt, um die Leistung von Programmiersprachen zu bewerten.

Answer

Die Chomsky-Hierarchie ordnet alle Sprachen nach ihrer Schwierigkeit.

Question 34

Welche der folgenden Aufgaben kann eine Turingmaschine NICHT lösen?

Accepted Answer

Das Halteproblem für beliebige Turingmaschinen.

Answer

Die Simulation eines endlichen Automaten.

Answer

Die Berechnung der Fakultätsfunktion.

Answer

Die Sortierung einer Liste von Zahlen.

Question 35

Ein endlicher Automat mit n Zuständen kann höchstens wie viele verschiedene Sprachen erkennen?

Accepted Answer

2^n

Answer

n

Answer

n!

Answer

n^2

Question 36

Welche der folgenden Aussagen über Pushdown-Automaten ist RICHTIG?

Accepted Answer

Pushdown-Automaten können kontextfreie Sprachen erkennen.

Answer

Pushdown-Automaten sind genauso mächtig wie Turingmaschinen.

Answer

Pushdown-Automaten können nur reguläre Sprachen erkennen.

Question 37

Welcher der folgenden regulären Ausdrücke entspricht der Sprache aller Zeichenfolgen, die mit 'a' beginnen und mit 'b' enden?

Accepted Answer

a.*b

Answer

ab*

Answer

a*b+

Answer

a+b*

Question 38

Welche der folgenden Aussagen über einen endlichen Automaten ist FALSCH?

Accepted Answer

Ein endlicher Automat kann eine unendliche Anzahl von Zuständen haben.

Answer

Ein endlicher Automat kann eine endliche Anzahl von Zuständen haben.

Answer

Ein endlicher Automat kann eine endliche Anzahl von Übergängen haben.

Question 39

Welche der folgenden Sprachen ist NICHT regulär?

Accepted Answer

Die Sprache aller Palindrome über dem Alphabet {a, b}.

Answer

Die Sprache aller Zeichenfolgen, die mit 'a' beginnen und mit 'b' enden.

Answer

Die Sprache aller Zeichenfolgen, die eine gerade Anzahl von 'a's enthalten.

Question 40

Was ist die Funktion eines endlichen Automaten?

Accepted Answer

Er akzeptiert oder verwirft eine Eingabezeichenfolge basierend auf einem Satz von Regeln.

Answer

Er berechnet mathematische Funktionen.

Answer

Er generiert zufällige Zeichenfolgen.

Question 41

Welche der folgenden Grammatiken ist eine reguläre Grammatik?

Accepted Answer

S -> aS | b

Answer

S -> aSa | bSb | ε

Answer

S -> aSb | a

Answer

S -> aSb | ε

Question 42

Was ist der Unterschied zwischen einem deterministischen endlichen Automaten (DFA) und einem nicht-deterministischen endlichen Automaten (NFA)?

Accepted Answer

Ein DFA hat für jede Eingabe und jeden Zustand genau einen Übergang, während ein NFA mehrere Übergänge für die gleiche Eingabe und den gleichen Zustand haben kann.

Answer

Ein DFA kann unendliche Eingaben verarbeiten, ein NFA nicht.

Question 43

Welche der folgenden Aussagen über Turingmaschinen ist WAHR?

Accepted Answer

Turingmaschinen können jede berechenbare Funktion berechnen.

Answer

Turingmaschinen können nur reguläre Sprachen erkennen.

Answer

Turingmaschinen sind effizienter als endliche Automaten.

Question 44

Welche der folgenden Aufgaben kann eine Turingmaschine lösen, die ein endlicher Automat NICHT lösen kann?

Accepted Answer

Die Entscheidung, ob eine Zeichenkette ein Palindrom ist.

Answer

Die Erkennung einer Zeichenkette, die mit 'a' beginnt.

Answer

Die Zählung der Anzahl der 'a's in einer Zeichenkette.

Question 45

Welches der folgenden Konzepte beschreibt die Fähigkeit eines Automaten, einen bestimmten Zustand zu erreichen, wenn er eine bestimmte Eingabe verarbeitet?

Accepted Answer

Erreichbarkeit

Answer

Akzeptierbarkeit

Answer

Determinismus

Answer

Regularität

Question 46

Ein endlicher Automat mit n Zuständen kann maximal wie viele verschiedene Sprachen erkennen?

Accepted Answer

2^n

Answer

n!

Answer

n^2

Answer

n