¿Qué clase de idiomas reconoce los autómatas de estado finito con

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 necesariamente en el mismo lugar en la entrada que las otras.

Definamos una máquina de estados finitos con $k$ cabezas de la siguiente manera:

Un NFA de cabeza k es una tupla $(Q, \Sigma, \Delta, q_0, F)$ , donde:

• Como de costumbre, $Q$ es un conjunto finito de estados, $\Sigma$ es un alfabeto finito, $q_0$ es un estado inicial y $F$ es un conjunto de estados de aceptación. Deje $\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$ denota el conjunto de caracteres, incluida la cadena vacía.

• $\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$ es la relación de transición: una transición$(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$ significa que, si la máquina está en el estado$p$ , puede leer en$(\sigma_1, \sigma_2, \ldots, \sigma_k)$ tal que$\sigma_i$ es el siguiente carácter para la cabeza$i$ (o$\varepsilon$ si esa cabeza no se mueve), y luego pasar al estado$q$ .

Una ejecución de este tipo de máquina (cualquier ruta que comience desde el estado inicial y termine en un estado de aceptación) da como resultado no una cadena, sino $k$ cadenas diferentes (formadas mediante la concatenación de los caracteres a lo largo de la ejecución). Luego decimos que la ejecución es válida si las cadenas $k$ son idénticas.

El lenguaje de la máquina es el conjunto de cadenas $w$ modo que existe una ejecución válida de la máquina donde las $k$ cadenas producidas a lo largo de esa ejecución son todas iguales a $w$ .

Pregunta: ¿Cuál es la clase de idiomas reconocidos por tales máquinas? ¿Ha sido estudiado?

Una primera observación es que tales máquinas producen una clase más grande que los idiomas regulares. Por ejemplo, el lenguaje

(Aquí, un borde etiquetado con $\sigma_1 / \sigma_2$ denota una transición de la forma $(p, (\sigma_1, \sigma_2), q)$ .)

$k$

Este modelo es uno de los modelos estándar en la teoría de autómatas y ha sido examinado por algunos investigadores.

Las referencias dadas en el primer comentario son muy buenos puntos de partida.

Cuando la cabeza es bidireccional, las clases de lenguajes reconocidos por tales modelos son idénticas a las clases de espacio logarítmico. Sin embargo, cuando la cabeza es unidireccional, entonces, que yo sepa, no tenemos una caracterización exacta similar, pero tenemos ciertos resultados incomparables y algunas jerarquías basadas en el número de cabezas.

Si está interesado, le recomiendo que compruebe también versiones alternativas, probabilísticas y cuánticas de autómatas de múltiples cabezales. Dichos modelos pueden ser bastante interesantes incluso cuando se usa un solo cabezal, ya que el cálculo se divide en diferentes rutas, y luego, en cada ruta, la cabeza puede acceder a diferentes partes de las entradas.

Algunas referencias genéricas:

• Máquinas de Turing con espacio sublogarítmico: https://books.google.lv/books?id=vNPuNOo9BUYC

Alternancia

• Viliam Geffert - https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam

Computación probabilística

• Ioan I. Macarie - https://dblp.org/pers/hd/m/Macarie:Ioan_I=

Cálculo probabilístico y cuántico

• Rusins ​​Freivalds - https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins
• Abuzer Yakaryilmaz - https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer

Modelos relacionados: autómatas de múltiples contadores y autómatas que utilizan guijarros.