Teoría de lenguajes formales - Autómata

Question

Me pregunto acerca de los lenguajes formales. Tengo una especie de programa de análisis: Se lee un xml-como estructura de árbol en serie y convertirla en una matriz multidimmensionnal.

Mi punto es en las similitudes entre el algoritmo que se utiliza y los diferentes tipos de autómatas (máquinas de Turing máquinas de estado de pila ...).

Así que la pregunta es: ¿cuál es el autómata que implícitamente uso aquí, y al cual formal de idiomas de la familia encaja? Y lo que es acerca de la recursividad?

Lo que quiero decir con "Autómata yo uso implícitamente" es "que es el autómata mínimo para hacer el mismo trabajo".

Aquí está el código fuente completo:

$ palabras; // una matriz de etiqueta XML '', '' y el contenido de texto simple

$ árbol = array ( 'Tipo' => 'root', 'Sub' => array () );

$ ptree = array (& $ árbol);

$ profunda = 0;

foreach ($ palabras como $ elem) {

if ( preg_match($openTag, $elem) ) { // $elem is an open tag

    $pTree[$deep++]['sub'][] = array( // we add an element to the multidim array
        'type' => 'block',
        'content' => $elem,
        'sub' => array()
    );

    $size = sizeof($pTree[$deep - 1]['sub']);
    $pTree[$deep] = &$pTree[$deep - 1]['sub'][$size - 1]; // down one level in the tree

} elseif ( preg_match($closeTag, $elem) ) { // it is a close tag

    $deep--; // up in the tree 

} else { // simple element

    $pTree[$deep]['sub'][] = array(
        'type' => 'simple',
        'content' => $elem
    );

}

}

Answer 1

Por favor, eche un vistazo a su pregunta de nuevo. ¿Se refiere a una variable $words, que no está en su ejemplo. Además, no existe un código, sin saber lo que se está haciendo es difícil responder a usted.

A juzgar por el nombre de la variable de $deep, probablemente no es el Estado. El estado en un autómata es un elemento de un conjunto que es específico para el autómata; miradas $deep como que podría contener una profundidad, con cualquier número entero positivo. Una vez más, difícil saber sin el código.

De todos modos, es probable que no "usando implícitamente" cualquier autómata en absoluto, si no el diseño de su código como una aplicación de uno.

Su sencilla similar a XML archivos probablemente podría ser reconocido por una máquina de pila determinista, o generada por una gramática libre de contexto determinista, haciéndolos tipo 2 en la jerarquía de Chomsky. Una vez más, esto es sólo una suposición, "un tipo XML serializado estructura de árbol" es demasiado vaga para cualquier tipo de formalismo.

En resumen, si usted está buscando para utilizar cualquier teoría formal, hacer la palabra a sus preguntas de manera más formal.

---

Editar (después de ver el código):

Estás construyendo un árbol. Que está fuera del alcance de un autómata (al menos los que “estándar”). autómatas finitos único trabajo con una entrada y un estado, máquinas de pila añadir una pila de eso, y las máquinas de Turing tiene una cinta de lectura-escritura que pueden moverse en ambas direcciones.

El “salida” de un autómata es un simple “Sí” (aceptado) o “No” (no se acepta, o un bucle infinito). (Máquinas de Turing pueden definirse para proporcionar más salida en su cinta.) Lo mejor que puedo responder a “que es el autómata mínimo para hacer el mismo trabajo” es que su lenguaje puede ser aceptado por una máquina de pila; pero funcionaría de manera muy diferente y no le dará los árboles.

Sin embargo, es posible mirar en gramáticas - otra construcción del lenguaje formal que introduce el concepto de árboles de análisis . Lo que está haciendo aquí es la creación de un árbol de análisis sintáctico como con un analizador de arriba hacia abajo.