Deje que se dé un número . Considere el siguiente lenguaje L n = { .
En palabras, es el conjunto de cadenas de copia de longitud 2 n .
Considere la siguiente función de complejidad de estado tal que s ( n ) es el número de estados en los autómatas pushdown más pequeños que reconoce L n .
Pregunta: ¿Puede probar formalmente algún límite inferior significativo para ?
Mi conjetura: .
Límite superior conocido: .
Reglas:
(1) El alfabeto de pila debe ser binario.
(2) La cinta de entrada es unidireccional y no puede detenerse en ningún carácter de entrada.
fl.formal-languages
automata-theory
grammars
context-free
Michael Wehar
fuente
fuente
Respuestas:
La técnica descrita por Yuval:
¿Existe un tamaño polinómico CFG que describa este lenguaje finito?
(también puede leer: Límites inferiores en el tamaño de los CFG para idiomas específicos finitos )
fuente