¿Cómo deberían influir las máquinas de jerarquía y de Turing de Chomsky en el diseño del lenguaje?

Question

Actualmente estoy estudiando para una prueba de matemáticas discretas en la que estamos aprendiendo Chomsky's hierarchy y el tipo de autómatas que reconocen cada nivel de la jerarquía. Me están enseñando que la mayoría de los lenguajes de computadora caen dentro del "nivel 2 y 1" de la jerarquía, pero no precisamente cómo.

Mis preguntas son:

1. ¿Qué características pertenecen a cada nivel?

2. ¿Es esto nada más que una base teórica? Me pregunto si los diseñadores de idiomas como Dennis Ritchie y James Gosling tuvieron que considerar estas consideraciones al diseñar C y Java. ¿Ellos? ¿Cómo alguien aplicaría esto?

3. Nos dicen que las máquinas de Turing reconocen el nivel 0 de la jerarquía. Si es así, ¿hay alguna característica del lenguaje que pertenezca al nivel 0? Supongo que esto puede ser un procesamiento natural del lenguaje, ¿verdad?

Answer 1

1. Ninguno. Nivel 1 Nivel 2 incluye Tal vez entendido mal, por lo que ser completa:

   • Idiomas regulares se usan en expresiones regulares. Coloquial: los DFA no pueden contar. Y necesita contar si quiere hacer coincidir los paréntesis. [Nivel 3]
   • La sintaxis del lenguaje normalmente es un lenguaje sin contexto. Ver 2) [Nivel 2]
   • El Lenguaje sensible al contexto se usa solo teóricamente. Ver 3) [Nivel 1]

2. Ayuda en el diseño de lexers y analizadores sintácticos. No sé si los creadores de C pensaron en eso, pero Java, sin duda. Parser Generator

3. Turing Machines calcule cualquier cosa que se pueda calcular. "Puede calcularse" incluso se define como: puede ser aceptado por una máquina de Turing. Esto incluye, por supuesto, el procesamiento del lenguaje natural. Cualquier cosa superior al Nivel 2 no es muy útil para la generación de idioma, porque un programa que lea tales entradas puede no detenerse (Word Problem ya no se puede resolver).

Answer 2

Tipo 3 gramáticas generan lenguajes regulares. Estos son idiomas con características como "xxx", "xxx", termina con "xxx", contiene un número impar de y, etc. Los autómatas finitos (determinísticos o no) reconocen estos idiomas.

Las gramáticas de tipo 2 generan lenguajes sin contexto. Estos son idiomas con características como un número de x seguidos por menos, o más, o igual número de y, o donde una palabra es seguida por la misma palabra, pero invertida. Los autómatas Pushdown reconocen estos lenguajes ... piense en autómatas finitos con una pila.

Las gramáticas de Tipo 1 generan lenguajes contextuales. Estos están tan cerca de las gramáticas Tipo 0 que a menudo es difícil encontrar una diferencia entre ellos. Los LBA (autómatas lineales limitados) reconocen estos lenguajes, piensan en máquinas Turing con recursos limitados ... piensen en una computadora moderna.

Las gramáticas de tipo 0 generan lenguajes de Turing, a veces llamados lenguajes recursivamente enumerables. Básicamente, se trata de cualquier lenguaje que se pueda escribir para reconocer un programa de computadora, pero realmente se combina con el Tipo 1, ya que las computadoras reales generalmente tienen algún tipo de límite de memoria.

Los autómatas finitos y los autómatas pushdown son muy importantes para resolver los problemas que surgen cuando se escriben compiladores. Sin embargo, esa no es la razón por la que los estudias, los estudias para aprender los límites de lo que se puede/no se puede calcular. Muchos programadores piensan que puedes resolver cualquier problema con una computadora. La teoría de la computación te enseña lo contrario.

Editar por "Amigo" - OK, aquí es una herramienta fácil de entender (y famosos) problema que no pueda ser resuelto por cualquier máquina de Turing o el ordenador o programador o el genio extranjero ...

Imagine que tiene algunas fichas de dominó ... pero en lugar de patrones de puntos, tiene una palabra corta en la parte superior e inferior, diga palabras como "aba" y "taxi". Si le doy 5 o 10 o 50 de estos dominós, ¿puede organizarlos para que las palabras en la parte superior, todos concatenados juntos, coincidan exactamente con las palabras concatenas en la parte inferior. Puedes hacer tantas copias como quieras de cada domino.

Ejemplo de dominó (ideado :) (a/aab), (aba/ac), (cab/ab) es un conjunto de 3 dominós donde las partes superiores (a + aba + cab) son exactamente iguales a las inferiores (aab + ac + ab).

Tan fácil como suena, no se puede resolver en general.

Por cierto, cuando leí por primera vez este problema ... Estaba pensando ... ooooh, n! está empezando a verse bien!