Simón, miembro de nuestro staff, nos hizo el favor de crear este post ya que domina muy bien el tema.
Solución:
Una gramática libre de contexto es una gramática que satisface ciertas propiedades. En informática, las gramáticas describen lenguajes; específicamente, describen lenguajes formales.
Un lenguaje formal es solo 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 “string”). 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 transformaciones que puede realizar para construir una string en el idioma descrito por una gramática. Las gramáticas dirán cómo transformar un símbolo de inicio (generalmente S) en algún string 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 S puede ser reemplazado por BBB, y B puede ser reemplazado por 0, y B puede ser reemplazado por 1. Entonces, para construir el string 010 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 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 están libres de contexto ya que contienen reglas como AB -> 1 que tienen más de un símbolo no terminal a la izquierda.
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 las Ciencias de la Computación, 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 pueda escribir en su computadora) para decidir si un string 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 las Ciencias de la Computación 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. Puede que le interese el lema de bombeo de los idiomas habituales. 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 incluso puede estar 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 ni siquiera una máquina de Turing (puede ser un programa que su computadora pueda ejecutar) no puede programarse para decidir si un idioma string 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 utilizan las letras ayb que contienen al menos tres b es un idioma regular: alicenciado en Letraslicenciado en Letraslicenciado en Letras
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.
Si aceptas, tienes el poder dejar un post acerca de qué te ha impresionado de esta reseña.