Quiz - Lema do Bombeamento

O Lema de Bombeamento para Linguagens Regulares tem como objetivo:

• Provar que uma Linguagem é regular

• Provar que uma Linguagem não é regular

• Verificar se uma Linguagem possui ciclos

• Verificar se um Linguagem é finita

Como mencionado na vídeo aula, existem dois tipos do Lema do Bombeamento. Quais são esses tipos?

• Lema do Bombeamento para Linguagens Regulares e Linguagens Sensíveis ao Contexto

• Lema do Bombeamento para Linguagens Infinitas e LInguagens Livres do Contexto

• Lema do Bombeamento para Linguagens Regulares e Linguagens Infinitas

• Lema do Bombeamento para Linguagens Regulares e Linguagens Livres do Contexto

Assumindo que um Linguagem A é regular, assinale a opção incorreta:

• a

• Toda cadeia 's' da Linguagem A 'pode ser decomposta em 3 partes (xyz) desde que |s| ≥ p

• Toda cadeia 's' da Linguagem A 'pode ser decomposta em 3 partes (xyz) desde que |s| < p

• A cadeia 's' pode ser dividida em xyz

• Toda Linguagem Regular satisfaz o Lema do Bombeamento

Tomando em conta uma Linguagem Regular A, aprendemos que ela pode ser decomposta em s = x(y^i)z
O que representa a letra 'i' ?

• O número de caracteres que ela gera

• A linguagem não é regular

• O número de ciclos que a cadeia possui

• O número de vezes que a cadeia pode ser decomposta

Considere uma máquina de estados finitos com 10 estados. Qual é o tamanho da cadeia mais longa que podemos construir sem que haja um ciclo?

• 8

• 9

• 10

• 11

• 12

Dada a linguagem A={0^m 1^n ∶m > n ≥ 0}. Sendo p ≥ 1 o tamanho do bombeamento e considerando a cadeia s = 0^(p+1) 1^p. Qual das seguintes divisões de s em xyz garante que a linguagem seja regular:

Ainda para a linguagem descrita no exercício anterior, sabemos que podemos escrever s como xy^(i)z para todo i ≥ 0. Dado que x = λ, y = 0^p, z = 01^p. Qual das alternativas abaixo contém um valor para i que gere uma cadeia que não está contida em A?

• i = 1

• i = 2

• i = 0

• i = 5

Dada a linguagem A = { (1^n²) : n ≥ 0 }. Utilizando o Lema do Bombeamento, podemos dizer sobre essa linguagem que:

• Ela é regular.

• Ela não é regular.

• Nada se pode concluir sobre essa linguagem utilizando apenas esse lema.