¿Qué es una Gramática Libre de Contexto?
¿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 gramática formal, me quedo totalmente aturdido. ¿Sería alguien tan amable de explicar qué son estas cosas?
Me pregunto esto porque deseo investigar el análisis, y también por un lado, la limitación de un motor regex.
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, tal vez esto podría ser movido si es así?
2 answers
Una gramática libre de contexto es una gramática que satisface ciertas propiedades. En ciencias de la computación, 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 "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 transformaciones que se pueden hacer 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 dado antes es:
S -> BBB
B -> 0
B -> 1
La manera de interpretar esto es decir que S puede ser reemplazado por B, y B puede ser reemplazado por 0, y B puede ser reemplazado por 1. Así que para construir la cadena 010 podemos hacer S - > BBB - > 0BB - > 01B - > 010.
A la gramática libre de contexto es simplemente una gramática donde lo que estás reemplazando (a la izquierda de la flecha) es un solo símbolo "no terminal". Un símbolo no terminal es cualquier símbolo que utilices en la gramática que no pueda aparecer en tus 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".
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-07-15 21:29:07
La Teoría del Lenguaje está relacionada con la Teoría de la Computación. Que es el lado más filosófico de la Informática, sobre 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 lenguaje regular. Un lenguaje regular es un lenguaje que puede ser decidido por un autómata finito determinista.
Usted debe leer el artículo sobre el Estado finito Máquinas: http://en.wikipedia.org/wiki/Finite_state_machine
Y lenguas regulares: http://en.wikipedia.org/wiki/Regular_language
Todos los Lenguajes Regulares son Lenguajes Libres de Contexto, pero hay Lenguajes Libres de Contexto que no son regulares. Un Lenguaje Libre de 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 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 posible programa que pueda 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 libro de texto de introducción a la Informática de tercer año fue bastante bueno para explicar estas cosas: Introducción a la Teoría de la Computación. Por Michael Sipser. Pero, me costó como 1 160 para comprarlo nuevo y no es muy grande. Tal vez usted puede encontrar una copia usada o encontrar una copia en una biblioteca o algo que podría ayudarle.
EDITAR:
Las limitaciones de las Expresiones Regulares y las clases de idiomas superiores han sido investigadas una tonelada en los últimos 50 años. Usted podría estar interesado en el lema de bombeo para los idiomas regulares. Es un medio de probar que un cierto idioma no es ordinarios:
Http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
Si un lenguaje no es regular puede ser Libre de Contexto, lo que significa que podría ser descrito por un Grammer Libre de Contexto, o puede ser incluso en una clase de lenguaje superior, usted podría probar que no es Libre de Contexto por el lema de bombeo para Lenguajes Libres de Contexto que es similar al de las expresiones regulares.
Un lenguaje puede incluso ser indecidible, lo que significa incluso una máquina de Turing (puede programar su computadora puede ejecutarse) no se puede programar para decidir si una cadena debe ser aceptada como en el idioma o rechazada.
Creo que la parte que más le interesa es 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 demostrar qué idiomas no son regulares.
Básicamente un lenguaje no es regular si necesita algún tipo de memoria o habilidad para contar. El lenguaje de los paréntesis coincidentes es no es normal, 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 mediante las letras a y b, que contienen al menos tres b, es un lenguaje regular: unbababa
El lenguaje de todas las cadenas que usan las letras a y b que contienen más b que a no es regular.
También no debe que todo el lenguaje finito sea regular, por ejemplo:
El idioma de todas las cadenas de menos de 50 caracteres usando las letras a y b que contienen más b que a es regular, ya que es finito sabemos que podría ser descrito como (b|abb|bab|bba|aabbb|ababb|...) ect hasta que se listen todas las combinaciones posibles.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-07-16 07:03:09