Langage infini vs langage fini

Je ne suis pas certain de l'utilisation des expressions langage "infini" ou langage "fini" en théorie informatique.

Je pense que la racine du problème est qu'un langage comme est infini dans le sens où il peut générer un nombre infini (mais dénombrable) de chaînes. Pourtant, il peut encore être reconnu par un automate à états finis .$L=\{ab\}^*$

Cela n'aide pas non plus que le livre Sipser ne fasse pas vraiment cette distinction (du moins pour autant que je sache). Une question sur les langues infinies / finies et leur relation avec les langues normales a été posée dans un exemple d'examen.

Oh mon. Cela semble être une confusion causée par la terminologie (ancienne école) du "langage à états finis" comme synonyme de ce que l'on appelle aujourd'hui le "langage régulier".

Quoi qu'il en soit, les définitions standard pour fini / infini acceptées de nos jours ne concernent que la taille de la langue:

1. un langage fini est tout ensemble de chaînes, de cardinalité finie, | L | < ∞ .$L$$|L|<\infty$
2. un langage infini est tout ensemble de chaînes, de cardinalité infinie ( ℵ 0 ) | L | = ∞ .$L$$\aleph_0$$|L|=\infty$

Un fini est toujours régulier.$L$

Un infini peut être régulier (parfois appelé "état fini"), décidable (parfois appelé "récursif"), non régulier (état non fini), non décidable, etc.,$L$

Une langue est un ensemble de chaînes. Il est fini s'il contient un nombre fini de chaînes.

Je ne suis pas certain de l'utilisation des expressions langage "infini" ou langage "fini" en théorie informatique.

$L=\{ab\}^∗$

Un autre problème est que la théorie formelle du langage est plutôt particulière dans la façon dont elle utilise le terme «langage».

Pour tout le monde dans ce monde, sauf les personnes dans la théorie formelle du langage, un langage est un système d'énoncés utilisés pour communiquer, donc chaque énoncé a une forme (sa syntaxe ) et une sorte de sens (sa sémantique ). La théorie du langage formel, du moins la partie utilisée en informatique, est consacrée au problème de la meilleure définition formelle de la syntaxe des langages. Il s'agit de la relation entre la syntaxe des langues (à quoi ressemblent les énoncés) et les formalismes (langues!) Tels que les expressions régulières utilisées pour définir la syntaxe des langues.

Ainsi, dans la théorie formelle du langage, «un langage» est défini simplement comme «un ensemble de chaînes». Il n'attribue généralement pas de signification aux chaînes de la langue.

Dans le même temps, les formalismes utilisés pour décrire les langues, telles que les expressions régulières, forment également des langues dans ce sens: par exemple, chaque expression régulière est une chaîne et, par conséquent, l'ensemble d'expressions régulières est une langue. Cependant, pour ces formalismes, les chaînes dans la langue do ont un sens: par exemple, la signification de chaque expression régulière est la langue qu'elle désigne.

$ab$$\{ab\}$ est une langue, à savoir la langue constituée de la chaîne $ab$. cependant,$ab$n'est pas seulement une chaîne, mais aussi une expression régulière: un membre de l'ensemble d'expressions régulières valides (qui est une langue). Comme toute expression régulière, elle a un sens: elle désigne une langue, dans ce cas, la langue$\{ab\}$.

Passons maintenant à votre exemple: $\{ab\}^*$. L'opérateur${}^*$ dénote une fonction qui mappe les langues aux langues: il mappe chaque langue $L$ à la langue composée de toutes les chaînes qui se composent d'une chaîne $L$zéro ou plusieurs fois répété. Si$L$ est la langue vide, le résultat est $L$; dans tous les autres cas, le résultat est un langage infini. Par exemple,$\{ab\}^*$ est la langue $\{ \epsilon, ab, abab, ababab, abababab, \ldots \}$. C'est infini, mais en utilisant l'opérateur${}^*$, nous pouvons le décrire de manière finie, comme $\{ab\}^*$.

De plus, nous pouvons utiliser une expression régulière pour décrire ce langage, à savoir $(ab)^*$. Comme toutes les expressions régulières, il s'agit d'une chaîne finie, mais comme la plupart des expressions régulières qui contiennent le${}^*$ opérateur, il décrit un langage infini.

Chaque fois qu'un texte sur les langues formelles utilise une expression telle que $(ab)^*$qui dénote une langue, demandez-vous si elle discute de l'expression régulière elle-même (par exemple, comment elle est construite, quelle langue elle dénote, etc.) ou si elle utilise simplement l'expression régulière pour se référer à la langue dénotée.