Sintaxe e semântica formais de "Máquinas de Post" como máquinas de estados finitos
Resumo
O estudo da equivalência de modelos de Computação requer que a sintaxe e a semântica dos modelos sejam formalmente definidas. Neste trabalho investigamos como a "Máquina de Post" aparece nos referenciais bibliográficos usados em um conjunto de IES com cursos na área de Computação e propomos definições sintáticas e semânticas rigorosas para o modelo. O resultado é um modelo mais similar ao de Turing, facilitando a construção e o entendimento de provas de equivalência.
Palavras-chave:
Autômatos de Fila, Educação em Computação, Teoria da Computação
Referências
Bird, R. (1976). Programs and machines. Wiley series in computing. John Wiley & Sons, Chichester, England.
Boolos, G. S., Burgess, J. P., and Jeffrey, R. C. (2007). Computability and Logic. Cambridge University Press, Cambridge, England, 5th edition.
Diverio, T. A. and Menezes, P. B. (2011). Teoria da computação: máquinas universais e computabilidade. Bookman, 3th edition.
Floyd, R. W. and Beigel, R. (1994). The language of machines. W.H. Freeman, New York, NY.
Folha de São Paulo (2019). Ranking Universitário Folha 2019. [link].
Greenlaw, R. and Hoover, H. J. (1998). Modern Computability Theory. Morgan Kaufmann, Oxford, England.
Harrison, M. A. (1978). Introduction to formal language theory. Addison-Wesley series in computer science. Addison Wesley Longman Publishing, New York, NY.
Hopcroft, J. E., Ullman, J. D., and Motwani, R. (2001). Introdução à Teoria de Autômatos, Linguagens e Computação. Campus, 2th edition.
Kozen, D. (1997). Automata and Computability. Undergraduate Texts in Computer Science. Springer, New York, NY, 1st edition.
Lewis, H. R. and Papadimitriou, C. H. (2004). Elementos da Teoria da Computação. Bookman, 2th edition.
Machtey, M. and Young, P. (1978). An introduction to the general theory of algorithms. North Holland.
Martin, J. C. (2010). Introduction to Languages and the Theory of Computation. Mc Graw Hill, 4th edition.
Menezes, P. B. (2002). Linguagens Formais e Autômatos: Volume 3 da Série Livros Didáticos Informática UFRGS. Bookman.
Minsky, M. L. (1967). Computation: Finite and Infinite Machines. Automatic Computation S. Prentice Hall, Old Tappan, NJ.
Moll, R. N., Arbib, M. A., and Kfoury, A. J. (1988). An introduction to formal language theory. AKM Series in Theoretical Computer Science. Springer, New York, NY, 1988 edition.
Post, E. L. (1936). Finite combinatory process: formulation 1. The Journal of Symbolic Logic, 1(3):103–105.
S. C. Coutinho, S. C. (2007). Autômatos e Linguagens Formais. Universidade Federal do Rio de Janeiro.
Sipser, M. (2006). Introduction to the Theory of Computation. Thompson Course Technology, Boston, MA, 2nd edition.
Sudkamp, T. A. (2005). Languages and machines. Pearson, Upper Saddle River, NJ, 3rd edition.
Vieira, N. J. (2006). Introdução aos fundamentos da computação: linguagens e máquinas. Thomson.
Boolos, G. S., Burgess, J. P., and Jeffrey, R. C. (2007). Computability and Logic. Cambridge University Press, Cambridge, England, 5th edition.
Diverio, T. A. and Menezes, P. B. (2011). Teoria da computação: máquinas universais e computabilidade. Bookman, 3th edition.
Floyd, R. W. and Beigel, R. (1994). The language of machines. W.H. Freeman, New York, NY.
Folha de São Paulo (2019). Ranking Universitário Folha 2019. [link].
Greenlaw, R. and Hoover, H. J. (1998). Modern Computability Theory. Morgan Kaufmann, Oxford, England.
Harrison, M. A. (1978). Introduction to formal language theory. Addison-Wesley series in computer science. Addison Wesley Longman Publishing, New York, NY.
Hopcroft, J. E., Ullman, J. D., and Motwani, R. (2001). Introdução à Teoria de Autômatos, Linguagens e Computação. Campus, 2th edition.
Kozen, D. (1997). Automata and Computability. Undergraduate Texts in Computer Science. Springer, New York, NY, 1st edition.
Lewis, H. R. and Papadimitriou, C. H. (2004). Elementos da Teoria da Computação. Bookman, 2th edition.
Machtey, M. and Young, P. (1978). An introduction to the general theory of algorithms. North Holland.
Martin, J. C. (2010). Introduction to Languages and the Theory of Computation. Mc Graw Hill, 4th edition.
Menezes, P. B. (2002). Linguagens Formais e Autômatos: Volume 3 da Série Livros Didáticos Informática UFRGS. Bookman.
Minsky, M. L. (1967). Computation: Finite and Infinite Machines. Automatic Computation S. Prentice Hall, Old Tappan, NJ.
Moll, R. N., Arbib, M. A., and Kfoury, A. J. (1988). An introduction to formal language theory. AKM Series in Theoretical Computer Science. Springer, New York, NY, 1988 edition.
Post, E. L. (1936). Finite combinatory process: formulation 1. The Journal of Symbolic Logic, 1(3):103–105.
S. C. Coutinho, S. C. (2007). Autômatos e Linguagens Formais. Universidade Federal do Rio de Janeiro.
Sipser, M. (2006). Introduction to the Theory of Computation. Thompson Course Technology, Boston, MA, 2nd edition.
Sudkamp, T. A. (2005). Languages and machines. Pearson, Upper Saddle River, NJ, 3rd edition.
Vieira, N. J. (2006). Introdução aos fundamentos da computação: linguagens e máquinas. Thomson.
Publicado
09/10/2023
Como Citar
FERREIRA, Ana Paula Lüdtke; MOREIRA, Nicholas Cortez; PORTELLA, Lourenço Nataniel Pinheiro.
Sintaxe e semântica formais de "Máquinas de Post" como máquinas de estados finitos. In: WORKSHOP-ESCOLA DE INFORMÁTICA TEÓRICA (WEIT), 7. , 2023, Rio Grande/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 111-119.
DOI: https://doi.org/10.5753/weit.2023.26604.
