Por que é $ ((AA) ^ * bb (AA) ^ * bb (AA) ^ *) ^ * $ de altura da estrela 1

Question

Uma expressão regular generalizada é como uma expressão regular, mas com mais uma operação permitida: complementação. O (generalizado) Estrela-altura de uma expressão regular generalizada é o número máximo de estrelas de kleene aninhadas. A altura da estrela de uma língua é a altura mínima da estrela de uma expressão regular descrevendo-a. Não se sabe se há até mesmo uma linguagem de estrela 2.

Então eu imagino a langagem $ ((AA) ^ * bb (AA) ^ * bb (AA) ^ *) ^ * (AA) ^ * $ de palavras que consistem em concatenações de $ AA $ e $ BB $ , com um número par de $ BB $ , é de altura da estrela generalizada $ 1 $ . Mas eu não pude provar isso. No papel alguns resultados no problema generalizado de altura da estrela (PIN, Straubing, Thérien), Lema 6.1 (o lema de transferência) não pode ser aplicado porque ambos $ (bb) ^ * $ e $ (AA) ^ * $ são de estrela-altura 1.

Eu vi em outro lugar alguns idiomas que foram conjectured para ser de estrela-altura 2 e eles eram mais complexos do que o que eu dou, por isso é muito provavelmente de estrela - altura 1. é o caso?

Answer 1

(esta é uma tentativa de uma resposta, espero que os detalhes estejam certos.)

Sua linguagem consiste em todas as strings em $ (AA + BB) ^ * $ com um número par de $ bb $ .

Estamos autorizados a usar complementação, então começamos observando o complemento da linguagem. Acho que podemos dividir o complemento em duas partes (sobrepostas)

• strings não da forma $ (AA + BB) ^ * $ , essa linguagem tem starheight.
• strings da forma $ w_0 \ cdot bb \ cdot w_1 \ cdot bb \ cdot w_2 \ dots bb \ cdot w_n $ , onde (1) o número de $ bb $ é ímpar, e (2) a $ w_i $ não contém nenhuma $ BB $ (mas eu terei que ser mais preciso nisso)

Agora vamos tentar encontrar uma expressão para a linguagem $ W $ da $ w_i $ sem usar a estrela. Isso significa que podemos usar a estrela para contar o número ímpar de $ bb $ , como na $ (w \ cdot bb \ cdot w \ cdot bb) ^ * \ cdot w \ cdot bb \ cdot w $ .

Esta é a parte complicada. Strings de $ W $ são

• a string vazia $ \ VAREPSILON $
• apenas uma única $ a $
• da forma $ AXA $ , onde $ a $ não contém $ BB $ . Não "contendo $ bb $ " é o complemento de $ (A + B) ^ * BB (A + B) ^ * $ , e como você sabe $ (A + B) ^ * $ é novamente livre de estrelas.

As strings que agora especificamos podem ter trechos mais longos de $ B $ 's, mas sempre que acontece a $ B $ vêm em pares.