itc exercicio 1 (Ellen Souza)

Prévia do material em texto

UNIVERSIDADE FEDERAL RURAL DE PERNAMBUCO
UNIDADE ACADÊMICA DE SERRA TALHADA
BACHARELADO EM SISTEMAS DE INFORMAÇÃO
 
 
Turma/Período: SI1 / 2012.2 Código
Nome: ______________________________
Data de Entrega: 10/01/2013 
 
1. Seja ∑ o alfabeto {a,b}, Quais as linguagens abaixo? 
Liste as cadeias que são reconhecidas pela linguagem:
a. {x ∈ ∑* | |x| é par}
b. {x ∈ ∑* | |x| ≤ 2} 
c. {x ∈ ∑* | o primeiro símbolo de x é igual ao último símbolo de x}
d. {x ∈ ∑* | o penúltimo caractere de x é a}
e. {x ∈ ∑* | x não contém a subcadeia aba}
f. {x ∈ ∑* | x não contém dois a consecutivos}
g. {x ∈ ∑* | x contém pelo menos dois a consecutivos}
h. {x ∈ ∑* | x contém no máximo dois a consecutivos}
i. {x ∈ ∑* | nenhum bloco de 3 carac
j. {x ∈ ∑* | |x| = 0} 
k. {x ∈ ∑* | |x| é impar e x é da forma yy
l. {xx | x ∈ ∑*} 
m. {xxR | x ∈ ∑*} 
n. {xyxR | x,y ∈ ∑*} 
o. {abanb : n ≥ 0} 
2. Construa AFDs que reconheças as seguintes linguagens sobre 
reconhecidas por cada um deles e 5 não reconhecidas. Realize o passo
de transição utilizada. 
a. { w | w possui aaa como subpalavra}
b. { w | o sufixo de w é bb}
c. { w | w possui número ímpar de a e b}
 
 
 
MINISTÉRIO DA EDUCAÇÃO 
UNIVERSIDADE FEDERAL RURAL DE PERNAMBUCO 
UNIDADE ACADÊMICA DE SERRA TALHADA 
BACHARELADO EM SISTEMAS DE INFORMAÇÃO 
Código / Disciplina: CCMP5009 - Introdução à Teoria da Computação
__________________________________________________________ 
 o alfabeto {a,b}, Quais as linguagens abaixo? 
Liste as cadeias que são reconhecidas pela linguagem: 
* | |x| é par} 
* | o primeiro símbolo de x é igual ao último símbolo de x} 
* | o penúltimo caractere de x é a} 
ão contém a subcadeia aba} 
ão contém dois a consecutivos} 
* | x contém pelo menos dois a consecutivos} 
* | x contém no máximo dois a consecutivos} 
* | nenhum bloco de 3 caracteres consecutivos de x contém dois a}
* | |x| é impar e x é da forma yyR para algum y ∈	∑*} 
*} 
que reconheças as seguintes linguagens sobre ∑ = {a,b}. Mostre 5 palavras 
reconhecidas por cada um deles e 5 não reconhecidas. Realize o passo-a-passo, mostrando cada regra 
{ w | w possui aaa como subpalavra} 
{ w | o sufixo de w é bb} 
{ w | w possui número ímpar de a e b} 
 
UFRPE 
Teoria da Computação 
____________________________________________ 
teres consecutivos de x contém dois a} 
Mostre 5 palavras 
passo, mostrando cada regra