Cómo llamar a un lenguaje estructurado que no puede repetirse o a un lenguaje funcional que no puede regresar

Question

Creé un "lenguaje de programación" de propósito especial que deliberadamente (por diseño) no puede evaluar el mismo fragmento de código dos veces (es decir,no puede realizar un bucle).Básicamente, está hecho para describir un proceso similar a un diagrama de flujo donde cada elemento del diagrama de flujo es un condicional que realiza una prueba diferente en el mismo conjunto de datos (sin poder modificarlo).Las ramas pueden dividirse y fusionarse, pero nunca de forma circular, es decir.el diagrama de flujo no puede volver a repetirse sobre sí mismo.Al llegar al final de una rama, se devuelve el estado actual y el programa sale.

Cuando está escrito, un programa típico se parece superficialmente a un programa en un lenguaje puramente funcional, excepto que no se permite ninguna forma de recursividad y las funciones nunca pueden devolver nada;la única forma de salir de una función es llamar a otra función o invocar una declaración de salida general que devuelva el estado actual.También se podría lograr un efecto similar tomando un lenguaje de programación estructurado y eliminando todas las declaraciones de bucle, o tomando un lenguaje de programación "no estructurado" y prohibiendo cualquier declaración goto o jmp que retroceda en el código.

Ahora mi pregunta es:¿Existe una forma concisa y precisa de describir dicho lenguaje?No tengo experiencia formal en informática y me resulta difícil entender artículos sobre teoría de autómatas y teoría del lenguaje formal, por lo que estoy un poco perdido.Sé que mi lenguaje no es Turing completo y, a través de un gran dolor, logré asegurarme de que mi lenguaje probablemente puede clasificarse como un "lenguaje regular" (es decir,un lenguaje que puede ser evaluado por una máquina de Turing de sólo lectura), pero ¿existe un término más específico?

Puntos de bonificación si el término es intuitivamente comprensible para una audiencia que conoce bien los conceptos generales de programación pero que no tiene experiencia formal en informática.También puntos de bonificación si hay un tipo específico de máquina o autómata que evalúa dicho lenguaje.Ah, sí, tenga en cuenta que no estamos evaluando un flujo de datos: cada elemento tiene acceso (de solo lectura) al conjunto completo de datos de entrada.:)

Answer 1

Sé que esta pregunta es algo antigua, pero para la posteridad, la frase que está buscando es el "árbol de decisión". Ver http://en.wikipedia.org/wiki/decision_tree_model para detalles. ¡Creo que esto captura exactamente lo que has hecho y tiene un nombre bastante descriptivo para arrancar!

Answer 2

Creo que su lenguaje es lo suficientemente poderoso como para codificar precisamente el idiomas sin estrellas.Este es un subconjunto de esos lenguajes regulares en los que ninguna expresión contiene una estrella de Kleene.En otras palabras, es el lenguaje de la cadena vacía, el conjunto nulo y los caracteres individuales el que se cierra bajo concatenación y disyunción.Esto es equivalente al conjunto de lenguajes aceptados por los DFA que no tienen ciclos dirigidos.

Puedo intentar una prueba de esto aquí dada la descripción de su idioma, aunque no estoy seguro de que funcione correctamente porque no tengo acceso completo a su idioma.Las suposiciones que estoy haciendo son las siguientes:

1. Ninguna función regresa nunca.Una vez que se llama a una función, nunca devolverá el flujo de control a la persona que la llama.
2. Todas las llamadas se resuelven estáticamente (es decir, puede mirar el código fuente y construir un gráfico de cada función y el conjunto de funciones que llama).En otras palabras, no hay punteros de función.
3. El gráfico de llamadas es acíclico;para cualesquiera funciones A y B, entonces se cumple exactamente una de las siguientes condiciones:A llama transitivamente a B, B llama transitivamente a A, o ni A ni B se llaman transitivamente entre sí.
4. De manera más general, el gráfico de flujo de control es acíclico.Una vez que una expresión se evalúa, nunca más se evalúa.Esto nos permite generalizar lo anterior de modo que, en lugar de pensar en funciones que llaman a otras funciones, podemos pensar en el programa como una serie de declaraciones que se llaman entre sí como un DAG.
5. Su entrada es una cadena donde cada letra se escanea una vez y sólo una vez, y en el orden en que se proporciona (lo que parece razonable dado el hecho de que está intentando modelar diagramas de flujo).

Dadas estas suposiciones, aquí hay una prueba de que sus programas aceptan un idioma si ese idioma no tiene estrellas.

Para demostrar que si hay un lenguaje sin estrellas, hay un programa en su idioma que lo acepta, comience por construir el DFA de estado mínimo para ese lenguaje.Los lenguajes sin estrellas no tienen bucles y escanean la entrada exactamente una vez, por lo que debería ser fácil crear un programa en su idioma desde DFA.En particular, dado un estado s Con un conjunto de transiciones a otros estados basados ​​en el siguiente símbolo de entrada, puede escribir una función que analice el siguiente carácter de entrada y luego llama a la función que codifica el estado que está haciendo la transición.Dado que DFA no tiene ciclos dirigidos, las llamadas a funciones no tienen ciclos dirigidos y, por lo tanto, cada declaración se ejecutará exactamente una vez.Ahora tenemos que (∀ R.es un lenguaje sin estrellas → ∃ un programa en tu idioma que lo acepte).

Para demostrar la dirección inversa de la implicación, esencialmente invertimos esta construcción y creamos un ε-NFA sin ciclos que corresponda a su programa.Realizar una construcción de subconjunto en este NFA para reducirlo a un DFA no introducirá ningún ciclo y, por lo tanto, tendrá un lenguaje sin estrellas.La construcción es como sigue:para cada declaración s_i en su programa, cree un estado q_i con una transición a cada uno de los estados correspondientes a las otras declaraciones en su programa que están a un salto de esa declaración.Las transiciones a esos estados estarán etiquetadas con los símbolos del insumo consumido al tomar cada una de las decisiones, o ε si la transición se produce sin consumir ningún insumo.Esto muestra que (∀ programa P en su idioma, &exists;un idioma sin estrellas R que acepta solo las cadenas aceptadas por su idioma).

En conjunto, esto demuestra que sus programas tienen idéntica potencia que los lenguajes sin estrellas.

Por supuesto, las suposiciones que hice sobre lo que pueden hacer sus programas pueden ser demasiado limitadas.Es posible que tengas acceso aleatorio a la secuencia de entrada, lo cual pensar se puede manejar con una modificación de la construcción anterior.Si potencialmente se pueden tener ciclos en ejecución, entonces toda esta construcción se rompe.Pero, incluso si me equivoco, me divertí mucho pensando en esto y gracias por una velada agradable.:-)

¡Espero que esto ayude!