Prova de Não Regularidade

Prévia do material em texto

Elaborar um AF pode tomar muito tempo, dependendo da complexidade do problema para o qual será desenvolvido. No entanto, devido a sua simplicidade, as linguagens regulares produzem soluções eficientes em termos de tempo de processamento a partir de soluções também muito simples. Desse modo, vale ressaltar que, se há a possibilidade de obter uma solução ótima para determinado problema, esta deverá ser utilizada.
Tendo em vista o apresentado, torna-se importante verificar se é possível obter uma solução por meio de uma linguagem regular. Isso posto, o lema do bombeamento consiste em uma importante ferramenta que tem o intuito de possibilitar, por meio de uma prova por contradição, a verificação da não regularidade de uma linguagem, ou seja, por meio dele, é possível determinar se dada linguagem faz parte da classe 3 na hierarquia de Chomsky. Logo, com o seu uso, pode-se saber de forma simples se é possível fazer uso de uma linguagem regular para determinada aplicação ou se será necessário utilizar uma linguagem mais complexa, o que poderá demandar maior poder de processamento.
O lema do bombeamento é um teorema muito simples, com base no princípio da casa dos pombos. Esse lema faz uso da prova por contradição para verificar se dada linguagem não é regular. Desse modo, torna-se uma excelente ferramenta a ser usada com o intuito de verificar se uma linguagem do tipo 3, ou seja, se uma linguagem regular pode ser a solução para determinado problema. Salienta-se que as linguagens regulares, apesar de sua simplicidade, são utilizadas em diversas ferramentas atuais ou serviram como base para elas. São exemplos de aplicações de linguagens regulares alguns analisadores léxicos utilizados em linguagens de programação, portas automáticas, sensores de presença, entre outros
Verifique se a linguagem apresentada faz parte do grupo das linguagens regulares. Para isso, use o lema do bombeamento para provar se a linguagem é não regular.
Padrão de resposta esperado
Suponha que L é uma linguagem regular.
Desse modo, existe um tamanho do bombeamento p de forma que, para uma cadeia escolhida w =10p10p1, com |w| >= p, poderá ser bombeada.
Considerando que w pode ser dividida em xyz e que xyz, para qualquer i >= 0, deverá pertencer a L, isto é, w = xyz∈ L, ∀ i >= 0.
Isso posto, para um |y| > 0, consideramos dois casos:
y contém apenas 0’s.
Nesse caso, a cadeia xyyz conterá uma quantidade diferente de 0’s, o que quebra a regra 1 do lema do bombeamento, pois não fará parte de L e verifica-se que a segunda avaliação não foi realizada na metade do processo do estágio.
y contém 10.
Nesse caso, ao bombear y, teremos cadeias que também não farão parte de L, pois teríamos três agrupamentos de 0’s em vez de dois, como solicitado por L. Quanto ao processo de estágio, verifica-se, nesse caso, que foram realizadas mais de três avaliações, diferente do padrão utilizado pela empresa.
Logo, como, em ambos os casos, xyyz não pertence à linguagem L, temos uma contradição, o que prova que L não é regular
image1.jpeg