Question 1
Question
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 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
Question 3
Question
Assumindo que um Linguagem A é regular, assinale a(s) opção(ões) incorreta(s):
Answer
-
Podemos utilizar o Lema do Bombeamento para provar que A é regular
-
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
Question 4
Question
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' ?
Answer
-
O número de caracteres que ela gera
-
A linguagem não é regular
-
O número de ciclos que percorremos na cadeia possui
-
O número de vezes que a cadeia pode ser decomposta
Question 5
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?
Question 6
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. Assuma que ela seja regular. Qual das seguintes divisões de s em xyz está de acordo com esta suposição?
Question 7
Question
Ainda para a linguagem descrita no exercício anterior, A={0^m 1^n ∶m > n ≥ 0}. 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?
Question 8
Question
Dada a linguagem A = { (1^n²) : n ≥ 0 }. Utilizando o Lema do Bombeamento, podemos dizer sobre essa linguagem que:
Question 9
Question
Dada a linguagem L = { (a^n)b : n ≥ 0 }. Utilizando o Lema do Bombeamento, podemos dizer sobre essa linguagem que:
Question 10
Question
Dada a linguagem L = { (0^n)(1^n)(2^n) : n ≥ 0 }. Utilizando o Lema do Bombeamento, podemos dizer sobre essa linguagem que: