Logo Passei Direto
Buscar

Exercícios de Teoria da Computação

Teoria da Computação

breadcrumb-separator

ESTÁCIO EAD

User badge image
Isakinhooo

em

Ferramentas de estudo

Mostrar todas

Questões resolvidas

(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
Gramática irrestrita.
Gramática de pilha.
Gramática regular.
Gramática livre de contexto.
Gramática sensível ao contexto.

Dado que A = {x ∊ ℕ | 1 < x < 3} e B = {x ∊ ℕ | 2 < x < 20}, então A ∩ B =
{3,4}
{3}
{ }
{2,3}
{2}

Vamos considerar que em uma classe 32 alunos gostam de Geografia e 40 de História. Sabendo que a classe possui 60 alunos, qual o número de alunos que gostam de Geografia e de História?
32
No máximo 12
20
No mínimo 12
36

(POSCOMP / 2016) O autômato finito exposto abaixo representa qual expressão regular?
a*b(c + da*b)*
a*b (d* + cb)
a*c* (b +d)*
ab*(da* + cb)*
(bb + d)* (aa + c)*

(POSCOMP / 2013) Sobre o Lema do Bombeamento (pumping lemma) para linguagens regulares, considere as afirmativas a seguir.
Assinale a alternativa correta.
I. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L1 = {w ∈ Σ* | w termina com b} não é regular.
II. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L2 = {(a ) | n ≥ 1} não é regular.
III. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que as linguagens L3 = {a | n ≥ 1}, L4 = {a ba ba | n, m ≥ 1} e L5 = {a b | 2 ≤ n ≤ m ≤ 3n} não são regulares.
IV. Se a linguagem for do tipo 3, então aplica-se o Bombeamento.
Somente as afirmativas I e II são corretas.
Somente as afirmativas I e IV são corretas.
Somente as afirmativas III e IV são corretas.
Somente as afirmativas I, II e III são corretas.
Somente as afirmativas II, III e IV são corretas.

(POSCOMP / 2008) Considere o autômato finito mostrado na figura abaixo (os círculos em negrito representam estados terminais) A esse respeito, assinale a afirmativa FALSA.
A palavra ababa não é reconhecida pelo autômato.
A palavra aba é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
A palavra baba é reconhecida pelo autômato.
A palavra aaa é reconhecida pelo autômato.

(POSCOMP / 2009 - adaptada) Seja o alfabeto e a linguagem regular. Qual das expressões regulares abaixo gera essa linguagem?
(a b* b b*)*
(( a )* | b*)*
( a | b )*
( b* | ( a )* | b*)*
( b* a b* a b* )*

Com base nas afirmativas abaixo assinale a resposta correta: I. As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos finitos. II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0. III. Em todo autômato finito existe sempre um estado inicial fixo. IV. Gramáticas têm um número finito de regras de produção.
I e IV, apenas.
I, II e IV, apenas
I, III e IV, apenas
II e IV, apenas
II e III, apenas

Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta? S U ∅ = S - ∅ = ∅ S ∩ ∅ = S S U ∅ = ∅ S U ∅ = S - ∅ = S S - ∅ = ∅

Conteúdos escolhidos para você

Lista de Exercícios - Autômatos e Expressões
2 pág.

Lista de Exercícios - Autômatos e Expressões

UFPE

Perguntas dessa disciplina

Na teoria da computação, a decidibilidade é um conceito fundamental que se refere à capacidade de resolver ou decidir um problema de forma algorítm...

Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica...

UNIÍTALO

Qual é o conceito principal da tese de Church-Turing na teoria da computação? a) A unicidade do computador pessoal. b) A existência de computadore...

Material
Buscar
páginas com resultados encontrados.
páginas com resultados encontrados.
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar esse material. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Questões resolvidas

(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
Gramática irrestrita.
Gramática de pilha.
Gramática regular.
Gramática livre de contexto.
Gramática sensível ao contexto.

Dado que A = {x ∊ ℕ | 1 < x < 3} e B = {x ∊ ℕ | 2 < x < 20}, então A ∩ B =
{3,4}
{3}
{ }
{2,3}
{2}

Vamos considerar que em uma classe 32 alunos gostam de Geografia e 40 de História. Sabendo que a classe possui 60 alunos, qual o número de alunos que gostam de Geografia e de História?
32
No máximo 12
20
No mínimo 12
36

(POSCOMP / 2016) O autômato finito exposto abaixo representa qual expressão regular?
a*b(c + da*b)*
a*b (d* + cb)
a*c* (b +d)*
ab*(da* + cb)*
(bb + d)* (aa + c)*

(POSCOMP / 2013) Sobre o Lema do Bombeamento (pumping lemma) para linguagens regulares, considere as afirmativas a seguir.
Assinale a alternativa correta.
I. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L1 = {w ∈ Σ* | w termina com b} não é regular.
II. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L2 = {(a ) | n ≥ 1} não é regular.
III. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que as linguagens L3 = {a | n ≥ 1}, L4 = {a ba ba | n, m ≥ 1} e L5 = {a b | 2 ≤ n ≤ m ≤ 3n} não são regulares.
IV. Se a linguagem for do tipo 3, então aplica-se o Bombeamento.
Somente as afirmativas I e II são corretas.
Somente as afirmativas I e IV são corretas.
Somente as afirmativas III e IV são corretas.
Somente as afirmativas I, II e III são corretas.
Somente as afirmativas II, III e IV são corretas.

(POSCOMP / 2008) Considere o autômato finito mostrado na figura abaixo (os círculos em negrito representam estados terminais) A esse respeito, assinale a afirmativa FALSA.
A palavra ababa não é reconhecida pelo autômato.
A palavra aba é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
A palavra baba é reconhecida pelo autômato.
A palavra aaa é reconhecida pelo autômato.

(POSCOMP / 2009 - adaptada) Seja o alfabeto e a linguagem regular. Qual das expressões regulares abaixo gera essa linguagem?
(a b* b b*)*
(( a )* | b*)*
( a | b )*
( b* | ( a )* | b*)*
( b* a b* a b* )*

Com base nas afirmativas abaixo assinale a resposta correta: I. As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos finitos. II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0. III. Em todo autômato finito existe sempre um estado inicial fixo. IV. Gramáticas têm um número finito de regras de produção.
I e IV, apenas.
I, II e IV, apenas
I, III e IV, apenas
II e IV, apenas
II e III, apenas

Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta? S U ∅ = S - ∅ = ∅ S ∩ ∅ = S S U ∅ = ∅ S U ∅ = S - ∅ = S S - ∅ = ∅

Conteúdos escolhidos para você

Lista de Exercícios - Autômatos e Expressões
2 pág.

Lista de Exercícios - Autômatos e Expressões

UFPE

Perguntas dessa disciplina

Na teoria da computação, a decidibilidade é um conceito fundamental que se refere à capacidade de resolver ou decidir um problema de forma algorítm...

Computabilidade é a habilidade de resolver problemas de forma efetiva. É um tópico chave para o campo da Teoria da Computabilidade dentro da Lógica...

UNIÍTALO

Qual é o conceito principal da tese de Church-Turing na teoria da computação? a) A unicidade do computador pessoal. b) A existência de computadore...

Prévia do material em texto

A
B
C
D
E
A
B
C
1 Marcar para revisão
(POSCOMP / 2009)  A análise léxica é usualmente
implementada a partir de:
Gramática regular.
Gramática livre de contexto.
Gramática sensível ao contexto.
Gramática irrestrita.
Gramática de pilha.
2 Marcar para revisão
Dado que A = {x ∊ ℕ | 1

Mais conteúdos dessa disciplina