Język nieskończony a język skończony

Nie jestem pewien, czy w teorii komputerowej używa się zwrotów „nieskończony” język lub „skończony” język.

Myślę, że źródłem problemu jest to, że język taki jak jest nieskończony w tym sensie, że może wygenerować nieskończoną (ale policzalną) liczbę łańcuchów. Jednak nadal może być rozpoznany przez automat skończony .$L=\{ab\}^*$

Nie pomaga też fakt, że książka Sipser tak naprawdę nie czyni tego rozróżnienia (przynajmniej o ile wiem). Pytanie o nieskończone / skończone języki i ich związek z językami zwykłymi pojawiło się na przykładowym egzaminie.

O mój. Wydaje się, że jest to zamieszanie spowodowane (starą szkołą) terminologią „języka skończonego” jako synonimu tego, co jest dziś znane jako „język regularny”.

W każdym razie standardowe definicje skończone / nieskończone przyjęte obecnie dotyczą tylko rozmiaru języka:

1. skończony język jest dowolny zestaw ciągów, o skończonej liczności, | L | < ∞ .$L$$|L|<\infty$
2. nieskończony język jest dowolny zestaw ciągów nieskończonych ( ℵ 0 ) liczności | L | = ∞ .$L$$\aleph_0$$|L|=\infty$

Skończony jest zawsze regularny.$L$

Nieskończony może być regularny (czasem nazywany „stanem skończonym”), rozstrzygalny (czasem nazywany „rekurencyjnym”), nieregularny (stan nieskończony), nierozstrzygalny itp.,$L$

Język to zestaw ciągów znaków. Jest skończony, jeśli ma skończoną liczbę łańcuchów.

Nie jestem pewien, czy w teorii komputerowej używa się zwrotów „nieskończony” język lub „skończony” język.

Myślę, że źródłem problemu jest to, że język taki jak jest nieskończony w tym sensie, że może wygenerować nieskończoną (ale policzalną) liczbę łańcuchów. Jednak nadal może być rozpoznany przez automat skończony.$L=\{ab\}^∗$

Inną kwestią jest to, że formalna teoria języka jest dość osobliwa w tym, jak używa terminu „język”.

Dla każdego na tym świecie, z wyjątkiem osób posiadających formalną teorię języka, język jest systemem wypowiedzi używanych do komunikacji, więc każda wypowiedź ma formę (swoją składnię ) i jakieś znaczenie ( semantykę ). Formalna teoria języka, przynajmniej część wykorzystywana w informatyce, poświęcona jest problemowi, jak najlepiej formalnie zdefiniować składnię języków. Chodzi przede wszystkim o związek między składnią języków (jak wyglądają wypowiedzi) a formalizmami (językami!), Takimi jak wyrażenia regularne używane do definiowania składni języków.

Dlatego w formalnej teorii języka „język” definiuje się po prostu jako „zbiór ciągów znaków”. Zazwyczaj nie przypisuje znaczenia ciągom w języku.

Jednocześnie formalizacje używane do opisu języków, takie jak wyrażenia regularne, również tworzą języki w tym sensie: na przykład każde wyrażenie regularne jest ciągiem znaków, a zatem zbiór wyrażeń regularnych jest językiem. Jednak dla tych formalizmów, komunikaty w języku zrób mają znaczenie: na przykład, znaczenie każdego wyrażenia regularnego jest językiem to oznacza.

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

$\{ab\}^*$. The operator ${}^*$ denotes a function that maps languages to languages: it maps each language $L$ to the language consisting of all strings that consist of a string in $L$ zero or more times repeated. If $L$ is the empty language, the result is $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.