21
¿Cómo puedo saber si los idiomas están libres de contexto o no?¿Cómo puedo determinar si un idioma no tiene contexto o no?
A
Respuesta
1
Necesita una gramática para el idioma para determinar si es libre de contexto. Una gramática está libre de contexto si todas sus producciones tienen forma "(no terminal) -> secuencia de terminales y no terminales".
22
Primero, intente construir un context-free grammar que forma el idioma en el asunto. Una gramática no tiene contexto si los lados izquierdos de todas las producciones contienen exactamente un símbolo no terminal. Por definición, si uno existe, entonces el lenguaje está libre de contexto.
Una construcción equivalente sería pushdown automaton. Es lo mismo que DFA, pero con una pila disponible. Puede ser más fácil de construir que una gramática.
Sin embargo, si no logras crear una gramática o un autómata, no significa que un idioma no esté libre de contexto; quizás, eres solo tú el que no puede construir una gramática lo suficientemente complicada (por ejemplo, una vez pasé unas 7 horas para construir una gramática para un lenguaje complicado).
Si comienza a dudar de que el idioma no tenga contexto, debe usar el llamado "pumping lemma for context-free languages". Describe una propiedad de todos lenguajes sin contenido, y si tu idioma no lo permite, entonces no es en absoluto contexto (ver usage notes en Wikipedia).
Este lema es un corolario de Ogden's lemma. Entonces Ogden's es más poderoso, y si no aplicas el lemma de bombeo, puedes probar Ogden (se usa de la misma manera).
+2
Todo esto es bueno, pero te das cuenta de que nada de esto determina por completo una respuesta, ¿verdad? ¿Qué sucede si no puede encontrar una gramática libre de contexto y el lema de Ogden no contradice ninguna propiedad conocida de su idioma? Todavía estás atascado con el problema. (Lo cual creo que es difícil, por lo que su respuesta es tal vez buena, solo indica que no es exhaustiva) – ShreevatsaR
+1
@ShreevatsaR, exactamente. Puede suceder que ninguno de los anteriores funcione. Pero en realidad no sé qué hacer en ese caso. –
2
Editar
Como se sugiere en los comentarios para probar un lenguaje que sea no-CFG, creo que es mediante el uso de un lema Ogdens. La mala interpretación inherente contenida en mi respuesta anterior debe ser excusada :) Retener la respuesta anterior para los acechadores.
respuesta Antiguo
Al mirar la gramática y reglas utilizado! Como se ve en la imagen (cortesía wikipedia chomsky hierarchy). Solo los idiomas regulares no tienen contexto. Implicar cualquier cosa que use cosas de la forma A-> aB o A-> Ba solo no está libre de contexto.
Editar A-> aB y A-> Definiciones Ba tienen el propósito de expresar izquierda y gramáticas recursivas derecho y no deben ser tomadas literalmente.
+1
Técnicamente, los lenguajes regulares están libres de contexto, pero estoy de acuerdo en que el término "sin contexto" se usa a menudo para indicar "sin contexto, pero no regular", es decir, que las etiquetas del diagrama se aplican a las áreas de encerramiento más pequeñas están dentro, en lugar de los círculos más pequeños en los que se encuentran. – reinierpost
+3
"Solo los idiomas regulares no tienen contexto". ¿Qué? Creo que estás leyendo el diagrama al revés. Los idiomas regulares son un subconjunto de idiomas libres de contexto y, por lo tanto, definitivamente no tienen contexto. Sin embargo, la mayoría de los lenguajes sensibles al contexto son * no * sin contexto, lo que hace que los lenguajes contextuales sean un superconjunto estricto de lenguajes sin contexto. – sepp2k
+0
Sepp2k, quise decir aquellos en términos de poder expresivo. Por ejemplo, el poder expresivo de los lenguajes libres de contexto es mucho más alto que el de los lenguajes normales. Una gramática regular ** no ** tendrá el mismo poder expresivo. Sin embargo, un CSL puede ser más expresivo que un CFG. Entonces un CSL definitivamente es un candidato para CFG pero RG no lo es. – questzen
Cuestiones relacionadas
- 1. ¿Cómo determinar si un idioma es recursivo o recursivo enumerable?
- 2. ¿Cómo puedo determinar si intento devolver un error o no?
- 3. ¿Cómo determinar si una cadena tiene caracteres no alfanuméricos?
- 4. ¿Cómo puedo determinar si un objeto ConstructorInfo tiene un parámetro no administrado?
- 5. cómo saber si un UITextView tiene un foco o no
- 6. ¿Cómo determinar si un campo tiene foco?
- 7. ¿Cómo determinar si un idioma es LL (1)?
- 8. ¿Cómo puedo determinar si un objeto o referencia tiene una coerción de cadena válida?
- 9. Python: compruebe si un sistema tiene 32 o 64 bits para determinar si ejecuta la función o no.
- 10. Determinar si QTableView tiene un editor abierto
- 11. ¿Cómo detectar si el iPhone tiene pantalla Retina o no?
- 12. ¿Cómo puedo verificar si una URL tiene un enlace en botw.org o no?
- 13. ¿Cómo puedo verificar si un servidor tiene ssl enable o no?
- 14. ¿Cómo puedo averiguar si un archivo es un archivo o directorio si no existe?
- 15. ¿Cómo determinar si un dispositivo Android tiene una pantalla táctil?
- 16. ¿Cómo puedo verificar si existe o no un recurso incrustado?
- 17. cómo verificar si div tiene id o no?
- 18. ¿Cómo puedo determinar si una aplicación .NET tiene 32 o 64 bits?
- 19. Cómo iniciar un intento si el contexto no es Contexto de actividad sino contexto de aplicación
- 20. ¿Cómo puedo determinar mediante programación si la barra de tareas de Windows está oculta o no?
- 21. En PowerShell, ¿cómo puedo determinar si la unidad actual es una unidad en red o no?
- 22. Determinar si una matriz es asociativa (hash) o no
- 23. ¿Cómo determinar si un flotador tiene una parte fraccionaria?
- 24. PHP detectar si la búsqueda tiene fecha o no
- 25. ¿Cómo determinar cuándo NSTextFieldCell isHighlighted no tiene foco?
- 26. Cómo comprobar si SQLDataReader no tiene filas
- 27. SQL portátil para determinar si existe una tabla o no?
- 28. ¿Cómo determinar si un elemento DOM específico es visible o no?
- 29. ¿Cómo puedo saber si mi programa tiene ARC habilitado o no?
- 30. Determinar si un vector no ordenado <T> tiene todos los elementos únicos
Sí, gracias. Entonces 0^n 1^n está libre de contexto. entonces El complemento de {(0^n1^n)^m | m, n> 0} está libre de contexto o no. – user423733
Debe señalarse que el hecho de que se pueda obtener una gramática sin contexto para un idioma no significa que no exista una gramática libre de contexto para ese idioma. En resumen, solo puedes usar la construcción de una gramática para mostrar que un idioma no tiene contexto, no para mostrar que no lo es. – sepp2k