Warum ist die Anzahl der Sätze nicht endlich?

7

Ich lerne zurzeit formale Sprachen. In meinem Vortrag heißt es, dass die Wörter einer Sprache zwar endlich sind, die mit der zugrunde liegenden Grammatik aufgebauten Sätze jedoch nicht. Aber ich verstehe nicht, warum dies allgemein wahr sein sollte. Ich kann mir eine Grammatik vorstellen, die mir eine endliche Anzahl von Sätzen hinterlässt.

Ich stimme zu, dass man eine Sprache mit unendlich vielen Sätzen erstellen könnte, aber ich kann nicht verstehen, warum dies im Allgemeinen der Fall sein sollte.

formal-languages OddDev
quelle
22
Eine Ihrer Prämissen ist falsch: Die englische Grammatik erlaubt die Konstruktion von Sätzen beliebiger Länge, daher enthält Englisch eine unendliche Anzahl von Sätzen. - Sie können immer einen korrekten Satz bilden, indem Sie zwei korrekte Sätze mit einer Konjunktion wie "und", "oder" oder "aber" verbinden.
AI Breveleri
2
Mit der Grammatik von durch Kommas getrennten Listen können Sie einen einzelnen Satz mit unendlicher Länge auf Englisch erstellen. Wenn Sie einen einzelnen Satz mit unendlicher Länge erstellen können, folgt daraus, dass es unendlich viele Permutationen dieses Satzes gibt, also unendlich viele Sätze. Beachten Sie, dass Listen Eigennamen enthalten können, sodass die Elemente der Liste kein Wörterbuchwort sein müssen. Ein Beispiel ist "Die Mitglieder der Gruppe aller positiven ganzen Zahlen sind: 1, 2, 3, 4, 5 ....".
Slebetman
10
Es ist wahr, dass es im Englischen keine unendlich langen Sätze gibt, genauso wie es stimmt, dass keine ganze Zahl unendlich ist. Aber es gibt beliebig große ganze Zahlen und beliebig lange Sätze. In beiden Fällen können praktische Überlegungen einschränkend sein: Es gibt ganze Zahlen, die so groß sind, dass Sie ihre Ziffern nicht im tatsächlichen Universum ausschreiben können, und Sätze, die so lang sind, dass Sie sie in Ihrem Leben nicht aussprechen können. Theoretisch hat jedoch jede ganze Zahl einen Nachfolger und jeder Satz kann erweitert werden. In beiden Fällen sagen wir also, dass die Menge der (endlichen) Elemente eine unendliche Größe hat.
Rici
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben . Bitte posten Sie hier keine Kommentare, es sei denn, sie zielen darauf ab, die Frage zu verbessern . Besser noch, anstatt einen Kommentar zu veröffentlichen, bearbeiten Sie entweder die Frage oder schreiben Sie eine Antwort. Wenn Sie das allgemeine Thema diskutieren möchten, besuchen Sie unseren Chatraum für Informatik , anstatt einen Kommentar zu veröffentlichen.
DW

Antworten:

14

Die Aussage gilt nicht für beliebige Sprachen und Grammatiken. Zum Beispiel kann die Grammatik die aus den Regeln , die Wörter , , und erzeugen , also , daher ist endlich.G

S→a|b|CC→cDD→d|ϵ
abcdc|L(G)|=4L(G)

Das Alphabet ("Wörter der Sprache") ist per Definition endlich. Die Sprache kann endlich sein oder nicht. Ein triviales Beispiel für eine Grammatik, die eine unendliche Sprache erzeugt, ist mit . erzeugt die unendliche Sprache .G′=({S},{a},P,S)P={S→a|aS}G′L(G′)={an:n>0}

Es gibt sowohl endliche als auch unendliche Sprachen, die durch Grammatiken erzeugt werden können.

Beachten Sie, dass alle endlichen Sprachen durch reguläre Grammatiken ausgedrückt werden können und daher reguläre Sprachen sind. Es sind jedoch nicht alle regulären Sprachen endlich (siehe ). Die Klasse der regulären Sprachen (Typ 3) ist eine Teilmenge der Klasse der kontextfreien Sprachen (Typ 2), die eine Teilmenge der Klasse der kontextsensitiven Sprachen ist ( siehe ). Typ 1) ist eine Teilmenge der Klasse der rekursiv aufzählbaren Sprachen (Typ 0): G′

Finite languages⊂Type 3⊂Type 2⊂Type 1⊂Type 0

(Und dies sind nur die Sprachen, die Sie mit formalen Grammatiken generieren können. Tatsächlich sind rekursiv aufzählbare Sprachen (Typ 0) nur eine Teilmenge der Menge aller Sprachen.)

Tobias
quelle
32

