Théorie des langages formels - Automate

Question

Je m'interroge sur les langages formels. J'ai une sorte d'analyseur: Il lit une structure arborescente sérialisée de type xml et la transforme en un tableau multidimensionnel.

Mon point est sur les similitudes entre l'algorithme utilisé et les différents types d'automates (machines d'état des machines de Turing pile ...).

La question est: qui est l'automate que j'utilise implictly ici, et à quelle famille langues formelle-t-il en forme? Et qu'en est-il de la récursivité?

Ce que je veux dire par « automate j'utilise implicitement » est « qui est l'automate minimal pour faire le même travail ». Voici la source complète:

$ words; // un tableau de balise XML '<tag>', '</tag >' et simple contenu texte

tree $ = array ( 'type' => 'root', 'sous' => array ( );

$ ptree = array (& arbre $);

$ profondeur = 0;

foreach (mots $ comme $ 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

S'il vous plaît jeter un oeil à votre question. Vous parlez d'une variable $words, ce qui n'est pas dans votre exemple. En outre, il n'y a pas de code, sans savoir ce qui se fait, il est difficile de vous répondre.

A en juger par le nom de la $deep variable, il est probablement pas l'état. L'état dans un automate est un élément d'un ensemble spécifique à l'automate; $deep ressemble à ce qu'il pourrait contenir une profondeur, tout nombre entier positif. Encore une fois, difficile à dire sans le code.

Quoi qu'il en soit, vous n'êtes probablement pas « en utilisant implicitement » tout automate du tout, si vous ne l'avez pas concevoir votre code comme une mise en œuvre d'un. Vos fichiers xml-like simples pourraient probablement être reconnus par une machine à pile déterministe, ou générés par une grammaire déterministe sans contexte, ce qui les rend de type 2 dans la hiérarchie de Chomsky. Encore une fois, c'est juste une supposition, "une structure arborescente sérialisée de type xml" est trop vague pour tout type de formalisme. En bref, si vous cherchez à utiliser une théorie formelle, posez vos questions plus formellement.

---

Modifier (après avoir vu le code):

Vous construisez un arbre. C'est hors de portée pour un automate (du moins les "standards"). Les automates finis ne fonctionnent qu'avec une entrée et un état, les machines de pile ajoutent une pile à cela, et les machines de Turing ont une bande de lecture-écriture qu'elles peuvent déplacer dans les deux directions.

La « sortie » d'un automate est un simple « oui » (accepté) ou « Non » (non accepté, ou une boucle infinie). (Machines de Turing peuvent être définis pour fournir plus de puissance sur leur bande.) Le mieux que je peux répondre à « qui est l'automate minimal pour faire le même travail » est que votre langue peut être acceptée par une machine à pile; mais cela fonctionnerait très différemment et ne vous donnerait pas d'arbres.

Cependant, vous pouvez regarder dans - une autre grammaires construction de langage formel qui introduit le concept de parse arbres. Ce que vous faites ici est de créer un tel arbre d'analyse avec un analyseur top-down.