alfa-ALN: Autômatos Lineares Não-Determinísticos com alfa-Transições - Bedregal, Benjamin Callejas (Trends in Computational and Applied Mathematics, 2011)
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.