alfa-ALN: Autômatos Lineares Não-Determinísticos com alfa-Transições
DOI:
https://doi.org/10.5540/tema.2011.012.03.0171Resumo
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.Referências
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
Publicado
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.