¿Qué es una gramática gratuita de contexto?

Question

¿Puede alguien explicarme qué es una gramática libre de contexto? Después de mirar la entrada de Wikipedia y luego la entrada de Wikipedia sobre la gramática formal, me siento total y totalmente aturdido. ¿Alguien sería tan amable de explicarme qué son estas cosas?

Me pregunto esto porque deseo investigar el análisis sintáctico, y también por el lado, la limitación de un motor de expresiones regulares.

No estoy seguro si estos términos están directamente relacionados con la programación, o si están más relacionados con la lingüística en general. Si ese es el caso, me disculpo, quizás esto podría ser movido si es así?

Answer 1

Una gramática de contexto libre es una gramática que satisface ciertas propiedades. En informática, las gramáticas describen los idiomas; específicamente, describen los lenguajes formales.

Un lenguaje formal es simplemente un conjunto (término matemático para una colección de objetos) de cadenas (secuencias de símbolos ... muy similar al uso de programación de la palabra "cadena"). Un ejemplo simple de un lenguaje formal es el conjunto de todas las cadenas binarias de longitud tres, {000, 001, 010, 011, 100, 101, 110, 111}.

Las gramáticas funcionan al definir las transformaciones que puede realizar para construir una cadena en el lenguaje descrito por una gramática. Las gramáticas dirán cómo transformar un símbolo de inicio (generalmente S) en una cadena de símbolos. Una gramática de la lengua dada antes es:

S -> BBB 
B -> 0 
B -> 1 

La forma de interpretar esto es decir que S se puede sustituir por B y B puede ser sustituido por 0, y B puede ser reemplazado por 1. Así que para construir la cadena 010 que podemos hacer S -> BBB -> 0BB -> 01B -> 010.

Una gramática libre de contexto es simplemente una gramática en la que lo que está reemplazando (a la izquierda de la flecha) es símbolo único "no terminal". Un símbolo no terminal es cualquier símbolo que utiliza en la gramática que no puede aparecer en sus cadenas finales. En la gramática anterior, "S" y "B" son símbolos no terminales, y "0" y "1" son símbolos "terminales". Gramáticas como

S -> AB 
AB -> 1 
A -> AA 
B -> 0 

no son regulares, ya que contienen reglas como "AB -> 1".

Answer 2

La teoría del lenguaje está relacionada con la teoría de la computación. ¿Cuál es el aspecto más filosófico de la Informática, sobre cómo decidir qué programas son posibles o cuáles serán posibles de escribir, y qué tipo de problemas es imposible escribir un algoritmo para resolver?

Una expresión regular es una forma de describir un idioma normal. Un lenguaje regular es un lenguaje que puede ser decidido por un autómata finito determinista.

Se debe leer el artículo sobre máquinas de estados finitos: http://en.wikipedia.org/wiki/Finite_state_machine

y lenguajes regulares: http://en.wikipedia.org/wiki/Regular_language

Todos los idiomas regulares son libres de contexto Idiomas, pero hay Contexto Idiomas gratuitas que no son regulares. Un lenguaje sin contexto es el conjunto de todas las cadenas aceptadas por un Grammer libre de contexto o un autómata pushdown que es una máquina de estado finito con una única pila: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

Hay lenguajes más complicados que requieren una máquina de Turing (Cualquier programa posible) puede escribir en su computadora) para decidir si una cadena está en el idioma o no.

La teoría del lenguaje también está muy relacionada con el problema P vs. NP, y algunas otras cosas interesantes.

Mi introducción al libro de texto de tercer año de Computer Science fue bastante bueno para explicar esto: Introducción a la teoría de la computación. Por Michael Sipser. Pero me costó $ 160 comprarlo nuevo y no es muy grande. Tal vez puedas encontrar una copia usada o encontrar una copia en una biblioteca o algo que pueda ayudarte.

EDIT:

Las limitaciones de las expresiones regulares y clases de idiomas más altas se han investigado una tonelada en los últimos 50 años más o menos. Puede que le interese el lema del bombeo para los idiomas habituales. Es un medio de probar que un determinado idioma no es regular:

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

Si un idioma no es regular puede ser Contexto libre, lo que significa que podría ser descrita por un contexto libre de gramática, o puede ser incluso en una clase de idioma superior, puede probar que no es Contexto libre por el lema de bombeo para idiomas sin contexto, que es similar al de las expresiones regulares.

Un idioma puede incluso ser indecidible, lo que significa que incluso una máquina de Turing (puede programar que su computadora pueda funcionar) no puede programarse para decidir si una cadena debe ser aceptada como en el idioma o rechazada.

Creo que la parte que más le interesa son las máquinas de estados finitos (tanto deterministas como deterministas) para ver qué idiomas puede decidir una expresión regular, y el lema de bombeo para probar qué idiomas no son regulares.

Básicamente, un idioma no es regular si necesita algún tipo de memoria o capacidad de contar. El lenguaje de paréntesis correspondiente no es regular, por ejemplo, porque la máquina necesita recordar si ha abierto un paréntesis para saber si tiene que cerrar uno.

El lenguaje de todas las cadenas utilizando las letras A y B que contienen al menos tres B es un lenguaje regular: un Ba ba ba

El lenguaje de todas las cadenas utilizando las letras A y B que contiene más b's que a's no es regular.

También usted no debe ese idioma todos los finitos son regulares, por ejemplo:

El lenguaje de todas las cadenas menos de 50 caracteres utilizando las letras A y B que contienen más B de que una de es regular, ya que es finito, sabemos que podría describirse como (b | abb | bab | bba | aabbb | ababb | ...) ect hasta que se enumeren todas las combinaciones posibles.