TC CI Exercicios P2 cap5 APDs GLCs

Prévia do material em texto

Universidade do Estado do Rio de Janeiro 
Centro de Tecnologia e Ciências 
Instituto de Matemática e Estatística 
Departamento de Informática e Ciência da Computação 
Prof. Maria Alice Brito 
 
Teoria da Computação 
Lista de Exercícios sobre autômato de pilha com reconhecimento das cadeias por estado 
final e pilha vazia e sobre gramática livre de contexto 
______________________________________________________________________ 
 
 
 
Considere cada linguagem livre de contexto, abaixo, para os exercícios I-a e I-b. 
 
I-a) Apresente um autômato de pilha determinístico, que reconheça cada linguagem 
livre de contexto, abaixo, por estado final e pilha vazia. 
I-b) Apresente a gramática livre de contexto que gera cada linguagem livre de contexto, 
abaixo. 
 
L1 = { a
i b j  i = j, i  1, j  1} 
L2 = { a
i b j  j = 2i, i  1, j  1} 
L3 = { a
i b j  i  j, i  1, j  1} 
L4 = { a
i b j  i  j, i  1, j  1} 
L5 = { a
i b j  i = j, i  0, j  0} 
L6 = { a
i b j  j = 2i, i  0, j  0} 
L7 = { a
i b j  i  j, i  0, j  0} 
L8 = { a
i b j  i  j, i  0, j  0} 
L9 = { a
i b j c k  i = j, i  1, j  1, k  1 } 
L10 = { a
i b j c k  i = k, i  1, j  1, k  1 } 
L11 = { a
i b j c k  j = k, i  1, j  1, k  1 } 
L12 = { a
i b j c k  i  j, i  1, j  1, k  1 } 
L13 = { a
i b j c k  i  k, i  1, j  1, k  1 } 
L14 = { a
i b j c k  j  k, i  1, j  1, k  1 } 
L15 = { a
i b j c k  i  j, i  1, j  1, k  1 } 
L16 = { a
i b j c k  i  k, i  1, j  1, k  1 } 
L17 = { a
i b j c k  j  k, i  1, j  1, k  1 } 
L18 = { a
i b j c k  i = j + k, i  1, j  1, k  1 } 
L19 = { a
i b j c k  k = i +j, i  1, j  1, k  1 } 
L20 = { a
i b j c k  i = j, i  0, j  0, k  0 } 
L21 = { a
i b j c k  i = k, i  0, j  0, k  0 } 
L22 = { a
i b j c k  j = k, i  0, j  0, k  0 } 
L23 = { a
i b j c k  i  j, i  0, j  0, k  0 } 
Universidade do Estado do Rio de Janeiro 
Centro de Tecnologia e Ciências 
Instituto de Matemática e Estatística 
Departamento de Informática e Ciência da Computação 
Prof. Maria Alice Brito 
 
Teoria da Computação 
Lista de Exercícios sobre autômato de pilha com reconhecimento das cadeias por estado 
final e pilha vazia e sobre gramática livre de contexto 
______________________________________________________________________ 
 
 
L24 = { a
i b j c k  i  k, i  0, j  0, k  0 } 
L25 = { a
i b j c k  j  k, i  0, j  0, k  0 } 
L26 = { a
i b j c k  i  j, i  0, j  0, k  0 } 
L27 = { a
i b j c k  i  k, i  0, j  0, k  0 } 
L28 = { a
i b j c k  j  k, i  0, j  0, k  0 } 
L29 = { a
i b j c k  i = j + k, i  0, j  0, k  0 } 
L30 = { a
i b j c k  k = i +j, i  0, j  0, k  0 } 
L31 = { a
i b j c m d n i = n, j = m, i  1, j  1, m  1, n  1} 
L32 = { a
i b j c m d n i = n, j = m, i  0, j  0, m  0, n  0} 
L33 = { a
i b j c m d n i  n, j = m, i  1, j  1, m  1, n  1} 
L34 = { a
i b j c m d n i  n, j = m, i  0, j  0, m  0, n  0} 
L35 = { a
i b j c m d n i = n, j  m, i  1, j  1, m  1, n  1} 
L36 = { a
i b j c m d n i = n, j  m, i  0, j  0, m  0, n  0} 
L37 = { a
i b j c m d n i  n, j  m, i  1, j  1, m  1, n  1} 
L38 = { a
i b j c m d n i  n, j  m, i  0, j  0, m  0, n  0} 
L39 = { a
i b j c m d n i  n, j = m, i  1, j  1, m  1, n  1} 
L40 = { a
i b j c m d n i  n, j = m, i  0, j  0, m  0, n  0} 
L41 = { a
i b j c m d n i = n, j  m, i  1, j  1, m  1, n  1} 
L42 = { a
i b j c m d n i = n, j  m, i  0, j  0, m  0, n  0} 
L43 = { a
i b j c m d n i  n, j  m, i  1, j  1, m  1, n  1} 
L44 = { a
i b j c m d n i  n, j  m, i  0, j  0, m  0, n  0} 
L45 = { a
i b 2j c 3k  i = j, i  1, j  1, k  1 } 
L46 = { a
i b 2j c 3k  i = j, i  0, j  0, k  0 } 
L47 = { a
i b 3j c k  i = k, i  1, j  1, k  1 } 
L48 = { a
i b 3j c k  i = k, i  0, j  0, k  0 } 
L49 = { a
3i b j c k  j = k, i  1, j  1, k  1 } 
L50 = { a
3i b j c k  j = k, i  0, j  0, k  0 } 
L51 = { a
i b 3j c 2k  i = k, i  1, j  1, k  1 } 
L52 = { a
i b 3j c 2k  i = k, i  0, j  0, k  0 } 
Universidade do Estado do Rio de Janeiro 
Centro de Tecnologia e Ciências 
Instituto de Matemática e Estatística 
Departamento de Informática e Ciência da Computação 
Prof. Maria Alice Brito 
 
Teoria da Computação 
Lista de Exercícios sobre autômato de pilha com reconhecimento das cadeias por estado 
final e pilha vazia e sobre gramática livre de contexto 
______________________________________________________________________ 
 
 
L53 = { a
2i b 3j c k  i = k, i  1, j  1, k  1 } 
L54 = { a
2i b 3j c k  i = k, i  0, j  0, k  0 }