grammar - listening - tag questions intonation
jerarquía chomsky en inglés llano (3)
Estoy tratando de encontrar una explicación simple (es decir, no formal) de los 4 niveles de gramáticas formales (no restringido, sensible al contexto, libre de contexto, regular) según lo establecido por Chomsky.
Ha sido una época desde que estudié gramáticas formales, y las diversas definiciones ahora son confusas para que las visualice. Para ser claros, no estoy buscando las definiciones formales que encontrará en todas partes (por ejemplo, here y here , puedo buscar en Google, así como cualquier otra persona), o incluso definiciones formales de cualquier tipo. En cambio, lo que esperaba encontrar era explicaciones claras y sencillas que no sacrificaran la claridad por el bien de la integridad.
En cuanto a los lenguajes regulares, hay muchas caracterizaciones equivalentes. Dan muchas maneras diferentes de mirar los idiomas regulares. Es difícil dar una definición de "inglés simple", y si le resulta difícil entender alguna de las caracterizaciones de los idiomas regulares, es poco probable que una explicación de "inglés simple" sirva de ayuda. Una cosa a tener en cuenta de las definiciones y las diversas propiedades de cierre es que los lenguajes regulares encarnan la noción de "finitud" de alguna manera. Pero esto es nuevamente difícil de apreciar sin una mejor familiaridad con los idiomas regulares.
¿Considera que la noción de un autómata finito no es simple y limpia?
Permítanme mencionar algunas de las muchas caracterizaciones equivalentes (al menos para otros lectores):
- Lenguas aceptadas por autómatas finitos deterministas.
- Idiomas aceptados por autómatas finitos no deterministas
- Idiomas aceptados alternando autómatas finitos
- Idiomas aceptados por autómatas finitos deterministas de dos vías
- Lenguajes generados por gramáticas lineales izquierdas.
- Lenguajes generados por gramáticas lineales derechas.
- Lenguajes generados por expresiones regulares .
- Una unión de algunas clases de equivalencia de una congruencia de derecho de índice finito .
- Una unión de algunas clases de equivalencia de una congruencia de índice finito.
- La imagen inversa bajo un homomorfismo monoide de un subconjunto de un monoide finito.
- Lenguajes expresables en monádica lógica de segundo orden sobre palabras.
Tal vez entienda mejor si recuerda los autómatas que generan estos lenguajes.
Los lenguajes regulares son generados por autómatas regulares. Solo tienen un conocimiento finito del pasado (la memoria de cómputo tiene límites), por lo que cada vez que tenga un idioma con sufijos que dependen de los prefijos (idioma palindrome), esto no se puede hacer con los idiomas normales.
Los lenguajes libres de contexto son generados por autómatas pushdown no deterministas. Tienen un tipo de conocimiento del pasado (la pila, que no está limitada en contraste con los autómatas regulares), pero una pila solo se puede ver desde arriba para que no tenga un conocimiento completo del pasado.
Los lenguajes sensibles al contexto son generados por máquinas de información no deterministas de enlace lineal. Conocen el pasado y pueden lidiar con diferentes contextos porque no son deterministas y pueden acceder a todo el pasado en cualquier momento.
Los lenguajes no restringidos son generados por las máquinas de Turing. De acuerdo con la Iglesia-Turing-Tesis, las máquinas son capaces de calcular todo lo que puedas imaginar (lo que significa que todo es decidible).
Regular: estos idiomas responden sí / no con autómatas finitos
Libre de contexto: estos idiomas cuando se les da una palabra de entrada (usando machene de estado y pila) siempre podemos responder sí / no si es miembro del idioma
Sensible al contexto: siempre que la producción en gramática nunca se reduzca (α -> β) podemos contestar sí / no (utilizando machene de estado y un trozo de memoria que es de tamaño lineal con entrada)
Recursivamente enumerable: Puede responder que sí, pero en caso de no, entrará en un bucle infinito.
Vea this video para una explicación completa.