 Thema: Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
|
|
Jetzt kommt,Lösung zur Aussage mit dem Durchschnitt
(A (Durchschnitt) B)* =A* (Durchschnitt) B* dies ist eine falsche Aussage
Gegenbeispiel: Sei A={1,0} und B={10}
A* (Durchschnitt) B* = { e, 1, 0, 10, ...} (Durchschnitt) { e, 10, 1010, ... }
= { e, 10, 1010, ... }
= (10)*
(A (Durchschnitt) B )* = O/ * = { e } wobei O/ die Leere Menge ist
Daraus folgt
(A(Durchschnitt)B )*=O/*= { e } ist nicht gleich (10)*= A* (Durchschnitt) B*
|
|
| Thema: Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
|
|
Hallo Ihr Lieben,
also hier kommt die Lösung zu (A*)*=A*
z.z. (A*)*=A*
Zuerst kommt ein Zwischenbeweis:
z.z. (A*)^n = A* (mit vollständiger Induktion)
Induktionsanfang: n=1 : (A*)^1=A* dies ist eine wahre Aussage
Induktionsvoraussetzung: (A*)^n = A*
Induktionsschritt: n --> n+1
Induktionsbeweis:
(A*)^n+1 = (A*) ^n ° A* wobei ich ° für die Multiplikation verwende
Ind.Vor. = A* ° A*
= {vw I v Element A*, w Element A*} wobei I für ein
senkrechten Strich steht
={ v1 v2 ...vn w1 w2 ...wm I n,m >=0, vi, wi ElementA} (1,2,n,m,i
sind Indizes)
={z1 z2 ... zn+m I n+m>=0, zi Element A}
= A* q.e.d vom Zwischenbeweis.
(A*)*= (A*)^1 U (A*)^2 U (A*)^3 U .... wobei U für
Vereinigung steht
wegen des Zwischenbeweises
= A* U A* U A* U ....
= A* q.e.d
|
|
| Thema: Entscheidbarkeit von Sprachen |
|
|
@Anonymus
Lieber Anonymus, vielen Dank, dass du mich darauf aufmerksam gemacht hast, dass nach meinen Lösungen gefragt wurde. Die Benachrichtigungsemail ist nämlich in meinem Spam folder gelandet, die ich heute gefunden habe. Also ich habe das nicht absichtlich gemacht, wollte ich Dir hier nur mal sagen, denn ich helfe immer sehr gerne, wenn ich kann.
|
|
| Thema: Entscheidbarkeit von Sprachen |
|
|
Hallo ihr Lieben,
ich brauche unbedingt Eure Hilfe, ich blicke da noch nicht so durch wenn es zu entscheidbaren Sprachen kommt. Ich soll die folgenden Aussagen mit wahr oder falsch kommentieren und begründen und ich habe keine Ahnung, obwohl ich mich ein wenig in die Thematik reingelesen habe.
Die Aussagen sind.
a)Alle echten Teilsprachen von unentscheidbaren Sprachen sind unentscheidbar.
b)Jede endliche Sprache ist entscheidbar.
c)Wenn L Teilmenge von {0,1}* unentscheidbar ist, dann ist auch L\{0110} unentscheidbar.
d)Jede entscheidbare Sprache ist regulär.
e)Jede entscheidbare Sprache ist Teilmenge einer regulären Sprache.
Vielen vielen Dank für Eure Hilfe im Voraus.
|
|
| Thema: Simulation eines DEAs durch eine Turing Maschine |
|
|
Hallo,
ich bräuchte mal Hilfe bei der folgenden Aufgabe:
a) Es ist zu beschreiben, wie man einen DEA durch eine Turing-Maschine simulieren kann. Man soll dabei die unterschiedlichen Akzeptierungsmodi beachten
b)Des Weitern ist zu beweisen, dass man jede Turingmaschine mit beidseitig unbeschränktem Eingabe-/ Arbeitsband durch eine Turingmaschine mit einseitig unbeschränktem Band simulieren kann.
Ich schätze jede Hilfe. Viele Grüße und vielen Dank im Voraus.
|
|
| Thema: Semi-Entscheidbarkeit |
|
|
Hallo ich bräuchte Hilfe bei der folgenden Aufgabe:
Sei L Teilmenge von Sigma Stern eine Sprache.
Zu Zeigen ist: Wenn L und Sigma Stern ohne L (E\L) rekursiv aufzählbar sind, so ist L entscheidbar.
Ich habe keine Ahnung wie ich daran gehen soll, würde mich über jede Hilfe freuen.
Viele Grüße
|
|
| Thema: Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
|
|
Bei der Aufgabe:
(A°B)*= A* ° B* , mit ° ist die Konkatenation gemeint.
Falsche Aussage! Denn
Sei A= {1,2} und B={5,6}
A°B={15,26} , (A°B)*= { leere Wort, 15,26, 1515, 1526,2615,2626,151515,151526,152615,152626,261515,261526,262615,262626, ...}
A*°B*={leere Wort (2 Mal hintereinander(weiss gar nicht, ob das geht)), 15,26,1155,1256,2165,2266,111555,112556,121565,122566,221655,222656,211665,
212666 ...}
z.B der String 1515 ist Element (A°B)*, aber nicht Element A*°B*
Ist das richtig?
|
|
| Thema: Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
|
|
Bei der Aufgabe:
( A [Durchschnitt] B)* = A* [Durchschnitt] B*
Annahme die Aussage ist falsch:
Sei A={1,2} und B={7,8}
Dann ist : A [Durchschnitt] B = leere Menge
Dann ist: ( A [Durchschnitt] B)* = [leeres Wort] oder?
A* und B* wie oben, aber A* [Durchschnitt] B* wäre dann ja auch das leere Wort. Also
hätte ich hier ein Widerspruch zur Annahme und die Aussage wäre richtig. Oder?
|
|
| Thema: Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
|
|
Hallo Karlito,
vielen Dank für den Tipp, also ich habe mir ein Beispiel für die Vereinigung ausgedacht:
Sei Sigma die Menge der natürlichen Zahlen.
Sei A={1,2} und B={7,8}
(A U B)* = { e (leere Wort), 1, 2,7,8,11,12,17,18,21,22,27,28,71,72,77, 78,81,82,87, 88, 111,112,117,118,121,122,127,128,171,172,177,178,181,182,187,188, ... }
A* U B* = {e(leere Wort),1,2,7,8,11,12,21,22,77,78,87,88,112,121,122,211,212, 221,222,777,787, ..}
=> 71 ist Element (A U B)* aber nicht Element A* U B*.
Wäre das so richtig?
|
|
| Thema: Kleene Stern angewandt auf Mengen Beweise oder Widerlege |
|
|
Meine Frage:
Sei E (sigma) ein Alphabet und A,B (sind) Teilmengen von E* formale Sprachen. Beweisen oder widerlegen Sie!
(A U B)*= A* U B*
(A ° B)*=A* ° B*
(A*)*= A*
Meine Ideen:
Zuerst dachte ich das ich die mathematische Mengenlehre hier anwenden kann, aber ich weiß nicht so recht was ich mit dem Kleene Stern machen soll. Ich weiß, dass der Kleene Stern auf eine beliebig oft iterierte Konkatenation hinweist, aber ich weiß nicht wie ich hier anfangen soll. Bitte um Hilfe
|
|
|
