Warum sind While-Programme nicht kontextfrei?
2002-06-22 20:22
mifudd
Hallo allerseits,
wie es der Zufall so will sitze ich vor einem Problem wo ich nicht weiter komme:
—–
Diese Aufgabe soll demonstrieren, daß die Menge
der gängigen Programmiersprachen nicht ganz kontextfrei sind. Mithilfe des Pumping-Lemmas werden wir zeigen, daß ein Aspekt, die Variablendeklaration, nicht kontextfrei behandelt werden kann. Sei L die Menge der Programme, die wie folgt definiert werden:
Ein Programm besteht aus einer Variablendeklaration und einem Programmrumpf.
Eine Variablendeklaration hat die Form VAR Variablenliste;
– VAR ist als ein Zeichen zu lesen.
– Eine Variable beginnt mit dem Zeichen X, gefolgt von einer beliebigen Anzahl von 0 und 1 (etwa: X11101 oder X000).
– Bemerkung: In den Programmiersprachen würde zu jeder Variable auch eine Typdeklaration gehören. Wir tun dies hier nicht der Einfachheit halber.
Der Programmrumpf ist so definiert wie die WHILE-Programme in Theoretischer Informatik 1. Es gibt nur eine Einschränkung: jede Variable, die im Rumpf vorkommt, muss deklariert worden sein!
Zeigen Sie: die Menge der so definierten Programme ist nicht kontextfrei.
—-
Vermutlich muß das Pumpinglemma angwand werden. Kann mir jemand bei der Aufgabe helfen? Ich kann mit dem Pumpinglemma umgehen; aber ich blicke nicht durch. Das küzeste Programm würde doch schon 60 Fallunterscheidungen verursachen? Gibt es vielleicht einen einfacheren Weg?
Viele Grüße
Mike
wie es der Zufall so will sitze ich vor einem Problem wo ich nicht weiter komme:
—–
Diese Aufgabe soll demonstrieren, daß die Menge
der gängigen Programmiersprachen nicht ganz kontextfrei sind. Mithilfe des Pumping-Lemmas werden wir zeigen, daß ein Aspekt, die Variablendeklaration, nicht kontextfrei behandelt werden kann. Sei L die Menge der Programme, die wie folgt definiert werden:
Ein Programm besteht aus einer Variablendeklaration und einem Programmrumpf.
Eine Variablendeklaration hat die Form VAR Variablenliste;
– VAR ist als ein Zeichen zu lesen.
– Eine Variable beginnt mit dem Zeichen X, gefolgt von einer beliebigen Anzahl von 0 und 1 (etwa: X11101 oder X000).
– Bemerkung: In den Programmiersprachen würde zu jeder Variable auch eine Typdeklaration gehören. Wir tun dies hier nicht der Einfachheit halber.
Der Programmrumpf ist so definiert wie die WHILE-Programme in Theoretischer Informatik 1. Es gibt nur eine Einschränkung: jede Variable, die im Rumpf vorkommt, muss deklariert worden sein!
Zeigen Sie: die Menge der so definierten Programme ist nicht kontextfrei.
—-
Vermutlich muß das Pumpinglemma angwand werden. Kann mir jemand bei der Aufgabe helfen? Ich kann mit dem Pumpinglemma umgehen; aber ich blicke nicht durch. Das küzeste Programm würde doch schon 60 Fallunterscheidungen verursachen? Gibt es vielleicht einen einfacheren Weg?
Viele Grüße
Mike