Unendliche Sprache vs. endliche Sprache

Mir ist nicht klar, wie die Ausdrücke "unendliche" Sprache oder "endliche" Sprache in der Computertheorie verwendet werden.

Ich denke , die Wurzel des Übels ist , dass eine Sprache wie $L=\{ab\}^*$ ist unendlich in dem Sinne , dass es eine unendliche erzeugen kann (aber zählbare) Anzahl der Saiten. Dennoch kann es von einem Automaten mit endlichen Zuständen erkannt werden .

Es hilft auch nicht, dass das Sipser-Buch diese Unterscheidung nicht wirklich trifft (zumindest soweit ich das beurteilen kann). Eine Frage zu unendlichen / endlichen Sprachen und ihrer Beziehung zu regulären Sprachen kam in einer Beispielprüfung auf.

Oh mein. Dies scheint eine Verwirrung zu sein, die durch die (alte Schule) Terminologie der "endlichen Staatssprache" als Synonym für das, was heute als "reguläre Sprache" bekannt ist, verursacht wird.

Wie auch immer, die Standarddefinitionen für endlich / unendlich, die heutzutage akzeptiert werden, berücksichtigen nur die Größe der Sprache:

1. eine endliche Sprache ist jede Menge von Zeichenketten, von endlicher Kardinalität, | L | < ∞ .$L$$|L|<\infty$
2. eine unendliche Sprache ist jede Menge von Zeichenketten mit unendlicher ( ℵ 0 ) Kardinalität | L | = ∞ .$L$$\aleph_0$$|L|=\infty$

Ein endliches ist immer regulär.$L$

Ein unendliches kann regulär (manchmal als "endlicher Zustand" bezeichnet), entscheidbar (manchmal als "rekursiv" bezeichnet), nicht regulär (nicht endlicher Zustand), nicht entscheidbar usw. sein.$L$

Eine Sprache ist eine Reihe von Zeichenfolgen. Es ist endlich, wenn es eine endliche Anzahl von Zeichenketten enthält.

Mir ist nicht klar, wie die Ausdrücke "unendliche" Sprache oder "endliche" Sprache in der Computertheorie verwendet werden.

Ich denke, die Wurzel des Problems ist, dass eine Sprache wie unendlich ist, in dem Sinne, dass sie eine unendliche (aber abzählbare) Anzahl von Zeichenfolgen erzeugen kann. Dennoch kann es von einem Automaten mit endlichen Zuständen erkannt werden.$L=\{ab\}^∗$

Ein weiteres Problem ist, dass die formale Sprachtheorie in Bezug auf die Verwendung des Begriffs "Sprache" ziemlich eigenartig ist.

Für alle Menschen auf dieser Welt, mit Ausnahme der Menschen in der formalen Sprachtheorie, ist eine Sprache ein System von Äußerungen, mit denen kommuniziert wird. Jede Äußerung hat also eine Form (ihre Syntax ) und eine Art Bedeutung (ihre Semantik ). Die formale Sprachtheorie, zumindest der Teil, der in der Informatik verwendet wird, befasst sich mit der Frage, wie die Syntax von Sprachen formal am besten definiert werden kann . Es geht um die Beziehung zwischen der Syntax von Sprachen (wie die Äußerungen aussehen) und Formalismen (Sprachen!) Wie regulären Ausdrücken, mit denen die Syntax von Sprachen definiert wird.

Daher wird in der formalen Sprachtheorie "eine Sprache" einfach als "eine Menge von Zeichenfolgen" definiert. Normalerweise werden den Zeichenfolgen in der Sprache keine Bedeutungen zugewiesen.

Gleichzeitig bilden die zur Beschreibung von Sprachen verwendeten Formalismen wie reguläre Ausdrücke auch Sprachen in diesem Sinne: Beispielsweise ist jeder reguläre Ausdruck eine Zeichenfolge, und daher ist die Menge regulärer Ausdrücke eine Sprache. Für diese Formalismen haben die Zeichenfolgen in der Sprache jedoch eine Bedeutung: Beispielsweise ist die Bedeutung jedes regulären Ausdrucks die Sprache, die sie kennzeichnet.

$ab$$\{ab\}$$ab$$ab$$\{ab\}$

$\{ab\}^*$${}^*$$L$$L$$L$$L$; in all other cases, the result is an infinite language. For instance, $\{ab\}^*$ is the language $\{ \epsilon, ab, abab, ababab, abababab, \ldots \}$. It is infinite, but using the operator ${}^*$, we can describe it in a finite way, as $\{ab\}^*$.

Furthermore, we can use a regular expression to describe this language, namely $(ab)^*$. Like all regular expressions, this is a finite string, but like most regular expressions that contain the ${}^*$ operator, it describes an infinite language.

Whenever a text on formal languages uses an expression such as $(ab)^*$ that denotes a language, ask yourself whether it is discussing the regular expression itself (e.g. how it is constructed, which language it denotes, etc.) or whether it merely uses the regular expression to refer to the language being denoted.