Una memoria de la computadora es finito, así que ¿cómo puede haber idiomas más potente que el resto?

Question

Un equipo tiene un número finito de memoria. No hay equipos con infinito de la memoria. Por lo tanto, los únicos idiomas que una computadora puede procesar son aquellos cuyos miembros cadenas son finitos. Como recuerdo, la potencia de cálculo necesaria para cualquier lenguaje finito es pequeño-un determinista autómatas de estado finito es suficiente para el proceso finito idiomas, creo.

Así que no hay tal cosa como el contexto libre de idiomas o recursivamente enumerable idiomas, derecho? Los lenguajes de programación no son de contexto libre, sólo son simples regulares de idiomas, derecho? La idea de que un lenguaje de programación es un contexto libre de la lengua ... bueno, eso es una ilusión, ¿verdad?

¿Por qué se molestó hablar de contexto libre de idiomas, lenguajes recursivos, recursivamente enumerable idiomas ya que dentro de la (finito) equipo todo es sólo un lenguaje regular?

Obviamente estoy jugando diablos-defensor de aquí, pero realmente me gustaría comprender la falacia de mi argumento.

Resumen de las Respuestas

Muchas gracias a todos los que respondieron. He estudiado sus respuestas cuidadosamente. Hay muchas perlas de sabiduría en sus respuestas que me decidí a resumir. Si mi resumen es incorrecta, claro, o la falta de un concepto importante, por favor hágamelo saber.

> A computer has a finite memory. There are no computers 
> with infinite memory. Therefore the only languages that 
> a computer can process are those whose member strings 
> are finite.

Respuestas

Una memoria de la computadora es finito, por lo que en su memoria se puede reconocer sólo finita idiomas. Sin embargo, si a usted le pase una entrada externa para el ordenador, entonces podría reconocer algunos infinito idiomas.

Ejemplo: a*b es un idioma infinito y cualquier cadena en la que el lenguaje puede ser reconocido, incluso si la cadena supera el tamaño de la memoria de la computadora. He aquí cómo: paso de la cadena en el equipo, carácter por carácter. Si el primer carácter que se pasa no es una "a", a continuación, ir a un estado de error. De lo contrario, permanecer en el "un" estado hasta que un no"un" carácter de entrada. Si el carácter no es una "b", a continuación, vaya al estado de error. De lo contrario, vaya a aceptar un estado. Para cualquiera de los caracteres más allá de la "b" ir al estado de error.

No todos los infinitos idiomas puede ser reconocido mediante esta técnica de alimentación de las cadenas de entrada como entrada externa. De hecho, la técnica puede ser utilizada sólo con regular idiomas. E incluso de los regulares de idiomas, sólo algunos de ellos pueden ser reconocidos.

Ejemplo: Para fines de ilustración, supongamos que el equipo tiene un ridículamente pequeño tamaño de la memoria, dicen, de 2 bytes. Supongamos que 1 byte se requiere para cada estado de un autómata de estado finito. A continuación, el equipo no será capaz de reconocer este lenguaje regular: a*b*c* porque, al menos, tres byes son necesarios – un byte para el estado que consume todo el un, un segundo byte para el estado que consume todo el b, y un tercer byte para el estado que consume todo el c.

Cualquier autómata de estado finito que requiere de más estados que no son bytes en la memoria de la computadora no puede ser reconocida.

Finalmente, con esta técnica de alimentación arbitrariamente largas cadenas en el equipo como externos de entrada, tendríamos que encontrar una manera alrededor de ciertas limitaciones técnicas, tales como una fuente de alimentación continua.

> A computer has a finite memory. Therefore the only languages 
> that a computer can process are those whose member strings 
> are finite … So there is no such thing as context-free languages 
> or recursively enumerable languages, right?

Respuestas

Considere la posibilidad de un idioma infinito. Se compone de cadenas de longitud arbitraria. Muchas cadenas será mayor que el tamaño de la memoria de la computadora. Es incorrecto decir que porque un equipo puede retener en su memoria sólo las cadenas que son de una cierta longitud finita, el lenguaje tiene sólo un número finito de cadenas. Es cierto que cualquier subconjunto finito de un lenguaje es regular. Pero eso no quiere decir que el idioma original debe haber sido regular.

> A computer has a finite memory. Therefore, in general, a computer 
> can only process a finite subset of an infinite language. A finite 
> subset of a language is regular. So why don't we simply treat all 
> languages used in computers as regular? 

Respuestas

La razón para tratar, por ejemplo, un lenguaje de programación independiente del contexto es que la gramática independiente del contexto, se explica cómo analizar el lenguaje. Si se considera sólo el subconjunto de programas con una longitud de no más de 2^{de 32}, que sería regular, pero la expresión regular es probable que constan de millones de casos individuales, y no sería útil para el análisis de los programas.

Answer 1

La razón para tratar a un lenguaje de programación independiente del contexto es que la gramática independiente del contexto, se explica cómo analizar el lenguaje. Si se considera sólo el subconjunto de C que consta de los programas de la longitud de no más de $2^{32}$ que sería normal, pero la expresión regular es probable que consisten en millones de casos individuales, y no sería útil para el análisis de los programas. Usted podría incluso no ser capaz de ajustar el compilador en la memoria...

Para un simple ejemplo, considere un contexto libre de la gramática de expresiones aritméticas con números naturales, la adición y la multiplicación.

