Kapitel 8

Question 1

Was sind Teilbereiche der Theoretischen Informatik?

Answer 1

• Formale Sprachen
• Automatentheorie
• Berechenkeitstheorie
• Komplexitätstheorie

Question 2

Was heißt XML?

Answer 2

Extensible Markup Language (Kontextfreie Grammatik)

Question 3

Was heißt DTD?

Answer 3

Document Type Definition (beschreibt Produktionsregeln)

Question 4

Was ist theoretische Informatik?

Answer 4

beschäftigt sich mit Computern anhand von Abstraktionen und Modellen

Question 5

Was ist die Definition von Algorithmus?

Answer 5

Vorschrift, nach der ein System Operationen in einer bestimmten Reihenfolge ausführt, um Aufgabe eines Typs zu lösen

Question 6

Nennen Sie die Begriffe der Theoretischen Informatik

Answer 6

Syntaxbaum(1) modelliert (1..n)Grammatik(1) erzeugt (1)Sprache

Sprache(1) erkennt (1)Automat(1..n) modelliert (1)Zustandsgraph

Sprache(1..n) besteht aus (1..n)Wort(1..n) besteht aus (1..n)Zeichen

Question 7

Erklären Sie die Chromsky-Hierarchie der Grammatiken

Answer 7

Alle Sprachen

• -> Typ 0: oder rekursiv aufzählbare Sprachen
  
  • -> Typ 1: oder kontextsensitive Sprachen
    
    • -> Typ 2: oder kontextfreie Sprachen
      
      • ->Typ 3: oder reguläre Sprachen