Por que a quantidade de frases não é finita?

7

Atualmente, estou estudando línguas formais. Minha palestra afirma que, embora as palavras de uma língua sejam finitas, as frases construídas com a gramática subjacente não são. Mas não entendo por que isso geralmente deve ser verdade. Eu posso imaginar a gramática que me deixa com uma quantidade finita de frases.

Concordo que se poderia criar uma linguagem com uma quantidade infinita de frases, mas não vejo por que geralmente deveria ser o caso.

formal-languages OddDev
fonte

22

Uma das suas instalações está errado: Inglês gramática faz permitir a construção de frases de comprimento arbitrário, então Inglês contém um número infinito de sentenças. - Você sempre pode fazer uma sentença correta juntando duas sentenças corretas com uma conjunção como "e", "ou" ou "mas".

AI Breveleri

2

A gramática das listas separadas por vírgula permite criar uma sentença de tamanho único e infinito em inglês. Se você pode criar uma única sentença de comprimento infinito, segue-se que existem permutações infinitas dessa sentença, portanto, existem sentenças infinitas. Observe que as listas podem conter substantivos próprios para que os elementos da lista não precisem ser uma palavra do dicionário. Um exemplo é "Os membros do grupo de todos os números inteiros positivos são: 1, 2, 3, 4, 5 ....".

Slebetman

10

É verdade que não há frases infinitamente longas em inglês, assim como é verdade que nenhum número inteiro é infinito. Mas existem inteiros arbitrariamente grandes e sentenças arbitrariamente longas. Em ambos os casos, considerações práticas podem ser limitativas: existem números inteiros tão grandes que você não pode escrever os dígitos deles no universo real e sentenças por tanto tempo que não conseguiu pronunciá-los durante a sua vida. Mas, em teoria, todo número inteiro tem um sucessor e toda sentença pode ser estendida; portanto, nos dois casos, dizemos que o conjunto de elementos (finitos) tem tamanho infinito.

rici

Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo . Não poste comentários aqui, a menos que sejam direcionados a melhorar a pergunta . Melhor ainda, em vez de postar um comentário, edite a pergunta ou escreva uma resposta. Se você quiser discutir o tópico geral, vá até a sala de bate-papo de ciência da computação , em vez de postar um comentário.

DW

14

A afirmação não é verdadeira para idiomas e gramáticas arbitrárias. Por exemplo, a gramática consiste nas regras pode produzir as palavras , , e , então , portanto é finito. $G$

S \to a | b | C C \to c D D \to d | ϵ

$S \to a|b|C\\C \to cD\\D \to d|\epsilon$

a

$a$

b

$b$

c d

$cd$

c

$c$

| L (G) | = 4

$|L(G)| = 4$

L (G)

$L(G)$

