Logo Passei Direto
Buscar

Primeira_Lista_de_Exerccios_de_FC (1)

Material
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

Prévia do material em texto

Universidade Federal de Roraima
Centro de Ciência e Tecnologia
Departamento de Ciência da Computação
______________________________________________________________________________________________
1a. Lista de Exercícios de Fundamentos da Computação
1) Escreva todos os prefixos, sufixos e subpalavras para as palavras a seguir:
a. aaa
b. abcb
c. aaba
2) É possível generalizar e responder qual é o número de prefixos, sufixos e subpalavras de uma palavra de
tamanho n?
3) Explique a diferença entre Σ= {0,1} e Σ1={0,1}.
4) Considerando um alfabeto ∑, explique o que representa ∑* - {ε}. Dê um exemplo.
5) Dados os AFD M1 e M2, responda às seguintes questões sobre cada um deles:
a. Qual é o estado inicial?
b. Qual é o conjunto de estados de aceitação?
c. Por qual sequência de estados a máquina passa para a entrada aabb?
d. A máquina aceita a cadeia aabb?
e. A máquina aceita a cadeia ε?
f. Dê a descrição formal das máquinas M1 e M2.
6) A descrição formal de um AFD M é ({q 1, q2, q3, q4, q5}, {u,d}, δ, q3, {q3}), onde δ é dada pela tabela a seguir.
Dê o diagrama de estados dessa máquina.
δ u d
q1 q1 q2
q2 q1 q3
q3 q2 q4
q4 q3 q5
q5 q4 q5
7) Construa AFDs (dê o diagrama de estados) para as seguintes linguagens sobre o alfabeto {0,1}:
a. O conjunto das palavras de tamanho 3.
b. O conjunto das palavras com no máximo três 1's.
c. O conjunto das palavras de tamanho múltiplo de 3.
d. O conjunto de palavras que começam com um 1 e terminam com um 0.
e. O conjunto de palavras que contém a subcadeia 0101.
f. O conjunto das palavras que contêm exatamente dois 1's e um número ímpar de 0's.
g. O conjunto das palavras que têm a forma {10}n com n ≥ 0.
h. O conjunto das palavras que não termina em 01.
8) Construa AFNs reconhecendo cada uma das linguagens a seguir.
a. A linguagem {ε} com 1 estado.
b. A linguagem {w | w termina com 00} com 3 estados.
c. A linguagem que tem bb ou não tem aa para o alfabeto {a,b}.
d. A linguagem {w є {a, b, c}* | o último símbolo de w seja idêntico ao primeiro}.
9) Seja o AFN M = ({q1, q2, q3}, {a,b}, δ, {q1}, {q1, q2, q3}), onde δ é dada pela tabela a seguir.
δ a b
q1 {q2} {}
q2 {q3} {}
q3 {} {q3}
Obtenha um AFN com um único estado final equivalente a M.
10) Converta os AFNs abaixo em AFDs:
11) Dado o AFN M = ({q0, q1}, {0, 1}, δ, q0, {q1}) e:
δ 0 1
q0 {q0,q1} {q1}
q1 {} {q0,q1}
Construir o AFD equivalente.
12) Minimize o seguinte AFD:
13) Especifique um AFD mínimo que, dentre as palavras que se escrevem com os símbolos 0, 1 e 2, aceite
apenas aquelas cujo somatório dos símbolos, interpretados como números, seja divisível por 3.
14) A descrição formal de um AFD M é ({q 0, q1, q2, q3, q4}, {0,1}, δ, q0, {q2, q4}), onde δ é dada pela tabela a
seguir. Minimize M.
δ 0 1
q0 q3 q1
q1 q4 q1
q2 q3 q0
q3 q2 q3
q4 q1 q0
15) Formalize as linguagens abaixo usando apenas operações básicas sobre conjuntos (concatenação, união,
fechos de Kleene, etc.).
a. {p ∈ {a, b}* | p começa com aa e termina com bb}.
b. {p ∈ {a, b}* | p começa com aa ou termina com bb}.
c. {p ∈ {a, b}* | p possui tamanho par}.
d. {p ∈ {a, b}* | p possui tamanho ímpar}.
e. {p ∈ {a, b}* | p começa e termina com a e contém pelo menos um b}.
f. {p ∈ {a, b}* | p contém exatamente dois b's}.
g. {p ∈ {0,1}* | todo 0 em p é seguido de 11}.
h. {p ∈ {0,1}* | p tem tamanho par e começa com 0 ou termina com 0}.
i. {p ∈ {0,1}* | p termina com 0 seguido de um número ímpar de 1's}.
16) Dada a seguinte linguagem, faça:
L={p ∈ {a, b, c}* | p contém ao menos um a e ao menos um b}
a. Faça uma GR que gere L (sem converter AFD em GR);
b. Faça uma ER que represente L;
c. Faça um AFN que reconheça L;
d. Converta o AFN encontrado em (c) em uma GR e compare com a GR encontrada em (a);
e. Converta a GR encontrada em (a) em um AFN e compare com o AFN encontrado em (c),
f. Converta o AFN encontrado em (c) em uma ER e compare com a ER encontrada em (b);
g. Converta a ER encontrada em (b) em um AFN e compare com o AFN encontrado em (c).
17) Para as linguagens abaixo, se forem regulares, apresente uma GR e uma ER, caso contrário use o lema do
bombeamento para provar que não são regulares (todas as variáveis apresentadas pertencem aos naturais):
a. {(ab)nak | n > k, k >= 0)}
b. {aibmcn | i > 0, 0 < m < n}
c. {aibmc2m | i, m, n ≥ 0}
d. {aibmcn | i ,m ≥ 0}
e. {anbmcn | n < 3 ,m ≥ 0}

Mais conteúdos dessa disciplina