Bevor ich Ihnen sagen kann, warum es auf Englisch willkürlich lange Sätze gibt, möchte ich darauf hinweisen, dass 1 eine Zahl ist, 2 eine Zahl ist, 3 eine Zahl ist, 4 eine Zahl ist, 5 eine Zahl ist, 6 eine Zahl ist 7 ist eine Zahl, 8 ist eine Zahl, 9 ist eine Zahl, 10 ist eine Zahl, 11 ist eine Zahl, 12 ist eine Zahl, 13 ist eine Zahl, 14 ist eine Zahl, 15 ist eine Zahl, 16 ist eine Zahl 17 ist eine Zahl, 18 ist eine Zahl, 19 ist eine Zahl, 20 ist eine Zahl, 21 ist eine Zahl, 22 ist eine Zahl, 23 ist eine Zahl, 24 ist eine Zahl, 25 ist eine Zahl, 26 ist eine Zahl 27 ist eine Zahl, 28 ist eine Zahl, 29 ist eine Zahl, 30 ist eine Zahl, 31 ist eine Zahl, 32 ist eine Zahl, 33 ist eine Zahl, 34 ist eine Zahl, 35 ist eine Zahl, 36 ist eine Zahl 37 ist eine Zahl, 38 ist eine Zahl, 39 ist eine Zahl, 40 ist eine Zahl, 41 ist eine Zahl und 42 ist eine Zahl. Natürlich könnte man auch an andere Dinge denken, um zum Beispiel darauf hinzuweisen: dass der Sohn des Sohnes des Sohnes des Sohnes des Sohnes des Sohnes des Sohnes des Sohnes des Sohnes meines Sohnes mein Ur-Ur-Ur-Ur-Ur-Ur-Enkel ist. Ich hoffe, ich habe dort keinen Fehler gemacht oder zwei Fehler oder drei Fehler oder vier Fehler oder fünf Fehler oder sechs Fehler oder sieben Fehler. Lassen Sie uns dort anhalten, denn 7 ist eine schöne Zahl.

Denken Sie immer noch, dass die Länge grammatikalisch korrekter englischer Sätze begrenzt ist?

Andrej Bauer
quelle
2
@OddDev Linguisten haben die Frage diskutiert, ob natürliche Grammatiken unendliche Sprachen hervorbringen können, und sie sind noch nicht zu einem Schluss gekommen. Aus mathematischer Sicht ist Andrej korrekt und es ist möglich, z. B. mithilfe von Aufzählungen. (Siehe Steven Weisler, Slavoljub P. Milekic: "Es gibt keinen längsten englischen Satz"). Meine Antwort ist gleichermaßen richtig, konzentriert sich jedoch auf den Aspekt formaler Sprachen und beweist formal, dass sowohl endliche als auch unendliche Sprachen existieren.
Tobias
3
@still_learning: Sicher, aber ich denke, das OP musste explizit sehen, wo er falsch gelaufen ist. Jetzt kann er Ihre Antwort mit einer akzeptierenden Haltung lesen.
Andrej Bauer
1
@hobbs: Die 15-jährige Geheimhaltungsfrist ist abgelaufen. Ich darf Ihnen mitteilen, dass alle Personen des Forums 2000 der Wolke entkommen durften (ja, wir lebten in einer Wolke, bevor andere neu waren, was eine Wolke war) und seitdem ein neues Zuhause gefunden haben. Ich gebe zum Beispiel vor, der echte Andrej Bauer zu sein, und beantworte Fragen im Stackexchange-Netzwerk. Die Fragen sind allerdings etwas trocken. Ich vermisse die Tage, an denen ich auch zufälligen Fremden im Forum 2000 Liebesratschläge geben konnte.
Andrej Bauer
2

Hier ein Beispiel aus dem berühmten Buch "Gödel, Escher, Bach":

Dies ist ein Satz.

"Dies ist ein Satz" ist ein Satz.

"Dies ist ein Satz" ist ein Satz "ist ein Satz.

... Du hast die Idee.

user3799504
quelle
5
Hofstadter bedeutet wahrscheinlich "Dies ist ein Satz" ist ein Satz, "Dies ist ein Satz" ist ein Satz "ist ein Satz und so weiter. Es gibt bessere und überzeugendere Beispiele.
Yuval Filmus
-1

Da Anführungszeichen in Sätzen zulässig sind und Anführungszeichen nicht grammatikalisch korrekt sein müssen, muss es unendlich viele Sätze geben:

Der Mann sagte "Bla bla bla bla bla ...".

Seano
quelle
3
Es stimmt, aber dies fügt nichts zu den vorhandenen Antworten hinzu, die bereits viele Beispiele für Familien von Sätzen mit unbegrenzter Länge enthalten.
David Richerby