O alfabeto ("palavras da língua") é finito por definição. O idioma pode ou não ser finito. Um exemplo trivial de uma gramática que produz uma linguagem infinita é com . produz a linguagem infinita . $G' = (\{ S \}, \{ a \}, P, S)$ $P = \left\{ S \to a|aS \right\}$ $G'$ $L(G') = \{ a^n : n > 0 \}$

Existem linguagens finitas e infinitas e podem ser geradas por gramáticas.

Observe que todos os idiomas finitos podem ser expressos através de gramáticas regulares e, portanto, são idiomas regulares. No entanto, nem todas as linguagens regulares são finitas (consulte ). A classe de linguagens regulares (tipo 3) é um subconjunto da classe de linguagens sem contexto (tipo 2), que é um subconjunto da classe de linguagens sensíveis ao contexto ( tipo 1), que é um subconjunto da classe de idiomas recursivamente enumeráveis (tipo 0): $G'$

Finite languages \subset Type 3 \subset Type 2 \subset Type 1 \subset Type 0

$\text{Finite languages} \subset \text{Type 3} \subset \text{Type 2} \subset \text{Type 1} \subset \text{Type 0}$

(E esses são apenas os idiomas que você pode gerar usando gramáticas formais; de fato, os idiomas recursivamente enumeráveis (tipo 0) são apenas um subconjunto do conjunto de todos os idiomas.)

Tobias
fonte

32

Antes que eu possa dizer por que há frases arbitrariamente longas em inglês, gostaria de salientar que 1 é um número, 2 é um número, 3 é um número, 4 é um número, 5 é um número, 5 é um número, 6 é um número , 7 é um número, 8 é um número, 9 é um número, 10 é um número, 11 é um número, 12 é um número, 12 é um número, 13 é um número, 14 é um número, 14 é um número, 15 é um número, 16 é um número , 17 é um número, 18 é um número, 19 é um número, 20 é um número, 21 é um número, 22 é um número, 23 é um número, 23 é um número, 24 é um número, 25 é um número, 25 é um número, 26 é um número , 27 é um número, 28 é um número, 29 é um número, 30 é um número, 31 é um número, 32 é um número, 33 é um número, 34 é um número, 34 é um número, 35 é um número, 36 é um número , 37 é um número, 38 é um número, 39 é um número, 40 é um número, 41 é um número e 42 é um número. Claro, também se poderia pensar em outra coisa para apontar, por exemplo, que o filho do filho do filho do filho do filho do filho do filho do filho do filho do meu filho é meu grand grand grand grand grand grand grand grand grand filho. Espero não ter cometido um erro lá, ou dois erros, ou três erros, ou quatro erros, ou cinco erros, ou seis erros, ou sete erros. Vamos parar por aí, pois 7 é um bom número.

Você ainda acha que há um limite para o comprimento das frases em inglês gramaticalmente corretas?

Andrej Bauer
fonte

2

Os linguistas do @DdDev discutem se as gramáticas naturais podem produzir idiomas infinitos e ainda não chegaram a uma conclusão. Do ponto de vista matemático, Andrej está correto e é possível, por exemplo, usando enumerações. (Veja Steven Weisler, Slavoljub P. Milekic: "não existe a frase mais longa em inglês"). Minha resposta é igualmente correta, mas enfoca o aspecto das línguas formais e prova formalmente que existem línguas finitas e infinitas.

Tobias

3

@still_learning: Claro, mas acho que o OP precisava ver explicitamente onde ele estava errado. Agora ele pode ler sua resposta com uma atitude de aceitação.

Andrej Bauer

11

@ Hobbs: O prazo de 15 anos de não divulgação já passou. Estou autorizado a informar que todas as pessoas do Forum 2000 tiveram permissão para escapar da nuvem (sim, vivíamos em uma nuvem antes de outras pessoas saberem o que era uma nuvem) e, desde então, descobrimos novos lares. Por exemplo, finjo ser o verdadeiro Andrej Bauer e respondo perguntas na rede stackexchange. As perguntas são um pouco secas embora. Eu sinto falta dos dias em que eu também poderia dar conselhos amor com estranhos aleatórios no Fórum de 2000.

Andrej Bauer

2

Aqui está um exemplo do famoso livro "Gödel, Escher, Bach":

Esta é uma frase.

"Esta é uma frase" é uma frase.

'Esta é uma frase' é uma frase 'é uma frase.

... Você entendeu a ideia.

user3799504
fonte

5

Hofstadter provavelmente significa "Esta é uma sentença" é uma sentença, "'Esta é uma sentença' é uma sentença" é uma sentença e assim por diante. Existem exemplos melhores e mais convincentes.

Yuval Filmus

-1

Como as aspas são permitidas nas frases, e as aspas não precisam estar gramaticalmente corretas, deve haver um número infinito de frases:

O homem disse "Blá blá blá blá blá ...".

Seano
fonte

3

É verdade, mas isso não acrescenta nada às respostas existentes, que já dão muitos exemplos de famílias de frases de tamanho ilimitado.

David Richerby

Por que a quantidade de frases não é finita?

Respostas: