Teoria da Computacao - Apostilha
24 pág.

Teoria da Computacao - Apostilha


DisciplinaTeoria da Computação726 materiais17.421 seguidores
Pré-visualização6 páginas
L = {anb2n | n \u2265 1} 
\u2022 L = {an | n é primo} 
 
Dependência. Observando os exemplos de linguagens não regulares apresentados, é 
possível notar que a quantidade de um determinado símbolo depende da quantidade de 
outro símbolo, ou ainda depende de um algoritmo que não pode ser representado 
usando um número finito de estados. 
 
Memória. Os AFDs não possuem memória. Isto é, são incapazes de armazenar a 
quantidade lida de um determinado símbolo. Nisto, reside sua principal limitação para 
reconhecer linguagens como L = {anbn | n \u2265 0} e L = {anbm | n \u2264 m}. 
 
16. Bibliografia 
 
LEWIS, Harry R. & PAPADIMITRION, Christos H. Elementos de Teoria da 
Computação. 2.ed. Porto Alegre, Bookman, 2000. 
 
MENEZES, Paulo Blauth. Linguagens formais e autômatos. 2.ed. Porto Alegre, Sagra 
Luzzatto, 1998. 165p. 
 
 
 
 
 
 Prof. Rômulo Silva 
24 
HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à Teoria de 
Autômatos, Linguagens e Computação; Rio de Janeiro; Ed. Campus, 2002. 
 
DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: Máquinas Universais e 
Computabilidade, Série Livros Didáticos Número 5, Instituto de Informática, da 
UFRGS, Editora Sagra Luzzatto, 1a edição, 1999. 
 
EUGÊNIO, Cristiana Munhoz; PALERMO, Lilliam. Unix Avançado: Programação C-
Shell. Disponível em http://www.ccuec.unicamp.br , acessado em 20/03/2006.