Theoretische Informatik - Entscheidbarkeit

Diskutiere Theoretische Informatik - Entscheidbarkeit im Mathematik Forum; Sei Σ ein Alphabet und seien L1 , L2 ∈ Σ* entscheidbar. Wieso sind dann auch L1 ∩ L2, L1 ∪ L2 und Σ* \ L1 entscheidbar??? Und gilt die...

  1. krgewb
    krgewb Aktives Mitglied
    Sei Σ ein Alphabet und seien L1 , L2 ∈ Σ* entscheidbar. Wieso sind dann auch L1 ∩ L2, L1 ∪ L2 und Σ* \ L1 entscheidbar??? Und gilt die Abgeschlossenheit unter Durchschnitt, Vereinigung und Komplementbildung auch für die Menge der semi-entscheidbaren Sprachen?
     
  2. Vielleicht hilft dir dieser Java-Kurs hier weiter --> (hier klicken)
  3. Kababär
    Kababär Aktives Mitglied
    Wenn die Mengen L1 und L2 entscheidbar sind, dann doch auch deren Vereinigung, Durchschnitt und Komplement.
    Um zu zeigen, dass die Vereinigung von L1 und L2 entscheidbar ist, muss du eine Bedingung aufstellen, die gleichermaßen einfach ist: Entweder ist der zu suchende Buchstabe 'a' in L1 oder in L2. Beim Durchschnitt kann bekanntermaßen entschieden werden, in dem geprüft wird, ob 'a' in L1 und L2 ist.
    Wenn man eine Menge entscheiden kann, so auch dessen Komplement. Dafür braucht man die Definition einer Sprache für jedes beliebige Element nur zu negieren.
    Das gleiche gilt für semi-entscheidbare Sprachen, die auch "aufzählbare Sprachen" genannt werden.
     
Die Seite wird geladen...

Theoretische Informatik - Entscheidbarkeit - Ähnliche Themen

Theoretische Informatik - Aufgaben lösen
Theoretische Informatik - Aufgaben lösen im Forum Private Stellangebote und Stellensuche von Usern
Gibt es Bedarf an theoretischen InformatikerInnen in der Wirtschaft?
Gibt es Bedarf an theoretischen InformatikerInnen in der Wirtschaft? im Forum Plauderecke
Theoretische Informatik - Automat für Vergleich von Dualzahlen
Theoretische Informatik - Automat für Vergleich von Dualzahlen im Forum Hausaufgaben
Theoretische Informatik Frage zu Formalismus RegExp
Theoretische Informatik Frage zu Formalismus RegExp im Forum Softwareentwicklung
Was genau ist eigentlich theoretische Informatik und wozu wird sie benötigt?
Was genau ist eigentlich theoretische Informatik und wozu wird sie benötigt? im Forum Plauderecke
Thema: Theoretische Informatik - Entscheidbarkeit