Preguntas etiquetadas con context-free

9
Si

Estoy atrapado resolviendo el siguiente ejercicio: Argumenta que si tiene contexto y es regular, entonces (es decir, el cociente correcto ) no tiene contexto.R L / R = { w ∣ ∃ x ∈ RLLLRRRL / R = { w ∣ ∃ x ∈ RS tw x ∈ L }L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\}...

9
Expresividad de las expresiones regulares modernas.

Recientemente hablé con un amigo sobre un sitio web que propuso desafíos de expresiones regulares, principalmente haciendo coincidir un grupo de palabras con una propiedad especial. Estaba buscando una expresión regular que coincida con cadenas como ||||||||donde el número |es primo. Inmediatamente...

8
Idiomas sin contexto cerrados bajo inversión

En la clase de esta semana hemos estado aprendiendo sobre las CFL y sus propiedades de cierre. He visto pruebas de unión, intersección y cumplido, pero para la reversión, mi profesor acaba de decir que está cerrado. Quería ver la prueba, así que he estado buscando durante los últimos días, pero...

8
Es el idioma

Es el idioma L={0n1m∣n and m are co-prime}L={0n1m∣n and m are co-prime} L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\} sin contexto? Supongo que no está libre de contexto porque parece demasiado complicado para que un PDA decida si 2 números son primos o no. Traté de usar el lema de...