Estaba leyendo sobre Iota y Jot y encontré esta sección confusa:
A diferencia de Iota, donde el árbol sintáctico para una cadena puede ramificarse tanto a la izquierda como a la derecha, la sintaxis de Jot se ramifica uniformemente a la izquierda. Como resultado, Iota es estrictamente libre de contexto, pero Jot es un lenguaje normal.
Tengo entendido que tanto Iota como Jot están completos. Pero aparentemente, uno no tiene contexto y el otro es regular. ¿Seguramente los idiomas normales no pueden ser completos?
regular-languages
programming-languages
turing-completeness
sdleihssirhc
fuente
fuente
1*0
es un lenguaje normal ;-) Aunque no es un lenguaje de programación muy amigable ni para el programador ni para el compilador-escritor.Respuestas:
En resumen, la respuesta es sí.
Pero está mezclando dos significados completamente no relacionados del término "lenguaje" (sí, esto es confuso):
Tenga en cuenta que puede hablar sobre "el lenguaje C ++" desde dos puntos de vista completamente no relacionados, utilizando los dos significados no relacionados de la palabra "lenguaje":
Los rasgos del "lenguaje C ++" desde estos dos puntos de vista no están relacionados.
Más ejemplos para ayudarlo a separar estos conceptos:
fuente
(([a-z][0-9]*)*[A-Z][0-9]*([a-z][0-9]*)*->([a-zA-Z][0-9]*)*)*
Si bien el conjunto de programas legales en Jot es regular, Jot en sí mismo es Turing completo. Eso significa que cada función computable se puede expresar en Jot. Incluso podemos encontrar un lenguaje en el que todas las cadenas binarias sean legales, pero el lenguaje en sí es Turing completo (ejercicio). Estás confundiendo sintaxis y semántica.
Por cierto, los lenguajes libres de contexto tampoco (probablemente) no tienen NP completo, ya que tienen un algoritmo de análisis de tiempo polinómico.
fuente
La sintaxis sola (como está codificada en los árboles de sintaxis) de los lenguajes de programación modernos está lejos de todo lo que hacen. De hecho, los lenguajes formales definidos por el conjunto de todos los programas en un idioma dado que se compilan sin errores rara vez incluso están libres de contexto .
La semántica estática y dinámica factor en la ecuación. Son invisibles en el árbol de sintaxis, pero determinan si un fragmento de código es realmente un programa y lo que calcula. En pocas palabras, el contexto libre resp. El lenguaje formal regular que se define por "sintaxis" proporciona una aproximación excesiva del lenguaje de programación.
Ahora para responder a su pregunta: sí, es posible. Considere, por ejemplo, cualquier numeración Gödel de máquinas Turing; obtienes el "lenguaje de programación" de todos los números naturales, cada uno representando una TM. De acuerdo, no es un buen lenguaje para programar, pero ciertamente es un lenguaje completo de Turing que es regular, incluso trivial.
fuente
Un lenguaje de programación es completo de Turing si es lo suficientemente expresivo como para especificar cada función computable por las máquinas de Turing. Aquí estamos discutiendo el poder de los lenguajes especificados en los lenguajes de programación . Por ejemplo, no es difícil escribir un intérprete para máquinas Turing en Python, por lo que Python es un lenguaje de programación completo de Turing.
La sintaxis de un lenguaje de programación , es decir, el conjunto de cadenas correspondientes a programas válidos en el lenguaje de programación, es en sí mismo un lenguaje. Por ejemplo, considere el conjunto de todos los posibles programas de Python. La sintaxis de un lenguaje de programación puede ser sensibles al contexto , libre de contexto , normal , etc. Estamos interesados en la dificultad de comprobar que una determinada cadena es un programa válido en el lenguaje de programación (esto se hace por los compiladores / intérpretes). Cuando decimos que la sintaxis de un lenguaje de programación no tiene contexto, significa que hay una gramática libre de contexto para su sintaxis e implica que hay autómatas para verificar la validez de los programas,
Tenga en cuenta que la simplicidad de la sintaxis de un lenguaje de programación no implica una restricción en el poder computacional de los programas especificados en esos lenguajes de programación.
fuente
La respuesta es sí. Verá, como dice la respuesta aceptada, una gramática es independiente de su significado. En las propias palabras de Chomsky:
Si una gramática puede producir suficientes oraciones para describir todas las cosas que se pueden calcular, entonces podemos asignar arbitrariamente significado computacional a sus oraciones, una para cada cosa que se puede calcular.
En cuanto a un ejemplo concreto real, el lenguaje popular
whitespace
tiene una gramática regular y quizás inclusox86 assembly languages
(necesita verificación).fuente