Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » formale sprachen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

formale sprachen
Beiträge zu diesem Thema	Autor	Datum
formale sprachen	g0ju	22.05.2008 19:47
RE: formale sprachen	Tobias	23.05.2008 10:40
RE: formale sprachen	g0ju	23.05.2008 11:40
RE: formale sprachen	Tobias	23.05.2008 15:59

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

g0ju
Grünschnabel

Dabei seit: 22.05.2008
Beiträge: 2

formale sprachen

Zitatantwort auf diesen Beitrag erstellen

Hallo,

ich habe hier eine aufgabe, in der es um formale sprachen geht und in der ich einen "beweis" erbringen soll.
folgender wortlaut:

zeigen sie, dass für alle beliebigen sprachen $[latex]L_1, L_2 \subseteq A^*[/latex]$ gilt:
$[latex](L_1 \circ L_2)^R = L_2^R \circ L_1^R[/latex]$

so, nun meine "lösung". ich bin mir im klaren, dass das mathematisch bestimmt alles andere als richtig und schön ist. es geht mir eigentlich nur darum, zu wissen, ob ich auf dem richtigen weg bin oder ob ich total falsch liege.

erster schritt:
$[latex](L_1 \circ L_2)^R = \{(w \circ v)^R | w \in L_1, v \in L_2\} = \{(w_1 \dots w_n v_1 \dots v_n)^R | w_{1 \dots n} \in w, v_{1 \dots n} \in v\} => \{v_n \dots v_1 w_n \dots w_1\}[/latex]$

zweiter schritt:
$[latex]L_2^R \circ L_1^R = \{v^R \circ w^R | v \in L_2, w \in L_1\} = \{(v_1 \dots v_n)^R \circ (w_1 \dots w_n)^R | v_{1 \dots n} \in v, w_{1 \dots n} \in w \} => \{v_n \dots v_1 w_n \dots w_1\}[/latex]$

so, nun steht ja da als ergebnis dasselbe.
reicht das aus und ist das alles so richtig?

danke erstmal fürs reinschauen! smile

22.05.2008 19:47

Nehmen Sie g0ju in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Die Idee ist richtig. Aber formal, wie du schon sagtest, nicht. Bei solchen einfachen beweisen kommt es aber gerade darauf an, den Beweis formal richtig aufzuschreiben.

23.05.2008 10:40

Nehmen Sie Tobias in Ihre Freundesliste auf

g0ju
Grünschnabel

Dabei seit: 22.05.2008
Beiträge: 2

kannst du mir vielleicht zeigen, wie ich es richtig aufschreibe bzw. kennst du eine seite im internet, auf der erklärt wird, wie man an solche beweise herangeht?
ich muss ehrlich sagen, dass ich bis zu dieser aufgabe noch nie irgendwo irgendwas beweisen musste.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von g0ju: 23.05.2008 11:43.

23.05.2008 11:40

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Ganz allgemein: Du sollst hier eine Mengengleichheit zeigen. Mengengleichheiten zeigt man in fast allen Fällen, in dem man beide Inklusionen beweist. D.h. für die Mengen M und N gilt:

$[latex]M = N \iff M \subseteq N \text{ und } N \subseteq M[/latex]$
Eine Inklusionsbeziehung $[latex]M \subseteq N[/latex]$ zeigt man, in dem man beweist: $[latex]x \in M \Rightarrow x \in N[/latex]$ . Analog zeigt man $[latex]N \subseteq M[/latex]$ durch $[latex]x \in N \Rightarrow x \in M[/latex]$ . Kann man eine Argumentationskette finden, die nicht nur Folgerungen sondern Äquivalenzen benutzt, also $[latex]x \in N \iff x \in M[/latex]$ , so hat man [latex]M = N[/latex]

in einem Schritt erledigt. Und genau das tun wir in deinem Fall:

Zu zeigen: $[latex](L_1 \circ L_2)^R = L_2^R \circ L_1^R[/latex]$

Es sei $[latex]x \in (L_1 \circ L_2)^R[/latex]$
$[latex]\iff \text{ es gibt } v=v_1\ldots v_s \in L_1, w=w_1\ldots w_k \in L_2[/latex]$ mit [latex]x = (vw)^R[/latex]

$[latex]\iff \text{ es gibt } u \in L_2, q \in L_1[/latex]$ mit $[latex]x = u^Rq^R \quad (\ast) [/latex]$
$[latex]\iff x \in L_2^R \circ L_1^R[/latex]$

Die Stelle (*) bedarf natürlich einer weitere Ausführung:

$[latex]x = (vw)^R = (v_1\ldots v_s w_1 \ldots w_k)^R = w_k \ldots w_1 v_s \ldots v_1 = w^R v^R[/latex]$ , setze also [latex]u:=w, q:=v[/latex]

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tobias: 23.05.2008 15:59.

23.05.2008 15:59

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale sprachen