Un DFA o NFA lee a través de una cadena de entrada con un solo encabezado, moviéndose de izquierda a derecha. Parece natural preguntarse acerca de las máquinas de estado finito que tienen múltiples cabezas , cada una de las cuales se mueve a través de la entrada de izquierda a derecha, pero no...
Relacionado con una pregunta reciente ( Límites en el tamaño del NFA más pequeño para L_k-distinct ) Noam Nisan solicitó un método para proporcionar un límite inferior mejor para el tamaño de un NFA que el que obtenemos de los límites de complejidad de la comunicación. Lo que sigue es una versión...
Dado un NFA NnorteN y su DFA equivalente que DreDresulta de la determinación total de NnorteN (usando la construcción del conjunto de potencia, por ejemplo), las siguientes propiedades se mantienen para NnorteN , DreD y para cualquier palabra www : lee w en tiempo de ejecución como máximo O ( |...