Theoretische Informatik at Albert-Ludwigs-Universität Freiburg

Flashcards and summaries for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg

Arrow Arrow

It’s completely free

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

Study with flashcards and summaries for the course Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Welche Bedingung(en) muss gelten, damit eine kontextfreie Grammatik ɛ-frei ist?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Wie ist ein deterministischer endlicher Automat (DFA) definiert?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Wie kann man die Übergangsfunktion eines DFA M = ⟨Q, Σ, δ, q0, F⟩ zu einer mit Wörtern (statt einzelnen Symbolen erweitern?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Welche Sprache kann durch einen DFA erkannt werden?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Die Klasse der Sprachen, die durch einen DFA erkannt werden können, ist genau die Klasse der regulären Sprachen

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Gebe die reguläre Grammatik G_M = ⟨V,Σ,P,S⟩ zum DFA M = ⟨Q, Σ, δ, q_0, F⟩ an.

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Wie ist ein nichtdeterministischer Automat (NFA) M aufgebaut?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Was ist ein Lauf (eines NFA)?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Wie viele Läufe hat ein DFA/NFA für ein Wort?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Was ist die Sprache eines NFA M?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Wie übersetzt man ein Syntaxdiagramm in einen NFA?

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Welche Zustände aus einem Potenzmengen-DFA kann man weglassen, um ihn zu vereinfachen?

Your peers in the course Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Flashcard Flashcard

Exemplary flashcards for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg on StudySmarter:

Theoretische Informatik

Welche Bedingung(en) muss gelten, damit eine kontextfreie Grammatik ɛ-frei ist?

Nur diese Regel (1): Es gibt keine Regel der Form A → ɛ

Theoretische Informatik

Wie ist ein deterministischer endlicher Automat (DFA) definiert?

M = ⟨Q, Σ, δ, q0, F⟩, wobei

Q: endliche Menge von Zuständen

Σ: Alphabet

δ: Übergangsfunktion, eine partielle Funktion Q×Σ → Q

q0: Startzustand, aus Q

F: Menge von Endzustände (Teilmenge von Q)

Theoretische Informatik

Wie kann man die Übergangsfunktion eines DFA M = ⟨Q, Σ, δ, q0, F⟩ zu einer mit Wörtern (statt einzelnen Symbolen erweitern?

δ: Q × Σ^∗ → Q

Definiere δ(q,w) wie folgt (für q ∈ Q, ein Wort w ∈ Σ^∗):

  • δ(q,ε) = q (Fall w = ε)
  • δ(q,av) = δ(δ(q,a),v) (Fall w = av)
  • δ(q,w) = undefiniert, wenn einer der nötigen Übergänge undefiniert ist.

Theoretische Informatik

Welche Sprache kann durch einen DFA erkannt werden?

Kontextsensitive Sprache (Typ 1)

Theoretische Informatik

Die Klasse der Sprachen, die durch einen DFA erkannt werden können, ist genau die Klasse der regulären Sprachen

Wahr

Theoretische Informatik

Gebe die reguläre Grammatik G_M = ⟨V,Σ,P,S⟩ zum DFA M = ⟨Q, Σ, δ, q_0, F⟩ an.

  • V := Q
  • S := q_0
  • P besteht aus den Regeln:
    • q →aq' , falls δ(q,a) = q'
    • q →a , falls δ(q,a) ∈ F
    • q_0 → ε , falls q_0 ∈ F

Theoretische Informatik

Wie ist ein nichtdeterministischer Automat (NFA) M aufgebaut?

M = ⟨Q, Σ, δ, Q0, F⟩ wobei

  • Q: endliche Menge von Zuständen
  • Σ: Alphabet
  • δ: Übergangsfunktion, eine totale Funktion Q×Σ→2^Q (Potenzmenge)
  • Q0: Menge möglicher Startzustände Q0 ⊆ Q
  • F: Menge von Endzuständen F ⊆ Q

Theoretische Informatik

Was ist ein Lauf (eines NFA)?

eine Folge von Zuständen q0 . . .qm, so dass gilt (für ein Wort w = σ1...σn):

  • q0 ∈ Q0
  • qi+1 ∈ δ(qi,σi+1) für alle 0 ≤ i < m
  • (1) m = |w| = n oder (2) m < n und δ(qm,σm) = ∅


akzeptierender Lauf: m = n und qn ∈ F

verwerfender Lauf: sonst

Theoretische Informatik

Wie viele Läufe hat ein DFA/NFA für ein Wort?

DFA: genau 1

NFA: genau 1

Theoretische Informatik

Was ist die Sprache eines NFA M?

L(M) = Menge aller Wörter w, für die M einen akzeptierenden Lauf hat.

Theoretische Informatik

Wie übersetzt man ein Syntaxdiagramm in einen NFA?

  • zusammenhängende Linienbereiche werden Zustände
  • Knoten werden Übergänge

Theoretische Informatik

Welche Zustände aus einem Potenzmengen-DFA kann man weglassen, um ihn zu vereinfachen?

unerreichbare Zustände

Sign up for free to see all flashcards and summaries for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg

Singup Image Singup Image
Wave

Other courses from your degree program

For your degree program Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to Albert-Ludwigs-Universität Freiburg overview page

What is StudySmarter?

What is StudySmarter?

StudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for Theoretische Informatik at the Albert-Ludwigs-Universität Freiburg or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards