Questão 2876695

• Banca: FCM
• Órgão: IFN-MG
• Ano: 2018
• Provas: FCM - 2018 - IFN-MG - Ciências da Computação: Teoria da Computação
• Disciplina: Programação
• Assuntos: Conceitos básicos de programação

Sobre o Teorema do Bombeamento para linguagens regulares, é INCORRETO afirmar que

• A. se uma linguagem L não é regular, pode-se demonstrar que de fato L não é regular, utilizando-se o Teorema do Bombeamento.
• B. para toda linguagem regular L e toda palavra suficientemente grande pertencente a L, é possível afirmar que há um trecho desta palavra que pode ser repetido quantas vezes desejarmos para se obterem outras palavras de L.
• C. o Teorema do Bombeamento pode ser utilizado para mostrar que a linguagem L, composta por palavras cujo comprimento é um número primo, não é regular.
• D. o enunciado do Teorema do Bombeamento possui diversos quantificadores lógicos, sendo eles existenciais e universais.
• E. o Teorema do Bombeamento pode ser utilizado para mostrar que a linguagem composta por palavras formadas por uma quantidade qualquer de 0’s, seguida da mesma quantidade de 1’s, não é regular.

Gabarito: A

Comentários

• As aplicações típicas do Teorema do Bombeamento dizem respeito a (tentar) provar que uma determinada linguagem não é regular. Deve-se notar, entretanto que o Teorema diz que TODA linguagem regular possui a propriedade do bombeamento, em geral o inverso não é verdadeiro (questão de Lógica). Assim, nem sempre é possível provar que uma linguagem NÃO é regular via Teorema do Bombeamento!

  Por isso a alternativa A já está errada logo de cara!

  Agora, convenhamos... Para que uma questão complexa dessa num Concurso? Será que a vaga é para um Cientista da NASA??? Trabalho há mais de 20 anos na área de Desenvolvimento e NUNCA vi alguém usar ou apenas comentar algo sobre o assunto...