Search Header Logo

PDAs

Authored by FSuB Uebung

Computers

University

Used 1+ times

PDAs
AI

AI Actions

Add similar questions

Adjust reading levels

Convert to real-world scenario

Translate activity

More...

    Content View

    Student View

10 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Welche Aussage ist korrekt?

Jede kontextfreie Sprache kann von einem DFA erkannt werden

Jeder PDA erkennt genau die regulären Sprachen

Für jede kontextfreie Sprache existiert ein PDA

Reguläre Sprachen sind Typ-2 im Chomsky-Hierarchie

2.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Ordne die Grammatiken den Chomsky-Typen korrekt zu:

regulär, kontextfrei, kontextsensitiv, rekursiv aufzählbar

kontextfrei, regulär, kontextsensitiv, rekursiv

regulär, kontextsensitiv, kontextfrei, rekursiv

regulär, regulär, regulär, regulär

3.

MULTIPLE SELECT QUESTION

45 sec • 1 pt

Was beschreibt die Transitionsrelation Δ eines Kellerautomaten?

Eine Relation, die nur Eingabe und Folgezustände betrachtet

Δ⊆Q×(Σ∪{ε})×Γ×Q×Γ^∗

Eine Relation über Zustände, Eingabesymbole, Kellersymbole und Folgezustände

Eine Relation über Zustände, Eingabesymbole, Kellersymbole und Folgezustände und Kellersymbole

4.

MULTIPLE SELECT QUESTION

30 sec • 1 pt

Was ist eine kontextfreie Grammatik?

Eine Grammatik mit Produktionen der Form A→α, wobei A∈V, α∈(V∪Σ)∗

Eine Grammatik mit Produktionen, bei denen auf der linken Seite genau ein Nichtterminal steht

Eine Grammatik mit Produktionen der Form A→α, wobei A∈V/S, α∈(V∪Σ)+ .

Eine Grammatik mit beliebigen Produktionen α→β, wobei ∣α∣≤∣β∣

5.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Was beschreibt eine Typ-3 Grammatik (regulär)?

Produktionen der Form A→aB oder A→a mit A,B∈V,a∈Σ

Produktionen der Form A→aB oder A→a mit A,B∈V,a∈Σ^*

Beliebige Produktionen mit Variablen auf beiden Seiten

Produktionen der Form A→BC

6.

MULTIPLE CHOICE QUESTION

30 sec • 1 pt

Was ist eine Typ-1 Grammatik (kontextsensitive)?

Produktionen der Form A→a

Alle Produktionen l→r mit ∣l∣≤∣r∣

Nur Produktionen mit rechten Seiten aus Terminals

Produktionen wie A→ε ohne Einschränkungen

7.

MULTIPLE SELECT QUESTION

30 sec • 1 pt

Welche algorithmischen Probleme sind bei Typ-3 Grammatiken lösbar?

Wortproblem

Leerheitsproblem

Äquivalenzproblem

Keine der genannten

Access all questions and much more by creating a free account

Create resources

Host any resource

Get auto-graded reports

Google

Continue with Google

Email

Continue with Email

Classlink

Continue with Classlink

Clever

Continue with Clever

or continue with

Microsoft

Microsoft

Apple

Apple

Others

Others

Already have an account?