λ-ALN: autômatos lineares não-determinísticos com λ-transições

Abstract

Neste trabalho introduziremos a classe dos autômatos lineares não-determinísticos com λ-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 λ-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 λ-transições que reconheça a mesma linguagem. Ou seja, as λ-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.

Translated abstract

In this paper we introduce the class of linear non-deterministic automata with λ-transitions, and based on a new normal form for linear grammars, we prove that the class of languages accepted by such automata is exactly the class of linear languages. Also we show that, analogously to finite automata and pushdown automata, the ocorrences of λ-transitions in a non-deterministic linear automaton not means that not be possible define a non-deterministic linear automata without λ-transitions which accept the same language. Thus, λ-transitions not increases the acceptance power of this class of automata and therefore can be dispensed. Finally, we present an application of this automata in the context of bioinformatics.