Linguagem infinita vs. linguagem finita

Não estou claro sobre o uso das frases "infinito" ou "finito" na teoria dos computadores.

Penso que a raiz do problema é que uma linguagem como $L=\{ab\}^*$ é infinita no sentido de poder gerar um número infinito (mas contável) de seqüências de caracteres. No entanto, ainda pode ser reconhecido por um autômato de estado finito .

Também não ajuda que o livro Sipser não faça essa distinção (pelo menos até onde eu sei). Uma pergunta sobre idiomas infinitos / finitos e sua relação com idiomas regulares surgiu em um exame de amostra.

Oh meu. Isso parece uma confusão causada pela terminologia (da velha escola) da "linguagem do estado finito" como sinônimo do que hoje é conhecido como "linguagem regular".

De qualquer forma, as definições padrão para finito / infinito aceitas atualmente consideram apenas o tamanho da linguagem:

1. uma linguagem finita é qualquer conjunto de strings, de cardinalidade finita, | L | < ∞ .$L$$|L|<\infty$
2. uma linguagem infinita é qualquer conjunto de strings, de infinita ( ℵ 0 ) cardinalidade | L | = ∞ .$L$$\aleph_0$$|L|=\infty$

Um finito é sempre regular.$L$

Um infinito pode ser regular (às vezes chamado de "estado finito"), decidível (às vezes chamado de "recursivo"), não regular (estado de não finito), não decidível etc.,$L$

Um idioma é um conjunto de strings. É finito se tiver um número finito de strings nele.

Não estou claro sobre o uso das frases "infinito" ou "finito" na teoria dos computadores.

Penso que a raiz do problema é que uma linguagem como é infinita no sentido de poder gerar um número infinito (mas contável) de seqüências de caracteres. No entanto, ainda pode ser reconhecido por um autômato de estado finito.$L=\{ab\}^∗$

Outra questão é que a teoria formal da linguagem é bastante peculiar na forma como usa o termo "linguagem".

Para todos neste mundo, exceto as pessoas na teoria formal da linguagem, uma linguagem é um sistema de enunciados usado para se comunicar, de modo que cada enunciado tem uma forma (sua sintaxe ) e algum tipo de significado (sua semântica ). A teoria formal da linguagem, pelo menos a parte usada na ciência da computação, é dedicada ao problema de como definir melhor formalmente a sintaxe das linguagens. É tudo sobre o relacionamento entre a sintaxe das línguas (como são as expressões) e os formalismos (línguas!), Como expressões regulares usadas para definir a sintaxe das línguas.

Portanto, na teoria formal da linguagem, "uma linguagem" é definida simplesmente como "um conjunto de strings". Normalmente, não atribui significados às seqüências de caracteres no idioma.

Ao mesmo tempo, os formalismos usados ​​para descrever linguagens, como expressões regulares, também formam linguagens nesse sentido: por exemplo, toda expressão regular é uma string e, portanto, o conjunto de expressões regulares é uma linguagem. No entanto, para estes formalismos, as cordas na língua Do têm um significado: por exemplo, o significado de cada expressão regular é a linguagem que denota.

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

$\{ab\}^*$${}^*$$L$$L$$L$$L$$\{ab\}^*$$\{ \epsilon, ab, abab, ababab, abababab, \ldots \}$${}^*$$\{ab\}^*$

$(ab)^*$${}^*$

$(ab)^*$