O Lema de Bombeamento para Linguagens Regulares tem como objetivo:
Answer
Provar que uma Linguagem é regular
Provar que uma Linguagem não é regular
Verificar se uma Linguagem possui ciclos
Verificar se um Linguagem é finita
Question 2
Question
Como mencionado na vídeo aula, existem dois tipos do Lema do Bombeamento. Quais são esses tipos?
Answer
Lema do Bombeamento para Linguagens Sensíveis ao Contexto
Lema do Bombeamento para Linguagens Infinitas e Livres do Contexto
Lema do Bombeamento para Linguagens Finitas e Infinitas
Lema do Bombeamento para Linguagens Regulares e Livres do Contexto
Question 3
Question
Assumindo que um Linguagem A é regular, assinale a opção incorreta:
Answer
Existe uma constate 'p' chamada constante do Lema de Bombeamento, a qual indica o tamanho do bombeamento
Toda cadeia da Linguagem A de tamanho 's' podem ser decompostas em 3 partes desde que |s| > p
Toda cadeia da Linguagem A de tamanho 's' podem ser decompostas em 3 partes desde que |s| < p
A cadeia 's' pode ser dividida em xyz
Toda Linguagem Regular satisfaz o Lema do Bombeamento (LB)
Question 4
Question
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?
Answer
8
9
10
11
12
Question 5
Question
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?