Cuando se consideran modelos de cómputo de máquinas, la jerarquía de Chomsky normalmente se caracteriza por (en orden), autómatas finitos, autómatas push-down, autómatas lineales y máquinas de Turing. Para el primer y último nivel 1 (lenguajes regulares y lenguajes recursivamente enumerables), no...
Estaba revisando la definición de Wikipedia de lenguaje sensible al contexto y encontré esto: Cada categoría de idiomas es un subconjunto apropiado de la categoría directamente encima de ella. Cualquier autómata y cualquier gramática en cada categoría tiene un autómata o gramática equivalente en...
Estoy tratando de entender las gramáticas sensibles al contexto. Entiendo por qué a los idiomas les gusta { w w ∣ w ∈ A∗}{ww∣w∈A∗}\{ww \mid w \in A^*\} { anortesinorteCnorte∣ n ∈ N }{anbncn∣n∈N}\{a^n b^n c^n \mid n\in\mathbb{N}\} no están libres de contexto, pero me gustaría saber si un...
En realidad, descubrí que el conjunto de lenguajes sensibles al contexto, ( \ mathbf {= NSPACE (O (n)) = LBA} idiomas aceptados) no se discuten tan ampliamente como \ mathbf {REG} (idiomas regulares) o \ mathbf {CFL} (lenguajes sin contexto). Y también el problema abierto \ mathbf {DSPACE (O (n))}...
Estoy buscando una gramática sensible al contexto que describa el siguiente lenguaje: .L = { w w ∣ w ∈ { a , b }∗, | w | ≥ 1 }L={ww∣w∈{una,si}∗,El |wEl |≥1}L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\} Tengo problemas con el hecho de que no se permiten reglas como y, por lo tanto, no puedo...
Se sabe que existe una propiedad de "bombeo" (las palabras de cierta longitud implican la existencia de bucles en el mecanismo de definición del lenguaje) para los lenguajes regulares y libres de contexto y algunos más (generalmente utilizados para refutar la pertenencia de un idioma a una...