Existe alguma hierarquia "legal" conhecida (pode ser finito) dentro da classe de idiomas regulares ? Por legal aqui, as classes em cada hierarquia capturam expressividade / poder / complexidade diferentes. Além disso, a composição de cada classe é "bem" demonstrada por alguns elementos (diferentemente do problema de altura da estrela que pode ser problemático).
Obrigado!
automata-theory
regular-language
regular-expressions
raja.damanik
fonte
fonte
Respostas:
Aqui está uma lista de várias hierarquias de interesse, algumas das quais já foram mencionadas em outras respostas.
Uma linguagem é um produto marcado de L 0 , L 1 , … , L n se L = L 0 a 1 L 1 ⋯ a n L n para algumas letras a 1 , … , a n . As hierarquias de concatenação são definidas alternando operações booleanas e operações polinomiais (= união e produto marcado). A hierarquia de Straubing-Thérien (ponto de partida { ∅ , A ∗ } )L L0,L1,…,Ln L=L0a1L1⋯anLn a1,…,an {∅,A∗}) e a hierarquia de profundidade de ponto (ponto inicial é desse tipo, mas você pode usar outros pontos de partida, principalmente os idiomas do grupo (idiomas aceitos por um autômato de permutação).{∅,{1},A+,A∗})
O padrão geral é contar o número mínimo de estrelas aninhadas necessárias para expressar um idioma a partir das letras, mas várias variantes são possíveis, dependendo dos operadores básicos permitidos. Se você permite somente união e produto, define a altura da estrela restrita, se você permite união, complemento e produto, define a altura da estrela (generalizada) e se permite união, interseção e produto, define a altura da estrela intermediária . Existem idiomas de estrela restrita para cada n e efetivamente podem computar efetivamente a altura da estrela de um determinado idioma regular. Para a altura da estrela, a altura da estrela 0 é decidível ( idiomas sem estrelas ), existem idiomas da altura da estrela 1n n 0 1 , mas nenhum idioma da altura da estrela é conhecido! Nenhum resultado é conhecido na altura intermediária da estrela. Veja este documento para uma visão geral.2
Há muitos deles, mas um dos mais importante é o chamado hierarquia. Uma fórmula é dito ser um Σ n -Fórmula se que é equivalente a uma fórmula da forma de Q ( x 1 , . . . , X k ) φ onde φ é quantificador livre e Q ( x 1 , . . . , X k ) é uma sequência de nΣn Σn Q(x1,...,xk)φ φ Q(x1,...,xk) n blocos de quantificadores de modo a que o primeiro bloco contém apenas quantificadores existenciais (nota que este primeiro bloco pode estar vazia), o segundo bloco quantificadores universais, etc. Da mesma forma, se é formado de n alternando blocos de quantificadores começando com um bloco de quantificadores universais (que novamente pode estar vazio), dizemos que φ é um Π n -Fórmula. Designam por Σ n (resp. Π n ) a classe de linguagens que podem ser definidas por uma Σ n -Fórmula (resp. Um ΠQ(x1,...,xk) n φ Πn Σn Πn Σn fórmula n ) e por B Σ n o fechamento booleano daslínguas Σ n . Finalmente, deixe Δ n = Σ n ∩ Π n . A imagem geral se parece com essa.
É claro que é necessário especificar a assinatura. Geralmente, há um predicado um para cada letra (e um x significa que existe uma carta um na posição X na palavra). Então pode-se adicionar um símbolo binário <Πn BΣn Σn Δn= Σn∩ Πn uma a x uma x < (a hierarquia correspondente é a hierarquia Straubing-Thérien) e também um símbolo sucessor (a hierarquia correspondente é a hierarquia de profundidade dos pontos). Outras possibilidades incluem a predicado, a contar modulo n , etc. Veja novamente este papel para uma visão geral.Mo d n
O padrão geral (que não é específico para idiomas regulares) é devido a Hausdorff. Seja uma classe de idiomas que contém o conjunto vazio e o conjunto completo e fechado sob interseção finita e união finita. Deixe- D n ( L ) ser a classe de todas as línguas de forma X = X 1 - X 2 + ⋯ ± X n em que X i ∈ L e X 1 ⊇ X 2 ⊇ X 3 ⊇ ⋯ ⊇ X n . Desde aeu Dn( L )
Um resultado de Krohn-Rhodes (1966) afirma que todo DFA pode ser simulado por uma cascata de autômatos de redefinição (também chamados de flip-flop) e autómatos cujos semigrupos de transição são grupos finitos. A complexidade do grupo de um idioma é o menor número de grupos envolvidos nessa decomposição do DFA mínimo do idioma. Os idiomas de complexidade são exatamente os idiomas sem estrelas e existem idiomas de qualquer complexidade. No entanto, nenhuma caracterização efetiva das linguagens de complexidade 1 é conhecida.0 0 1
O ponto de partida é o belo artigo que mostra em particular que a classe A C 0 ∩ R e g é decidível. Deixe Um C C ( q ) = { L ⊆ { 0 , 1 } * | L ⩽ Um C 0 M O D q } , em que H S D Q = { u ∈ { 0 , 1 }[ 1 ] A C0 0∩ R e g A CC( q) = { L ⊆ { 0 , 1 }∗∣ L ⩽A C0 0MO Dq} . Se q divide q ′ , então A C C ( q ) ⊆ A C C ( q ′ ) . Uma questão interessante é saber se A C C ( q ) ∩ R e g é decidível para qualquer q .MO Dq={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. Línguas regulares em N C 1 . J. Comput. Sci do sistema 44(1992)[1] NC1
fonte
Expandindo o comentário: uma hierarquia natural é a induzida pelo número de estados do DFA.
Podemos definir queLn={L∣ exists an n-states DFA D s.t. L(D)=L}
( , | Q | = n )D={Q,Σ,δ,q0,F} |Q|=n
Claramente (basta usar estados mortos)Ln⊆Ln+1
Para mostrar a inclusão adequada , podemos simplesmente escolher o idioma: L n + 1 = { a i ∣ i ≥ n } ∈ L n + 1Ln⊊Ln+1 Ln+1={ai∣i≥n}∈Ln+1
Muito informalmente: o DFA (mínimo) que reconhece deve ser uma "cadeia de estados" de comprimento n + 1 : q 0 → a q 1 → a . . . → a q n , F = { q n } e q n → a q n ( q n possui um auto-loop). Portanto, n + 1 estados são suficientes para aceitar{ai∣i≥n} n+1 q0→aq1→a...→aqn F={qn} qn→aqn qn n+1 . Mas todo caminho aceitante de q 0 até um estado final q f que é estritamente menor que n + 1 deve aceitar alguns a i com i < n que não pertence a L n + 1 , portanto, um DFA com n ou menos estados não pode aceite L n + 1 .Ln+1 q0 qf n+1 ai i<n Ln+1 n Ln+1
fonte
Recentemente, deparei-me com este artigo, que pode dar outro exemplo relevante (cf. a última frase do resumo):
Guillaume Bonfante, Florian Deloup: O gênero das línguas regulares.
Resumo: O artigo define e estuda o gênero de autômatos determinísticos de estado finito (FSA) e linguagens regulares. De fato, uma FSA pode ser vista como um gráfico para o qual surge a noção de gênero. Ao mesmo tempo, um FSA tem uma semântica através de sua linguagem subjacente. É então natural estabelecer uma conexão entre as línguas e a noção de gênero. Depois de introduzir e justificar a noção de gênero para linguagens regulares, [...] construímos linguagens regulares de gênero grande arbitrário: a noção de gênero define uma hierarquia apropriada de linguagens regulares.
fonte
Existem várias hierarquias naturais para idiomas regulares de palavras infinitas, que transmitem uma noção de "complexidade do idioma", por exemplo:
Essas hierarquias podem ser generalizadas para idiomas regulares de árvores infinitas, para as quais novas hierarquias aparecem, veja, por exemplo, esta resposta .
fonte