Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Wie ist bei det und ndet?

–1 Punkt
24 Aufrufe

und mit det und ndet gilt dann?

L detEA ( L ndetEA ( netLKA (dnetLKA (LdetTM (LndetTM  ?

 
bezieht sich auf eine Antwort auf: Nachfrage zur Sprachmächtigkeit
Gefragt 22, Okt 2014 in SPR-AD von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte

Hallo,

das hängt davon ab, welche Automaten du betrachtest. Bei EA und TM ist die Mächtigkeit unabhängig vom Determinismus. Lediglich die Mächtigkeit des nichtdet. KA ist größer als die des det. KA.

Somit gilt L detEA = L ndetEA ( L detKA ( L ndetKA ( L detTM = L ndetTM

Mächtigkeit bedeutet in diesem Kontext z.B., dass die Menge der Sprachen, die von einem EA erkannt werden kann, eine Teilmenge der Sprachen ist, die von einem KA erkannt werden kann.

Viele Grüße

Philippe (Tutor)

 

Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...