¿Es este lenguaje libre de contexto?

8

Es el idioma

L={una,si}{(unanortesinorte)nortenorte1}

sin contexto? Creo que la respuesta es que no es una CFL, pero no puedo probarlo con el lema de Ogden o el lema de Pumping.

Andrés Felipe Téllez Crespo
fuente
Crossposted en matemáticas . SE ; por favor no hagas eso! ¿Revisaste la pregunta que te señalé? Incluya sus intentos y por qué fallan.
Raphael
El teorema de Parikh funciona para{(unanortesinorte)nortenorte1} pero no para L; Desafortunadamente,Ψ{una,si}[L]=norte2. Incluso el lema de Intercambio parece cumplirse. Wow, desagradable.
Raphael

Respuestas:

8

Insinuación:

si

Solución:

{(unanortesinorte)nortenorte1}={unanorte1sinorte2...unanorte2k-1sinorte2k}:k1norte1=kyo.norteyo=norteyo+1}


y por lo tanto el complemento es

{una,si}{(unanortesinorte)nortenorte1}={unanorte1sinorte2...unanorte2k-1sinorte2k:norte1kyo.norteyonorteyo+1}


que no tiene contexto, ya que puede escribir fácilmente un PDA no determinista.
sdcvvc
fuente
2
Ooohhh! * facepalm * Quizás quieras agregar el truco de diseño central; Puede que no sea obvio para el novato.
Raphael
No entiendo, pensé que el complemento de una CFL no era CFL en general. Gracias
Andrés Felipe Téllez Crespo
{(unanortesinorte)norte}no está libre de contexto, pero su complemento sí.
sdcvvc
@ AndrésFelipeTéllezCrespo: El complemento de una CFL no siempre es CFL (por lo que no hay propiedad de cierre), pero nadie dice que no haya CFL cuyo complemento sea CFL. En particular, todos los complementos de todos los idiomas regulares están libres de contexto (porque incluso son regulares).
Raphael
Idiomas similares a L- una disyunción finita de condiciones adecuadas - se puede resolver utilizando el no determinismo: adivine la condición violada y verifique que se viole (ignore el resto).
Raphael