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

¿Alguien puede explicarme qué es una gramática libre de contexto? Después de mirar la entrada de Wikipedia y luego la entrada de Wikipedia sobre gramática formal, me quedo total y completamente desconcertado. ¿Alguien sería tan amable de explicar qué son estas cosas?

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

No estoy seguro de 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 cambiarse si es así?

Una gramática libre de contexto es una gramática que satisface ciertas propiedades. En informática, las gramáticas describen idiomas; específicamente, describen 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 definiendo 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 para el idioma dada anteriormente es:

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

La forma de interpretar esto es decir que Spuede ser reemplazado por BBB, y Bpuede ser reemplazado por 0, y Bpuede ser reemplazado por 1. Entonces, para construir la cadena 010 podemos hacerlo S -> BBB -> 0BB -> 01B -> 010.

Una gramática libre de contexto es simplemente una gramática donde lo que está reemplazando (a la izquierda de la flecha) es un solo símbolo "no terminal". Un símbolo no terminal es cualquier símbolo que usa 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".

La Teoría del Lenguaje está relacionada con la Teoría de la Computación. Cuál es el lado más filosófico de la informática, acerca de decidir qué programas son posibles, o cuáles serán posibles de escribir, y qué tipo de problemas es imposible resolver para escribir un algoritmo.

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

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

E idiomas regulares: http://en.wikipedia.org/wiki/Regular_language

Todos los idiomas regulares son idiomas libres de contexto, pero hay idiomas libres de contexto que no son regulares. Un lenguaje libre de contexto es el conjunto de todas las cadenas aceptadas por un gramatizador libre de contexto o un autómata pushdown que es una máquina de estados finitos con una sola 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 que puedas escribir en tu 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 libro de texto de tercer año de Introducción a la informática fue bastante bueno para explicar estas cosas: Introducción a la teoría de la computación. Por Michael Sipser. Pero me costó como $ 160 comprarlo nuevo y no es muy grande. Tal vez pueda encontrar una copia usada o encontrar una copia en una biblioteca o algo que pueda ayudarlo.

EDITAR:

Las limitaciones de las expresiones regulares y las clases de idiomas superiores se han investigado mucho durante los últimos 50 años aproximadamente. Es posible que le interese el lema de bombeo para idiomas regulares. Es un medio para demostrar 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 Context Free, lo que significa que podría ser descrito por un Context Free Grammer, o puede estar incluso en una clase de idioma superior, puede probar que no es Context Free por el lema de bombeo de Context Free lenguajes que es similar al de las expresiones regulares.

Un idioma puede ser incluso indecidible, lo que significa que incluso una máquina de Turing (puede ser un programa que su computadora pueda ejecutar) no puede programarse para decidir si una cadena debe aceptarse como en el idioma o rechazarse.

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

Básicamente, un idioma no es regular si necesita algún tipo de memoria o capacidad para contar. El lenguaje de los paréntesis coincidentes 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 idioma de todas las cadenas que usan las letras ayb que contienen al menos tres b es un idioma regular: a ba ba ba

El idioma de todas las cadenas que utilizan las letras ayb que contienen más b que a no es regular.

Además, no debería saber que todos los lenguajes finitos son regulares, por ejemplo:

El lenguaje de todas las cadenas de menos de 50 caracteres con las letras ayb que contienen más b que a 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.