• E -> {secuencia de dígitos 0-9}
• E -> ( E + E )
• E -> ( E * E )

Si sólo mira expresiones con 500 o menos símbolos, que fragmento del lenguaje es regular, pero es mucho más difícil describir como un lenguaje regular de un contexto libre de uno. Además, el árbol de análisis de la gramática independiente del contexto da una forma directa para evaluar las expresiones, mientras que el árbol de análisis para que el más pequeño fragmento como un lenguaje regular no es probable para ayudar a evaluar la expresión.

Answer 2

En realidad, en el sentido de que el programa, usted puede hacer que un equipo como el poder como la Máquina de Turing universal. (De hecho, el equipo que son, probablemente lo es). Más precisamente, se puede escribir de forma explícita una Máquina de Turing universal en muchos de los actuales lenguajes de ordenador por ahí. Así que, en un mundo real sentido, hay un programa de ordenador mucho más poder que cualquier autómatas finitos (el modelo de cálculo que reconoce regulares de idiomas).

Es cierto que un equipo ha finito de memoria. Esto simplemente significa que un equipo va a imitar a cualquier máquina de Turing hasta que se agote la memoria, electricidad, etc. Sin embargo, cualquier cálculo que se detiene la toma cantidad finita de tiempo. Así que, en teoría, uno podría necesitar para construir un ordenador más potente. Si el cálculo no se puede detener por un idealizar la máquina de Turing, ni tampoco por cualquier equipo real no importa cuán poderoso. Esto no cambia el hecho de que su verdadero equipo se está ejecutando el mismo programa como una máquina de Turing universal.

Además, usted debe hacer una distinción entre las lenguas y el modelo de cálculo. Un idioma es una cadena de símbolos. Un recursiva del lenguaje es uno decidió por una Máquina de Turing. Un recursivamente enumerable el lenguaje es una aceptados por una máquina de Turing. Por ejemplo, el conjunto de $H$ código $\langle e, f \rangle$ de manera tal que el $e^\text{th}$ Máquina de Turing se detiene en la entrada de $f$ es recursivamente enumerable de la serie correspondiente a la detención de problema. Este es sólo un conjunto de números! Una idea! ¿Por qué debe el hecho de que los equipos reales limitados de memoria tienen ninguna relación en si un recursiva del lenguaje o lenguaje regular (algunas conjunto infinito; una idea abstracta) debe "existe" o no.

Preguntar si los idiomas (una noción abstracta) existe debido a la naturaleza real de los equipos no está todo bien definido pregunta. Hace un recursiva del lenguaje no existe porque no existe ningún equipo puede correr el tiempo suficiente para detener? Pero va a detener el tiempo. Del mismo modo, uno puede hacer grandes autómatas finitos que no va a detener nadie con vida. Se va a parar, finalmente, también. Esto no significa de ningún lenguaje regular existentes, ya sea porque no hay ningún dispositivo de corriente puede finalizar el cálculo.

Recursiva del lenguaje y regular idiomas son solo ideas calculada por otras nociones abstractas, como máquinas de Turing o autómatas finitos. La naturaleza de los equipos físicos no hacer que las ideas reales.

Answer 3

Hay algunos puntos interesantes que se plantean aquí.

La cosa acerca de todos los idiomas reconocible por un equipo de un ser finito que está mal. Por ejemplo, usted puede hacer un programa interactivo que lee una cadena de entrada de un usuario, y su programa de procesos de cada uno de los caracteres del flujo de entrada a medida que se introducen. Podemos eliminar la necesidad de almacenar toda la cadena de entrada en la memoria. Esto significa que podemos tener una arbitrariamente larga cadena de entrada. También es posible hacer un idioma infinito y un programa que reconoce el lenguaje. Por ejemplo, supongamos que el conjunto de alfabeto es $\{0,1\}$. Puedo hacer que un idioma $L = 1^*$. $L$ es infinito, y es evidente cómo un reconocedor puede ser programado. ($L$ aquí todavía es regular).

Es cierto, sin embargo, que suponiendo que la memoria es limitada, cada idioma reconocible es regular, simplemente porque usted puede ver todos los posibles estados de la memoria como los estados de un afd. Obviamente hay un carácter desfavorable de este DFA - la escandalosamente gran número de estados. Esto, en un sentido, es una razón por la que los lenguajes de programación tienen el control de otras declaraciones que "si" y "caso".

Answer 4

No hay ninguna falacia. En la práctica, realmente todo es normal (finito). Sin embargo, usted no conseguirá mucho por hacer si usted los trata como tales. Un DFA para el tiempo razonablemente largo para las cadenas de un lenguaje interesante terminará teniendo injustificado a muchos estados.

Answer 5

No estoy de acuerdo con esto. Supongamos que desea comprobar si dos grafos son isomorfos, o si un número es primo. A priori no se conoce el límite en el número de nodos o en el tamaño del número, por lo tanto, tenemos necesidad de infinito idiomas. Sin embargo, esto no contradice el hecho de que un equipo ha finito de memoria, ya que una máquina de Turing siempre utiliza una cantidad finita de memoria en un momento dado, sin embargo, puede utilizar la memoria tanto como se quiera en un sentido finito, esto es justo como queremos abstracto fuera de hardware. Esto está conforme con la idea de que incluso para el general de los equipos no asumimos a priori límite en la cantidad de memoria que tiene.