Informatiker Board | Theoretische Informatik | Beweis zum Kürzen in Worthalbgruppen

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis zum Kürzen in Worthalbgruppen » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

[quote][i]Original von David1979[/i]
Hallo zusammen,

ich habe hier die folgende Aufgabenstellung:

[quote][i]"In Worthalbgruppen gelten die Kürzungsregeln, wenn [latex]xu=xw[/latex], dann [latex]u = w[/latex] und wenn [latex]ux = wx[/latex], dann [latex]u = w[/latex].

Zeigen Sie die Gültigkeit dieser Regeln. Beachten Sie dabei, daß [latex]x \circ y[/latex] aus [latex]a \circ x = a \circ y[/latex], die Funktion zur Bildung von Wörtern also im zweiten Argument eineindeutig ist."[/i][/quote]

Jetzt habe ich mittels vollständiger Induktion versucht eine Lösung für das Kürzen zu bekommen:

[b](i) Induktionsannahme mit [latex]x=\epsilon[/latex][/b]

[latex]\epsilon u = \epsilon w  \Rightarrow u = w[/latex]

[b](ii) Induktionsanfang mit [latex]x = v[/latex][/b]

[latex]vu = vw \Rightarrow u = w[/latex]

[b](iii) Induktionsschritt mit [latex] x = av[/latex][/b]

[latex]avu = avw \Rightarrow au = aw[/latex]

und nach Definition erhalten wir wieder

[latex]au = aw \Rightarrow u = w[/latex]

Ist das so in Ordnung? Ich kann mir irgendwie nicht vorstellen, dass das schon alles ist ?!? ?(

//EDIT: Titel nochmal geändert[/quote]

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 4 Beiträge

ed209

RE: Beweis zum Kürzen in Worthalbgruppen

Zitat:

Das mit der Definition der einzelnen Wörter oder Zeichen hätte ich auch gerne näher beschrieben, aber die Aufgabenstellung hat aus meiner Sicht an der Stelle irgendwie nicht mehr hergegeben. Vielleicht ist es auch gar nicht so wichtig, ob es sich um Wörter oder Zeichen handelt, aber das werde ich ja noch erfahren smile

Sobald du in deinem Beweis Variablen verwendest mußt du klären aus welcher Menge die Variablen sind. Sonst ist der Beweis nicht vollständig. Ich nehme mal an daß a ein beliebiger Buchstabe ist und u,w und x Wörter, aber das ist keineswegs klar-.
Die Idee ist zwar völlig richtig, aber solche Ungenauigkeiten führen schnell zu Fehlern.
Auch mußt du hinschreiben daß du die Induktion über die Länge von x machst.

Gruss,
ED

David1979

RE: Beweis zum Kürzen in Worthalbgruppen

Erst einmal Danke fürs Drüberschauen smile

!

Das mit der Definition der einzelnen Wörter oder Zeichen hätte ich auch gerne näher beschrieben, aber die Aufgabenstellung hat aus meiner Sicht an der Stelle irgendwie nicht mehr hergegeben. Vielleicht ist es auch gar nicht so wichtig, ob es sich um Wörter oder Zeichen handelt, aber das werde ich ja noch erfahren smile

Den zweiten Beweisweg spare ich mir dann an dieser Stelle... läuft ja äquivalent ab.

Gruß,

David

ed209

RE: Beweis zum Kürzen in Worthalbgruppen

Zitat:

und nach Definition erhalten wir wieder

$[latex]au = aw \Rightarrow u = w[/latex]$

Ist das so in Ordnung? Ich kann mir irgendwie nicht vorstellen, dass das schon alles ist ?!? verwirrt

Für mich sieht das ganz solide aus, aber du solltest deutlicher machen worüber induzierst und was a,u,v,w,x sind (Zeichen oder Strings).

Die andere Richtung fehlt wohl auch noch. $[latex]ux =wx \Rightarrow u = w[/latex]$

Gruß,
ED

David1979

Beweis zum Kürzen in Worthalbgruppen

Hallo zusammen,

ich habe hier die folgende Aufgabenstellung:

Zitat:

"In Worthalbgruppen gelten die Kürzungsregeln, wenn , dann und wenn , dann .

Zeigen Sie die Gültigkeit dieser Regeln. Beachten Sie dabei, daß $[latex]x \circ y[/latex]$ aus $[latex]a \circ x = a \circ y[/latex]$ , die Funktion zur Bildung von Wörtern also im zweiten Argument eineindeutig ist."

Jetzt habe ich mittels vollständiger Induktion versucht eine Lösung für das Kürzen zu bekommen:

(i) Induktionsannahme mit $[latex]x=\epsilon[/latex]$

$[latex]\epsilon u = \epsilon w \Rightarrow u = w[/latex]$

(ii) Induktionsanfang mit

$[latex]vu = vw \Rightarrow u = w[/latex]$

(iii) Induktionsschritt mit

$[latex]avu = avw \Rightarrow au = aw[/latex]$

und nach Definition erhalten wir wieder

$[latex]au = aw \Rightarrow u = w[/latex]$

Ist das so in Ordnung? Ich kann mir irgendwie nicht vorstellen, dass das schon alles ist ?!? verwirrt

//EDIT: Titel nochmal geändert