¿Hay alguna jerarquía "agradable" conocida (puede ser finita) dentro de la clase de lenguajes regulares ? Por bueno aquí, las clases en cada jerarquía capturan diferente expresividad / poder / complejidad. Además, la membresía de cada clase está "bien" demostrada por algunos elementos (a diferencia del problema de altura de la estrella que puede ser problemático).
¡Gracias!
automata-theory
regular-language
regular-expressions
raja.damanik
fuente
fuente
Respuestas:
Aquí hay una lista de varias jerarquías de interés, algunas de las cuales ya se mencionaron en otras respuestas.
Un lenguaje es un producto marcado de L 0 , L 1 , ... , L n si L = L 0 a 1 L 1 ⋯ a n L n para algunas letras a 1 , ... , a n . Las jerarquías de concatenación se definen alternando operaciones booleanas y operaciones polinómicas (= unión y producto marcado). La jerarquía Straubing-Thérien (punto de partida { ∅ , A ∗ } )L L0,L1,…,Ln L=L0a1L1⋯anLn a1,…,an {∅,A∗}) y la jerarquía de profundidad de puntos (punto de partida son de este tipo, pero puede tomar otros puntos de partida, especialmente los idiomas de grupo (idiomas aceptados por un autómata de permutación).{∅,{1},A+,A∗})
El patrón general es contar la cantidad mínima de estrellas anidadas necesarias para expresar un idioma a partir de las letras, pero son posibles varias variantes, dependiendo de los operadores básicos que permita. Si solo permite la unión y el producto, define la altura de estrella restringida, si permite la unión, el complemento y el producto, define la altura de estrella (generalizada) y si permite la unión, la intersección y el producto, define la altura de estrella intermedia . Hay idiomas de estrella restringida para cada ny se puede calcular efectivamente la altura de la estrella de un lenguaje regular determinado. Para la altura de estrella, la altura de estrella 0 es decidible ( idiomas libres de estrellas ), existen idiomas de altura de estrella 1n n 0 1 , pero no se conoce ningún lenguaje de altura de estrella . No se conoce ningún resultado en la altura de estrella intermedia. Consulte este documento para obtener una descripción general.2
Hay muchos de ellos, pero uno de los más importantes es la llamada jerarquía . Una fórmula se dice que es un Σ n fórmula de L si es equivalente a una fórmula de la forma Q ( x 1 , . . . , X k ) φ donde φ es cuantificador libre y Q ( x 1 , . . . , X k ) es una secuencia de nΣn Σn Q(x1,...,xk)φ φ Q(x1,...,xk) n bloques de cuantificadores de tal manera que el primer bloque contiene sólo cuantificadores existenciales (nota que este primer bloque puede estar vacía), los cuantificadores universales segundo bloque, etc. mismo modo, si se forma de n Alternando bloques de cuantificadores que comienzan con un bloque de cuantificadores universales (que nuevamente podrían estar vacíos), decimos que φ es una fórmula Π n . Denote con Σ n (resp. Π n ) la clase de idiomas que puede definirse mediante una fórmula Σ n (resp. A ΠQ(x1,...,xk) n φ Πn Σn Πn Σn fórmula) y por B Σ n el cierre booleano de Σ n- idiomas. Finalmente, dejemos Δ n = Σ n ∩ Π n . La imagen general se ve así.
Uno necesita, por supuesto, especificar la firma. Generalmente hay un predicado a para cada letra (y una x significa que hay una letra a en la posición x en la palabra). Entonces uno puede agregar un símbolo binario <Πn BΣn Σn Δn=Σn∩Πn a ax a x < (la jerarquía correspondiente es la jerarquía Straubing-Thérien) y también un símbolo sucesor (la jerarquía correspondiente es la jerarquía de profundidad de puntos). Otras posibilidades incluyen un predicado , para contar el módulo n , etc. Consulte nuevamente este documento para obtener una descripción general.Mod n
El patrón general (que no es específico de los idiomas regulares) se debe a Hausdorff. Sea una clase de idiomas que contiene el conjunto vacío y el conjunto completo, y se cierra bajo intersección finita y unión finita. Sea D n ( L ) la clase de todos los idiomas de la forma X = X 1 - X 2 + ⋯ ± X n donde X i ∈ L y X 1 ⊇ X 2 ⊇ X 3 ⊇ ⋯ ⊇ X n . Ya queL Dn(L)
Un resultado de Krohn-Rhodes (1966) afirma que cada DFA puede ser simulado por una cascada de autómatas y autómatas de reinicio (también llamados flip-flop) cuyos transiciones en semigrupos son grupos finitos. La complejidad grupal de un lenguaje es el menor número de grupos involucrados en dicha descomposición del mínimo DFA del lenguaje. Los idiomas de complejidad son exactamente los idiomas libres de estrellas y existen idiomas de cualquier complejidad. Sin embargo, no se conoce una caracterización efectiva de los lenguajes de complejidad 1 .0 1
El punto de partida es el bonito artículo que muestra en particular que la clase A C 0 ∩ R e g es decidible. Sea A C C ( q ) = { L ⊆ { 0 , 1 } ∗ ∣ L ⩽ A C 0 M O D q } , donde M O D q = { u ∈ { 0 , 1 }[1] AC0∩Reg ACC(q)={L⊆{0,1}∗∣L⩽AC0MODq} . Si q divide q ′ , entonces A C C ( q ) ⊆ A C C ( q ′ ) . Una pregunta interesante es saber si A C C ( q ) ∩ R e g es decidible para cualquier q .MODq={u∈{0,1}∗∣|u|1≡0modq} q q′ ACC(q)⊆ACC(q′) ACC(q)∩Reg q
Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Idiomas regulares en N C 1 . J. Comput. System Sci. 44(1992)[1] NC1
fuente
Ampliando el comentario: una jerarquía natural es la inducida por el número de estados del DFA.
Podemos definirLn={L∣ exists an n-states DFA D s.t. L(D)=L}
( , | Q | = n )D={Q,Σ,δ,q0,F} |Q|=n
Claramente (simplemente use estados muertos)Ln⊆Ln+1
Para mostrar la inclusión adecuada simplemente podemos elegir el idioma: L n + 1 = { a i ∣ i ≥ n } ∈ L n + 1Ln⊊Ln+1 Ln+1={ai∣i≥n}∈Ln+1
Muy informalmente: el (mínimo) DFA que reconoce debe ser una "cadena de estado" de longitud n + 1 : q 0 → a q 1 → a . . . → a q n , F = { q n } y q n → a q n ( q n tiene un bucle automático). Entonces n + 1 estados son suficientes para aceptar{ai∣i≥n} n+1 q0→aq1→a...→aqn F={qn} qn→aqn qn n+1 . Pero cada ruta de aceptación de q 0 a un estado final q f que es estrictamente más corto que n + 1 debe aceptar alguna a i con i < n que no pertenece a L n + 1 , por lo que un DFA con n o menos estados no puede aceptar L n + 1 .Ln+1 q0 qf n+1 ai i<n Ln+1 n Ln+1
fuente
Recientemente me encontré con este artículo que puede dar otro ejemplo relevante (cf. la última oración del resumen):
Guillaume Bonfante, Florian Deloup: El género de los idiomas regulares.
Del resumen: el artículo define y estudia el género de los autómatas deterministas de estado finito (FSA) y los lenguajes regulares. De hecho, un FSA puede verse como un gráfico para el cual surge la noción de género. Al mismo tiempo, una FSA tiene una semántica a través de su lenguaje subyacente. Entonces es natural hacer una conexión entre los idiomas y la noción de género. Después de presentar y justificar la noción de género para los idiomas regulares, [...] construimos idiomas regulares de género grande arbitrario: la noción de género define una jerarquía adecuada de idiomas regulares.
fuente
Existen varias jerarquías naturales para los idiomas regulares de palabras infinitas, que transmiten una noción de "complejidad del lenguaje", por ejemplo:
Estas jerarquías se pueden generalizar para lenguajes regulares de árboles infinitos, para los cuales aparecen nuevas jerarquías, vea por ejemplo esta respuesta .
fuente