Fachrat Informatik - Forum

Negative Zahlen gibt es definitiv nicht.

Und so wie ich das in der Übung heute verstanden habe ist eine Variable, die 0 ist und von der man einen Wert größer 0 abzieht, immer noch 0. In einen Fehler oder so laufen die Programme in diesem Fall nicht.

@compost

wie Joachim schon sagte, negative Zahlen gibt es nicht. null minus fünf ist also immer noch null.

was ich eigentlich sagen wollte: ich weiss nicht genau, wie wichtig es ist, aber lipeck hat am ende der letzten vorlesung erwähnt, dass es nicht ziel der übung sei, einen automaten zu konstruieren, der einfach x0 - x1 berechnet, sondern das goto-programm, so wie es da steht, in einen TA umzubauen.

vielleicht auch nicht so wichtig. trotzdem, wenn jemand interesse an der hausübung hat, kurze mail an mich.

gruß, eike

klar geht das. aber LOOP-programme kennen keine negativen zahlen und ein TA, der auch negative zahlen berechnet, ist nicht äquivalent zu dem LOOP-programm.

Quoted

Original von compost
so. noch mal ne frage: eigentlich sogar zwei:

1. das while programm - kann man das folgendermaßen simpel schreiben:

read (x0, x1)
while x1 ungleich 0 do
x1:=x1-1
x0:=x0-1
endwhile
stop ??
write (x0)

In der Aufgabe war die Konstruktion nach Satz 8.11 gefordert. Und dein Programm hat damit ja nun überhaupt nichts zu tun. Mag zwar wie gewünscht funktionieren, ist aber nicht im Sinne der Aufgabe. Leider.

Quoted

2. über einen kleinen tipp zu aufgabe 2 würde ich mich sehr freuen...

Für jede der beiden Sprachen rausfinden, zu welcher Sprachklasse sie gehört und das dann beweisen:
1. Grammatik angeben oder über Abschlußeigenschaften argumentieren, um zu zeigen, daß die Sprache zu der genannten Sprachklasse gehört.
2. Zeigen, daß die Sprache zu keiner kleineren Klasse gehört (Pumping-Lemma!)

Tip: a) ist kontextfrei, b) ist kontextsensitiv


HTH,
Joachim

noch 'n kleiner tip:

zu a) sprache vereinfachen {a^2n b^n c^m} = {aa}o{a^2y b^y}o{b}o{c}* für y größer oder gleich null (ausnutzung der abschlusseigenschaften)
sieht zwar erstmal wild aus, aber bekannt ist, dass die teilwörter aa , b und c* regulär sind. zu zeigen bleibt dann nur noch, dass das teilwort {a^2y b^y} durch folgende kontextfreie grammatik (produktion!) erzeugt werden kann (S->aaSb|epsilon). damit ist gezeigt, dass auch die ganze sprache L1 mindestens kontextfrei ist. beweis, dass nicht regulär, durch pumping lemma.

zu 2)
WHILE-programm nach satz 8.irgendwas:

(x0 , x1);
xs := 1;
while (xs ungleich 0) do
if (xs = 1) then
if (x1 = 0) then
xs := 5;
else
xs := xs + 1;
endif;
endif;
if (xs = 2) then x1 := x1 – 1; xs := xs + 1; endif;
if (xs = 3) then x0 := x0 – 1; xs := xs + 1; endif;
if (xs = 4) then xs := 1; endif;
if (xs = 5) then xs := 0; endif;
endwhile;
write(x0);

sieht beknackt aus, ist aber original nach vorlesung.

tschuldigung, die erste zeile des WHILE-programms lautet natürlich read (x0,x1);