Aussagenlogik in While-Program < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:20 Mo 22.11.2010 | | Autor: | derda22 |
| Aufgabe | Im Folgenden wird die Syntax einer sehr einfachen Programmiersprache definiert, der so genannten
WHILE-Programme. Die Menge L, die hier definiert wird, ist die Menge aller Zeichenketten
über dem Alphabet A, die syntaktisch korrekte WHILE-Programme sind. Hierbei ist
A := {x, :=,+,−, 6=, ;, while, do, end} [mm] \cup \IN [/mm] , und L ist die folgendermaßen rekursiv definierte
Menge:
Basisregeln: (B1) Für Zahlen i, j, c [mm] \in \IN [/mm] gilt: xi := xj + c [mm] \in [/mm] L.
(B2) Für Zahlen i, j, c [mm] \in \IN [/mm] gilt: xi := xj −c [mm] \in [/mm] L.
Rekursive Regeln: (R1) Sind w1 [mm] \in [/mm] L und w2 [mm] \in [/mm] L, so ist auch w1; w2 [mm] \in [/mm] L.
(R2) Ist w [mm] \in [/mm] L und i [mm] \in \IN, [/mm] so ist while xi 6= 0 do w end [mm] \in [/mm] L.
(a) Welche der folgenden Wörter aus A gehören zu L und welche nicht? Begründen Sie jeweils
Ihre Antwort.
(i) x3 := x3−2
(ii) x7 := 11; x8 := x9 + 10
(iii) while x1 = 0 do x0 := x0 + 1; x1 := x1−1 end
(iv) x1 := x1 + 42; while x1 6= 0 do x1 := x1−1 end |
Die ersten beiden Aufgaben sind ja leicht
(i) richtig, siehe Basisregel 2.
(ii) falsch, B1 und B2 werden von x7 := 11 verletzt
Aber, bei (iii) und (iv) habe ich keine Ahnung, wie ich die rekursiven Regeln anwenden soll, da ích nicht verstehe was es mit w1 und w2 auf sich hat.
was soll denn das bedeuten w1 [mm] \in [/mm] L und w2 [mm] \in [/mm] L . Ich meine was hat das mit while x1 = 0..... zu tun. Was ist denn jetzt w1 und was ist w2?
Hat jemand hier einen Ansatz oder kann mir jemand die rekursiven Regeln hier erklären ??
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo derda22,
> Im Folgenden wird die Syntax einer sehr einfachen
> Programmiersprache definiert, der so genannten
> WHILE-Programme. Die Menge L, die hier definiert wird, ist
> die Menge aller Zeichenketten
> über dem Alphabet A, die syntaktisch korrekte
> WHILE-Programme sind. Hierbei ist
> A := {x, :=,+,−, 6=, ;, while, do, end} [mm]\cup \IN[/mm] , und L
> ist die folgendermaßen rekursiv definierte
> Menge:
> Basisregeln: (B1) Für Zahlen i, j, c [mm]\in \IN[/mm] gilt: xi :=
> xj + c [mm]\in[/mm] L.
> (B2) Für Zahlen i, j, c [mm]\in \IN[/mm] gilt: xi := xj −c [mm]\in[/mm]
> L.
> Rekursive Regeln: (R1) Sind w1 [mm]\in[/mm] L und w2 [mm]\in[/mm] L, so ist
> auch w1; w2 [mm]\in[/mm] L.
> (R2) Ist w [mm]\in[/mm] L und i [mm]\in \IN,[/mm] so ist while xi 6= 0 do
> w end [mm]\in[/mm] L.
> (a) Welche der folgenden Wörter aus A gehören zu L und
> welche nicht? Begründen Sie jeweils
> Ihre Antwort.
> (i) x3 := x3−2
> (ii) x7 := 11; x8 := x9 + 10
> (iii) while x1 = 0 do x0 := x0 + 1; x1 := x1−1 end
> (iv) x1 := x1 + 42; while x1 6= 0 do x1 := x1−1 end
> Die ersten beiden Aufgaben sind ja leicht
> (i) richtig, siehe Basisregel 2.
Korrekt: (i) kann mit (B2) konstruiert werden.
> (ii) falsch, B1 und B2 werden von x7 := 11 verletzt
(ii) kann nicht mit (B1) und (B2) konstruiert werden, aber vielleicht mit (B1),(B2),(R1),(R2)  . Beispielsweise kann [mm] \textbf{x7 := x7 + 11; x8 := x9 - 10} [/mm] auch nicht allein mit (B1),(B2) konstruiert werden, ist aber trotzdem ein WHILE-Programm!
>
> Aber, bei (iii) und (iv) habe ich keine Ahnung, wie ich die
> rekursiven Regeln anwenden soll, da ích nicht verstehe was
> es mit w1 und w2 auf sich hat.
>
> was soll denn das bedeuten w1 [mm]\in[/mm] L und w2 [mm]\in[/mm] L . Ich
> meine was hat das mit while x1 = 0..... zu tun. Was ist
> denn jetzt w1 und was ist w2?
w1 kann jede mit den Regeln konstruierte Zeichenkette (z.B. [mm] \textbf{x3 := x3 - 2}) [/mm] sein.
>
> Hat jemand hier einen Ansatz oder kann mir jemand die
> rekursiven Regeln hier erklären ??
Versuche aus den Regeln die Zeichenketten zu konstruieren, wenn es klappt bist Du fertig, wenn es nicht klappt, versuchst Du zu beweisen, dass es nicht klappen kann.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
LG mathfunnel
|
|
|
|
