TI: Rekursiv aufzählbare Sprachen

Wissenschaft Informatik
#1

Hallo.

Ich hoffe ihr könnt mir helfen, denn ich komme einfach nicht zu einem vernünftigen Beweis.

Ich soll zeigen das, wenn L1 und L2 rekursiv aufzählbar sind, dann ist auch L1 geschnitten L2 rekursiv aufzählbar.

Nur wie zeige ich das? Ich weiß das eine rekursiv aufzählbare Sprache vom Typ 0 und und sich durch eine Turing Maschine darstellen lässt, welche L = L(M) akzeptiert. Wenn also L1 und L2 sich jeweils auf eine TM abbilden lassen, dann muss das ja auch für die Teilmenge von L1 geschnitten L2 der Fall sein, nur wie kann ich das Beweisen?

Schöne Grüße,

Dennis

#2

Hallo,

M1 sei Semialgo bzw Turingmaschine für L1 und M2 Semialgo für L2

L1, L2 sind rekursiv a., dann auch der Schnitt:

w Elem. L1 geschnitten L2 -> w in L1 und w ist in L2-> M1 hält und akzeptiert und M2 auch.

w nicht Elem. L1 geschnitten L2->

1Fall: w nicht Elem. L1, M1 hält und akz. nicht oder M1 hält nicht.
2Fall: w Elem. L1, aber w nicht Elem. L2: M1 hält und akz., aber M2 hält und akz. nicht oder M2 hält nicht.

fertig…

#3

Ok danke für die schnelle Antwort!

Hab da wohl wieder zu kompliziert gedacht.

Dennis