alfa-ALN: Autômatos Lineares Não-Determinísticos com alfa-Transições
DOI:
https://doi.org/10.5540/tema.2011.012.03.0171Abstract
Neste trabalho introduziremos a classe dos autômatos lineares não-determinísticos com alfa-transições. Baseados numa nova forma normal para gramáticas lineares, provamos que a classe de linguagens aceita por este tipo de autômato é exatamente a classe das linguagens lineares. Mostramos ainda que, análogo ao que ocorre com os autômatos finitos e com os autômatos com pilhas, a existência das alfa-transições em um autômato linear não-determinístico não significa que não possa ser definido um autômato linear não-determinístico sem alfa-transições que reconheça a mesma linguagem. Ou seja, as alfa-transições não aumentam o poder de aceitação destes autômatos e portanto podem ser dispensadas do modelo. Finalmente, apresentamos uma aplicação destes autômatos no contexto de bioinformática.References
B. Albert, “Molecular Biology of the Cell”, 4a ed., Garland Science, New York, 2002.
J.A. Anderson, “Automata Theory with Modern Applications”, Cambridge University Press, Cambridge, 2006.
J.M. Autebert, J. Berstel, L. Boasson, Context-free languages and pushdown automata, em “Handbook of Formal Languages, Vol. 1: Word, Language, Grammar” (G. Rozenberg, ed.), pp. 111–174, Springer-Verlag, New York, 1997.
B.C. Bedregal, Pushdown automata free of explicit nondeterminism and an infinite hierarchy of context-free languages, Fundamenta Informaticae, 81 (2007), 367–377.
B.C. Bedregal, B.M. Acióly, A. Lyra, “Introdução à Teoria da Computação: Linguagens Formais, Autômatos e Computabilidade”, Editora UnP, Natal, 2010.
B.C. Bedregal, A.C.R. Costa, G.P. Dimuro, Fuzzy rule-based hand gesture recognition, IFIP Int. Fed. for Information Processing, 217, pp. 285–294, 2006.
J. Carroll, D. Long, “Theory of Finite Automaton With an Introduction to Formal Languages”, Prentice-Hall, Englewood Cliffs, New Jersey, 1989.
D.I.A. Cohen, “Introduction to Computer Theory” (Revised printing), John Wiley & Sons, New York, 1991.
C. De La Higuera, J. Oncina, Inferring Deterministic Linear Languages, em “Proc. of the 15th Annual Conference on Computational Learning Theory (DLT)”(J. Kivinen, R.H. Sloan, eds.), Lectures Notes in Computer Science, Vol. 2375, pp. 185–200, Springer-Verlag, Berlim, 2002.
H.T.A. De Sena, Algumas Evidencias Computacionais da Infinitude dos Números Primos Palindrômicos e Generalizações Destes. Trabalho de Conclusão de Curso. (Graduação em Bach. em Ciências da Computação), Universidade Federal do Rio Grande do Norte, Natal, 2008. (Disponível em http://www.dimap.ufrn.br/∼bedregal/students.html)
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.