Äquivalenzrel. / Ordnungsrel. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Sei $G = (N, T, P, S)$ eine kontextfreie Grammatik. Auf $N$ ist die Relation [mm] \sim [/mm] definiert vermöge
$X [mm] \sim [/mm] Y [mm] :\gdw [/mm] X [mm] \xrightarrow\* [/mm] Y [mm] \wedge [/mm] Y [mm] \xrightarrow\* [/mm] X$.
sowie auf [mm] $N/\sim$ [/mm] die Relation [mm] \rightsquigarrow [/mm] vermöge
$A [mm] \rightsquigarrow [/mm] B [mm] :\gdw \exists [/mm] X [mm] \in [/mm] A, [mm] \exists [/mm] Y [mm] \in [/mm] B$ mit $(X,Y) [mm] \in [/mm] P$.
Zeigen Sie, dass [mm] \sim [/mm] eine Äquivalenzrelation und [mm] \rightsquigarrow\* [/mm] eine Ordnungsrelation ist. [mm] (\rightsquigarrow\* [/mm] ist die reflexiv transitive Hülle von [mm] \rightsquigarrow [/mm] .) |
Hallo,
hat jmd eine Idee, wie man an diese Aufgabe rangehen könnte? Ich habe so garkeinen Plan und ich muss auch zugeben, dass beweisen nicht gerade zu meinen Stärken zählt.^^
Danke schonmal und nachträglich noch Frohe Weihnachten. =)
glg
Kalia
|
|
| |
|
Hallo Kalia,
nur eine Idee, um mal mit dem ersten Teil anzufangen:
> Sei [mm]G = (N, T, P, S)[/mm] eine kontextfreie Grammatik. Auf [mm]N[/mm] ist
> die Relation [mm]\sim[/mm] definiert vermöge
> [mm]X \sim Y :\gdw X \xrightarrow\* Y \wedge Y \xrightarrow\* X[/mm].
>
> sowie auf [mm]N/\sim[/mm] die Relation [mm]\rightsquigarrow[/mm] vermöge
> [mm]A \rightsquigarrow B :\gdw \exists X \in A, \exists Y \in B[/mm]
> mit [mm](X,Y) \in P[/mm].
>
> Zeigen Sie, dass [mm]\sim[/mm] eine Äquivalenzrelation und
> [mm]\rightsquigarrow\*[/mm] eine Ordnungsrelation ist.
> [mm](\rightsquigarrow\*[/mm] ist die reflexiv transitive Hülle von
> [mm]\rightsquigarrow[/mm] .)
>
> Hallo,
>
> hat jmd eine Idee, wie man an diese Aufgabe rangehen
> könnte? Ich habe so garkeinen Plan und ich muss auch
> zugeben, dass beweisen nicht gerade zu meinen Stärken
> zählt.^^
Um den ersten Teil zu zeigen, musst du ja zeigen, dass [mm]\sim[/mm]
1) reflexiv
2) symmetrisch
3) transitiv
ist.
Mal zu 3):
Nimm dir Nichtterminale [mm]X,Y,Z[/mm] her mit [mm]X\sim Y[/mm] und [mm]Y\sim Z[/mm]
Dann ist nach Def. ([mm]X\overset{\star}{\rightarrow} Y[/mm] und [mm]Y\overset{\star}{\rightarrow} X[/mm]) und ([mm]Y\overset{\star}{\rightarrow} Z[/mm] und [mm]Z\overset{\star}{\rightarrow} Y[/mm])
Also [mm]X\overset{\star}{\rightarrow} Y \overset{\star}{\rightarrow} Z[/mm] und [mm]Z\overset{\star}{\rightarrow} Y \overset{\star}{\rightarrow} X[/mm]
Dh. [mm]X\overset{\star}{\rightarrow} Z[/mm] und [mm]Z\overset{\star}{\rightarrow} X[/mm]
Damit [mm]X\sim Z[/mm]
1) und 2) sollten nicht schwer sein
>
> Danke schonmal und nachträglich noch Frohe Weihnachten.
Dir auch!
> =)
>
> glg
> Kalia
Gruß
schachuzipus
|
|
|
| |
|
Hallo und danke dir schonmal.^^
Wäre das für die Reflexivität und die Symmetrie jetzt so brauchbar?
reflexiv: $X [mm] \sim [/mm] X$
* wähle NTe $X$ und $Y$ mit $X [mm] \sim [/mm] X$ und $Y [mm] \sim [/mm] Y$
* es gilt : $X [mm] \xrightarrow\* [/mm] X$ und $Y [mm] \xrightarrow\* [/mm] Y$
[mm] \Rightarrow [/mm] jedes NT steht zu sich selbst in Relation
* dann gilt: $X [mm] \sim [/mm] Y$
symmetrische: $X [mm] \sim [/mm] Y$ [mm] \Rightarrow [/mm] $Y [mm] \sim [/mm] X$
* nach Def. bereits gegeben: $X [mm] \xrightarrow\* [/mm] Y$ [mm] \wedge [/mm] $Y [mm] \xrightarrow\* [/mm] X$
[mm] \Rightarrow [/mm] $X [mm] \sim [/mm] Y$ [mm] \Rightarrow [/mm] $Y [mm] \sim [/mm] X$
[mm] \Rightarrow [/mm] Symmetrie
Danke schonmal/nochmal.^^
|
|
|
| |
|
Hallo,
> Wozu brauchst du $Y$?
Das liegt daran, dass ich immer denke ich müsste alle NTs in dem Fall verwenden, ohne zu berücksichtigen, dass das X ja quasie nur als "Stellvertreter" für alle NTs steht.^^
Danke dir schonmal für diesen ersten Teil der Aufgabe. =)
War ja doch nicht so schwer, wie ich mal wieder dachte.^^
Wie kann ich denn jetzt an den Teil mit der Ordnungsrelation rangehen?
lg
Kalia
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Sa 31.12.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Do 29.12.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
