Ich hätte da eine Frage zum Satz von Immermann und Szelepczényi von S.50 im Skript von Vollmer:
Im Algorithmus zum Beweis steht folgendes:
|
Source code
|
1
2
3
4
5
6
7
|
For all K mit Platz s do
begin
rate nichtdeterministisch (a) oder (b)
(a) falls sich K in t Schritten aus K_start ableiten läßt m=m+1;
(b) mache nichts;
end
if m!=n then ablehnen...
|
Es werden also genau die n Konfigurationen geraten, die sich in t Berechnungsschritten ergeben können.
Wo liegt denn das Problem wenn ich das deterministisch mache?? Einfach:
|
|
Source code
|
1
2
3
4
5
6
7
8
9
|
For all K mit Platz s solange m<n do
begin
falls sich K in t Schritten aus K_start ableiten läßt m=m+1;
end
...
|
Der Platzbedarf wird doch dadurch nicht größer, oder? Und die Zeit ist einem doch hier egal.
Ich habe den Eindruck, dass ich da was entscheidendes nicht verstanden habe.
Wäre für klährende Erläuterung sehr dankbar.
Gruß,
Brötchen
Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Kernkompetenzbereiche Master-Studium (IS, MMK, NVS, SE, Sys, ThI)
Frage zum Skript Formale Sprachen
