A maior rede de estudos do Brasil

O que é o lema do bombeamento?


1 resposta(s)

User badge image

Juntos somos

Há mais de um mês

O lema do bombeamento para linguagens regulares descreve uma propriedade essencial de todas as linguagens regulares: todas as cadeias suficientemente longas duma dada linguagem regular podem ser "bombeadas", isto é, cada uma dessas cadeias tem uma subcadeia central que pode ser repetida arbitrariamente a fim de produzir uma nova cadeia que também pertence à mesma linguagem.

O lema do bombeamento foi primeiro enunciado por Y. Bar-Hillel, Micha Perles e Eli Shamir em 1961.[1] Ele é útil para provar que uma linguagem não é regular. Há vários outros lemas do bombeamento, todos com objetivos similares

O lema do bombeamento para linguagens regulares descreve uma propriedade essencial de todas as linguagens regulares: todas as cadeias suficientemente longas duma dada linguagem regular podem ser "bombeadas", isto é, cada uma dessas cadeias tem uma subcadeia central que pode ser repetida arbitrariamente a fim de produzir uma nova cadeia que também pertence à mesma linguagem.

O lema do bombeamento foi primeiro enunciado por Y. Bar-Hillel, Micha Perles e Eli Shamir em 1961.[1] Ele é útil para provar que uma linguagem não é regular. Há vários outros lemas do bombeamento, todos com objetivos similares

Essa pergunta já foi respondida por um dos nossos estudantes