Comment appeler un langage structuré qui ne peut pas en boucle ou un langage fonctionnel qui ne peut pas revenir

Question

Je créé un « langage de programmation » spécialisés qui sont délibérément (par la conception) ne peut pas évaluer le même morceau de code deux fois (ie. Il ne peut pas en boucle). Il se compose essentiellement de décrire un procédé de type organigramme dans lequel chaque élément dans l'organigramme est un conditionnel qui effectue un test différent sur le même ensemble de données (sans pouvoir la modifier). Les branches peuvent fractionner et fusionner, mais jamais de façon circulaire, à savoir. l'organigramme ne peut pas revenir en boucle sur lui-même. En arrivant à la fin d'une branche, l'état actuel est retourné et le programme se termine.

écrit, un programme typique ressemble superficiellement à un programme dans un langage purement fonctionnel, sauf qu'aucune forme de récursion est autorisé et les fonctions ne peut jamais retourner quoi que ce soit; la seule façon de sortir d'une fonction est d'appeler une autre fonction, ou d'invoquer une déclaration de sortie générale qui renvoie l'état actuel. Un effet similaire pourrait aussi être atteint en prenant un langage de programmation structuré et en supprimant toutes les instructions de boucle, ou en prenant un langage de programmation « non structurées » et interdisant toute goto ou déclaration JMP qui va vers l'arrière dans le code.

Maintenant, ma question est: est-il un concis et de façon précise pour décrire la langue d'un tel? Je n'ai pas CS fond formel et il est difficile pour moi de comprendre des articles sur la théorie et la théorie des automates langage formel, donc je suis un peu à perte. Je sais que ma langue n'est pas Turing complet, et par une grande douleur, je réussis à me assurer que ma langue probablement peuvent être classés comme une « langue régulière » (ie. Une langue qui peut être évaluée par un la machine en lecture seule Turing), mais est-il un terme plus précis?

Les points de bonus si le terme est intuitivement compréhensible pour un public qui est bien versé dans les concepts de programmation généraux, mais ne dispose pas d'un arrière-plan formel CS. Aussi des points bonus s'il y a une sorte spécifique de la machine ou automate qui permet d'évaluer la langue d'un tel. Oh oui, gardez à l'esprit que nous ne sommes pas l'évaluation d'un flux de données - chaque élément a (lecture seule) l'accès à l'ensemble des données d'entrée. :)

Answer 1

Je sais que cette question est un peu vieux, mais pour la postérité, la phrase que vous recherchez est « arbre de décision ». Voir http://en.wikipedia.org/wiki/Decision_tree_model pour plus de détails. Je crois que ce capture exactement ce que vous avez fait et a un nom assez descriptif pour démarrer!

Answer 2

Je crois que votre langue est suffisamment puissant pour coder avec précision les langues étoiles sans . Ceci est un sous-ensemble de langues que dans le cadre desquels aucune expression contient une étoile de Kleene. En d'autres termes, il est la langue de la chaîne vide, le jeu nul, et les caractères individuels est fermé sous concaténation et disjonction. Cela équivaut à l'ensemble des langues acceptées par DFA qui n'ont pas de cycles dirigés en eux.

Je peux tenter une preuve ici donné votre description de votre langue, bien que je ne suis pas sûr qu'il fonctionnera correctement précisément parce que je n'ai pas accès à votre langue. Les hypothèses que je fais sont les suivantes:

1. Aucune fonction retourne un jour. Une fois qu'une fonction est appelée, elle ne reviendra jamais le flux de contrôle à l'appelant.
2. Tous les appels sont résolus statiquement (qui est, vous pouvez consulter le code source et construire un graphique de chaque fonction et l'ensemble des fonctions qu'il appelle). En d'autres termes, il n'y a pas de pointeurs de fonction.
3. Le graphe d'appel est acyclique; pour toutes les fonctions A et B, alors exactement l'une des conditions suivantes est remplie: A appelle transitivement B, B appelle transitive A, ou ni A ni B appeler transitive un autre
.
4. De manière plus générale, le graphe de flux de contrôle est acyclique. Une fois qu'une expression évalue, il évalue jamais. Cela nous permet de généraliser ce qui précède de sorte qu'au lieu de penser à d'autres fonctions fonctions d'appel, nous pouvons penser au programme comme une série de déclarations qui appellent tous les uns les autres comme DAG.
5. Votre entrée est une chaîne où chaque lettre est balayée une fois et une seule fois, et dans l'ordre dans lequel il est donné (ce qui semble raisonnable compte tenu du fait que vous essayez de modèle ordinogrammes).

Compte tenu de ces hypothèses, voici une preuve que vos programmes acceptent une langue ssi cette langue est sans étoile.

Pour prouver que s'il y a un langage sans étoile, il y a un programme dans votre langue qui l'accepte, commencer par la construction du DFA minimum d'état pour cette langue. langues libres Star sont sans boucle et balayer l'entrée une seule fois, et il devrait être facile de construire un programme dans votre langue de la DFA. En particulier, étant donné un s d'état avec un ensemble de transitions vers d'autres états en fonction du symbole suivant de l'entrée, vous pouvez écrire une fonction se penche sur le caractère suivant de l'entrée, puis appelle la fonction codant pour l'état étant à la transition. Étant donné que le DFA n'a pas de cycles dirigé, les appels de fonction ont pas cycles dirigé, et ainsi chaque instruction sera exécutée une seule fois. Nous avons maintenant que (? R. est un langage sans étoile ? ? un programme dans votre langue qui l'accepte).

Pour prouver le sens inverse de l'implication, nous inversons essentiellement cette construction et de créer un e-NFA sans cycles qui correspond à votre programme. Faire une construction de sous-ensemble sur cette NFA pour le réduire à un DFA n'introduira aucun cycles, et ainsi vous aurez un langage sans étoile. La construction est la suivante: pour chaque instruction _i dans votre programme, créer un état q _i avec une transition vers chacun des états correspondant aux autres déclarations contenues dans votre programme qui sont à un bond de cette déclaration. Les transitions vers les états seront étiquetés avec les symboles d'entrée ayant fait chacune des décisions, ou e si la transition se produit sans consommer d'entrée. Cela montre que (? programmes P dans votre langue, et existe, une langue sans étoile R l'accepte seulement les chaînes acceptées par langue)

.

Dans l'ensemble, cela montre que vos programmes ont identiquement la puissance des langues sans étoiles.

Bien sûr, les hypothèses que j'ai fait sur ce que vos programmes peuvent faire peut-être trop limité. Vous pourriez avoir accès aléatoire à la séquence d'entrée, que je penser peut être manipulé avec une modificationfication de la construction ci-dessus. Si vous pouvez éventuellement avoir des cycles dans l'exécution, cette ensemble des pauses de construction. Mais, même si je me trompe, j'avais encore beaucoup de réflexion amusant à ce sujet, et je vous remercie pour une soirée agréable. : -)

Hope this helps!