Árbol autómata, Definiciones, Propiedades

Un autómata árbol es un tipo de máquina de estado. Árbol de acuerdo con autómatas estructuras de árbol, en lugar de las cadenas de máquinas de estado más convencionales.

El siguiente artículo trata de ramificación autómatas árbol, que corresponden a los lenguajes regulares de árboles. Para una noción diferente del árbol de autómata, véase el árbol de pie autómata.

Al igual que con autómatas clásica, autómatas finitos árbol puede ser o bien un autómata determinista o no. Según cómo el autómata procesa el árbol de entrada, autómatas finitos árbol puede ser de dos tipos: de abajo hacia arriba, de arriba hacia abajo. Esta es una cuestión importante, ya que aunque no determinista de arriba hacia abajo y de abajo hacia arriba ND autómatas árboles son equivalentes en fuerza expresiva, determinista autómatas de arriba hacia abajo son estrictamente menos potentes que sus contrapartes deterministas de abajo hacia arriba, ya que las propiedades del árbol especifican determinista autómatas árbol de arriba hacia abajo sólo puede depender de propiedades de la ruta.

Definiciones

Un alfabeto es clasificado un par de alfabeto normal y una función. Cada letra tiene su aridad por lo que se puede utilizar para construir términos. Elementos nullary también se llaman constantes. Términos construidas con símbolos unarios y constantes pueden ser considerados como cadenas. Aridad Superior conduce a los árboles.

Un ascendente autómata finito árbol más se define por:

He aquí un conjunto de letras unarios, es un alfabeto clasificado, es un conjunto de estados finales, y es un conjunto de reglas de transición, es decir, reescribir las reglas de los nodos cuyas raíces niño 'son estados, a los nodos cuyas raíces son estados. Así, el estado de un nodo se deduce de los estados de sus hijos.

No hay un estado inicial como tal, pero las reglas de transición para los símbolos constantes se puede considerar como estados iniciales. El árbol se rechaza si el estado marcado en la raíz es un estado de aceptación.

Un top-down tree autómata finito sobre se define por:

Hay dos diferencias con ascendente autómatas árbol: en primer lugar, el conjunto de sus estados iniciales, sustituye, en segundo lugar, las reglas de transición son a la inversa, es decir, reescribir las reglas de los nodos cuyas raíces están unidos a los nodos cuyas raíces del niño son estados . El árbol se acepta si cada rama se puede ir por este camino.

Las reglas de reescritura causan los símbolos de a 'viajar' a lo largo de las ramas del árbol.

Uno puede adivinar fácilmente que los autómatas árbol de arriba hacia abajo no determinista son equivalentes a no deterministas los de abajo hacia arriba, las reglas de transición son simplemente invierten, y los estados finales se convierten en los estados iniciales.

¿Por qué entonces son determinista descendente FTA menos potentes que sus contrapartes de abajo hacia arriba? Debido a que un TA determinista es, por definición, uno donde no hay dos reglas de transición tienen el mismo lado de la izquierda. Para autómatas árbol, reglas de transición son las reglas de reescritura, y para los de arriba hacia abajo, la izquierda será nodos principales. Por consiguiente, un determinista de arriba hacia abajo del árbol autómata sólo será capaz de probar las propiedades de los árboles que son verdaderas en todas las ramas, ya que la elección del estado para escribir en cada rama niño se determina en el nodo padre, sin saber el contenido ramas menores.

Propiedades

Determinismo

Como se dijo antes, un árbol autómata determinista es aquel en el que no hay dos reglas de transición tienen el mismo lado de la izquierda. Esta definición coincide con la idea intuitiva de que para un autómata sea determinista, una y sólo una transición debe ser posible para un nodo dado.

Reconocibilidad

Para un autómata de abajo hacia arriba, un término planta se acepta si existe una reducción que se inicia desde y termina con, donde es un estado final. Para un autómata de arriba hacia abajo, un término fundamental es aceptada si existe una reducción que parte de y termina con, donde es un estado inicial.

El lenguaje árbol reconocido por un autómata árbol es el conjunto de todos los términos aceptados por tierra. Un conjunto de términos de tierra es reconocible si existe un autómata árbol que lo reconoce.

Una propiedad importante es que homomorfismos lineales conservan reconocible.

Integridad y Reducción

Un no determinista autómata finito árbol es completa si hay al menos una regla de transición disponible para todas las combinaciones posibles de símbolos estados. Un estado es accesible si existe un plazo por razón de que existe una reducción de hasta. Un acuerdo de libre comercio se reduce si todos sus estados son accesibles.

Pumping Lemma

Dejar ser un conjunto reconocible de los Términos de tierra. Entonces, existe una constante 0 "src ="// upload.wikimedia.org/math/1/c/e/1ceed399f1d8fa4a79cc94a5e6c5c76c.png "/> satisfactoria: por cada término fundamental de tal que k" src = "//carga .wikimedia.org/math/0/2/6/026b53433b97b193ad21c962d3cf9fc7.png "/>, existe un contexto, un contexto no trivial y un término por razones de eso y, para todos.

Cierre

La clase de los lenguajes reconocibles árbol es cerrado bajo la unión, en la complementación, y en la intersección.

Myhill-Nerode Teorema

A congruencia en idiomas de árbol es una relación tal que

Es de índice finito si el número de clases de equivalencia es finito.

Para un árbol de lengua determinada, definir si para todos los contextos.

El teorema de Myhill-Nerode para el árbol autómata establece que las tres afirmaciones siguientes son equivalentes:

  • L es un lenguaje reconocible árbol
  • L es la unión de algunas clases de equivalencia de congruencia de índice finito
  • la relación es una congruencia de índice finito