grammatiken von Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:24 Fr 13.05.2005 | | Autor: | asudau |
ich habe diese Frage in keinem anderen Forum gestellt
wie lässt sich effizient ermittlen, ob eine durch eine Grammatik erzeugte Sprache unendlich viele Wörter enthält?
Taucht das in irgendwelchen Lehrbüchern auf? Hat man sich da allgemein auf eine bestimmte Vorgehensweise geeinigt oder ist diese Fragestellung komplett neu (bzw. zu unwichtig)?
schöne Grüße von anne
|
|
| |
|
Hallo Anne!
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> wie lässt sich effizient ermittlen, ob eine durch eine
> Grammatik erzeugte Sprache unendlich viele Wörter enthält?
> Taucht das in irgendwelchen Lehrbüchern auf? Hat man sich
> da allgemein auf eine bestimmte Vorgehensweise geeinigt
> oder ist diese Fragestellung komplett neu (bzw. zu
> unwichtig)?
So wie die Frage formuliert ist, ist sie wohl schwer lösbar. Es gibt
nämlich verschiedene Arten von Grammatiken (mit dazugehörigen
Automaten). An der Spitze stehen die Phasenstrukturgrammatiken,
bei deren Produktionen links wie rechts so viele Zeichen wie Du willst stehen können mit der Einschränkung, daß links keine Zeichenketten vorkommen dürfen, die nur aus Terminalen bestehen.
Danach kommen die kontextsensitiven Grammatiken, wo es bei jeder Produktion links weniger Zeichen geben muß als rechts. Danach kommen die kontextfreien Grammatiken und danach die Regulären (kann man ja sicherlich in jedem theo.Inf-Skript nachlesen).
Jedenfalls hatten wir bis zu den kontextfreien Grammatiken folgende Ungleichung kennengelernt:
Sei G eine kontextfreie Grammatik. Dann ist [mm] $L\left(G\right)$ [/mm] genau dann unendlich, wenn [m]\exists z \in L\left(G\right) \exists n \in \IN: 2^{n-1} \le \left|z\right| \le 2^{n-1} + 2^n[/m]. Diese Ungleichung folgt aus dem Pumping Lemma für kontextfreie Sprachen. Ich weiß leider nicht wie man ursprünglich darauf gekommen ist. Und der Beweis ist auch etwas subtil. Er basiert wohl auf der Tatsache, daß es in einer unendlichen Sprache für ein vorgegebenes Wort aus dieser Sprache sich immer ein Wort finden läßt, daß länger ist als das Erste. Danach kann man offensichtlich über die Ableitungsbäume für solche Wörter argumentieren und kommt wohl so auf die obere Abschätzung (wobei man von der Chomsky Normal Form von einer beliebigen ktf. ausgeht).
Für kontextsensitive Grammatiken, die nicht kontextfrei sind(!), wird die Sache schon schwerer. Vor allem gibt es dort ja auch so interessante Probleme wie das Halteproblem auf einem unendlichen Band (Sprachen, die durch solche Grammatiken entstehen, werden nämlich von Turing-Maschinen (speziell: linear beschränkte Turing-Maschinen) erkannt), welches ja unlösbar ist. Außerdem gibt es für solche Grammatik-Formen auch kein Pumping Lemma mehr. Ich bezweifele also, daß es für diese Grammatik-Formen einen Algorithmus geben könnte, der für jede Grammatik entscheiden könnte, ob die Sprache einer solchen Grammatik (un)endlich ist. Das Ganze "rieht" zu stark nach Halteproblem. 
Viele Grüße
Karl
|
|
|
|
