3 Trabalho De Teoria Da Computa O

Estudo Sobre o Lema do Bombeamento para
Linguagens Regulares
Alexandre A. Giron

Mauricio Begnini

Paulo Roberto de Oliveira

Mestrado em Ciência da Computação
Departamento de Informática
Universidade Estadual de Maringá
Email: [e-mail]

Mestrado em Ciência da Computação
Departamento de Informática
Universidade Estadual de Maringá
Email: [e-mail]

Mestrado em Ciência da Computação
Departamento de Informática
Universidade Estadual de Maringá
Email: [e-mail]

Resumo—Um Lema interessante da área da Teoria da Computação é o Lema do Bombeamento para Linguagens Regulares, cuja finalidade principal é provar se uma linguagem não é regular. Assim, este artigo discorrerá sobre esse Lema, com base em 3 autores diferentes, bem como mostrar alguns exemplos de aplicação do Lema. Constatou-se que o Lema é uma técnica consolidada e usual para a verificação de que uma linguagem não é regular.

I. I NTRODUÇÃO
As Linguagens Regulares são o tipo mais básico das
Linguagens formais. São bastante úteis em linguagens de programação e análise de entradas, por exemplo, para um compilador. Para que uma linguagem seja dita como regular é necessário verificar se existe um Autômato Finito (AF) que a reconhece [1].
Entretanto, existem outros tipos de linguagens formais.
Dessa forma, pode ser necessário descobrir se uma dada linguagem ou expressão regular que a represente, não é regular.
Se uma linguagem não é regular, ela provavelmente deverá ter maior poder computacional [1].
Outro aspecto importante sobre as linguagens regulares se relaciona com questões de demonstração de decidibilidade dessa classe de linguagens. Considerando esses aspectos, surgiu uma técnica para ajudar no tratamento dessas questões.
Essa técnica é conhecida como "Pumping Lema", ou Lema do Bombeamento para Linguagens Regulares.
O Lema do Bombeamento para Linguagens Regulares, neste trabalho denominado como LBLR, surgiu em 1961 e foi enunciado por Yehoshua Bar-Hillel, Micha