Lista Exercícios 2

Prévia do material em texto

UERJ Universidade do Estado do Rio de Janeiro
IME Instituto de Matemática e Estatística
DICC Departamento de Informática e Ciência da Computação - Profa. Maria Alice Silveira de Brito
Teoria da Computação Lista 2
1. Mostre que: 
a) cada linguagem abaixo não é regular,
b) cada linguagem abaixo é livre de contexto,
c) Apresente um autômato de pilha não determinístico que as reconheça, por estado final e por pilha vazia ao mesmo tempo. 
	L1 = { ai b j  i = j, i  1, j  1} 
	L2 = { ai b j  j = 2i, i  1, j  1}
	L3 = { ai b j  i  j, i  1, j  1}
	L4 = { ai b j  i  j, i  1, j  1}
	L5 = { ai b j  i = j, i  0, j  0}
	L6 = { ai b j  j = 2i, i  0, j  0}
	L7 = { ai b j  i  j, i  0, j  0}
	L8 = { ai b j  i  j, i  0, j  0}
L9 = { ai b j c k  i = j, i  1, j  1, k  1 }
L10 = { ai b j c k  i = k, i  1, j  1, k  1 }
L11 = { ai b j c k  j = k, i  1, j  1, k  1 }
L12 = { ai b j c k  i  j, i  1, j  1, k  1 }
L13 = { ai b j c k  i  k, i  1, j  1, k  1 }
L14 = { ai b j c k  j  k, i  1, j  1, k  1 }
L15 = { ai b j c k  i  j, i  1, j  1, k  1 }
L16 = { ai b j c k  i  k, i  1, j  1, k  1 }
L17 = { ai b j c k  j  k, i  1, j  1, k  1 }
L18 = { ai b j c k  i = j + k, i  1, j  1, k  1 }
L19 = { ai b j c k  k = i +j, i  1, j  1, k  1 }
L20 = { ai b j c k  i = j, i  0, j  0, k  0 }
L21 = { ai b j c k  i = k, i  0, j  0, k  0 }
L22 = { ai b j c k  j = k, i  0, j  0, k  0 }
L23 = { ai b j c k  i  j, i  0, j  0, k  0 }
L24 = { ai b j c k  i  k, i  0, j  0, k  0 }
L25 = { ai b j c k  j  k, i  0, j  0, k  0 }
L26 = { ai b j c k  i  j, i  0, j  0, k  0 }
L27 = { ai b j c k  i  k, i  0, j  0, k  0 }
L28 = { ai b j c k  j  k, i  0, j  0, k  0 }
L29 = { ai b j c k  i = j + k, i  0, j  0, k  0 }
L30 = { ai b j c k  k = i +j, i  0, j  0, k  0 }
L31 = { ai b j c m d n i = n, j = m, i  1, j  1, m  1, n  1}
L32 = { ai b j c m d n i = n, j = m, i  0, j  0, m  0, n  0}
L33 = { ai b j c m d n i  n, j = m, i  1, j  1, m  1, n  1}
L34 = { ai b j c m d n i  n, j = m, i  0, j  0, m  0, n  0}
L35 = { ai b j c m d n i = n, j  m, i  1, j  1, m  1, n  1}
L36 = { ai b j c m d n i = n, j  m, i  0, j  0, m  0, n  0}
L37 = { ai b j c m d n i  n, j  m, i  1, j  1, m  1, n  1}
L38 = { ai b j c m d n i  n, j  m, i  0, j  0, m  0, n  0}
L39 = { ai b j c m d n i  n, j = m, i  1, j  1, m  1, n  1}
L40 = { ai b j c m d n i  n, j = m, i  0, j  0, m  0, n  0}
L41 = { ai b j c m d n i = n, j  m, i  1, j  1, m  1, n  1}
L42 = { ai b j c m d n i = n, j  m, i  0, j  0, m  0, n  0}
L43 = { ai b j c m d n i  n, j  m, i  1, j  1, m  1, n  1}
L44 = { ai b j c m d n i  n, j  m, i  0, j  0, m  0, n  0}
L45 = { ai b 2j c 3k  i = j, i  1, j  1, k  1 }
L46 = { ai b 2j c 3k  i = j, i  0, j  0, k  0 }
L47 = { ai b 3j c k  i = k, i  1, j  1, k  1 }
L48 = { ai b 3j c k  i = k, i  0, j  0, k  0 }
L49 = { a3i b j c k  j = k, i  1, j  1, k  1 }
L50 = { a3i b j c k  j = k, i  0, j  0, k  0 }
L51 = { ai b 3j c 2k  i = k, i  1, j  1, k  1 }
L52 = { ai b 3j c 2k  i = k, i  0, j  0, k  0 }
3. Mostre que são ou não regulares, ou que são ou não livres de contexto as seguintes linguagens, com o auxílio dos lemas do bombeamento:
	L3a = { aibj  i,j  0 }
	L3b = {aibi  i  0 }
	L3c = { aibj i  j  0 }
	L3d = { aibj i  1, j  1 }
	L3e = { aibj 0 < i < j}
	L3f = { aibici i  1}
	L3g = {w.w  w  {a,b}* }
	L3h = {w.wR  w  {a,b}* }
4. Utilizando a mT M4, M4 = ( K, , , ,i , F), em que K = { q0, q1, q2, q3, q4 },  = {a, b},  = {a, b, X, Y,  }, i = q0, F = { q4 } e 
	
	a
	b
	X
	Y
	
	q0
	q1XR
	
	
	q3YR
	q4XR
	q1
	q1aR
	q2YL
	
	q1YR
	
	q2
	q2aL
	
	q0XR
	q2YL
	
	q3
	
	
	
	q3YR
	q4XR
	q4
	
	
	
	
	
Verifique se as cadeias aab e abbaa são aceitas por esta mT M4, mostrando a sequência de configurações assumidas por M6 ao tentar reconhecer cada cadeia.
5.ª) Construa uma mT M5 que reconheça as cadeias da linguagem L5 = { anbncn  n  1 }.
6.ª) Tente definir a gramática G6 , para a linguagem L6 = {aibjck| i < j < k, i  1}, com base na gramática sensível ao contexto G6= < {S,B,C}, {a,b,c}, P, S >, que gera a linguagem L6 = { anbncn  n  1 }, cujas regras encontram-se, a seguir: 
	S→aSBC
	S→aBC
	CB→BC
	aB→ab
	bB→bb
	bC→bc
	cC→cc
	
7.ª) Encontre uma gramática para as linguagens:
L1={ai: i=k2, k um inteiro positivo}.
L2={xx: x {a,b}*}.
pag.� PAGE �1� -� DATE \@"DD\/MM\/YY" �28/02/13