Seja um alfabeto finito. Para um determinado idioma L ⊆ A * o monoid sintática M ( L ) é uma noção bem conhecida na teoria da linguagem formal. Além disso, um monóide M reconhece uma linguagem L se existir um morfismo φ : A ∗ → M tal que L = φ - 1 ( φ ( L ) ) ) .
Então temos o bom resultado:
Um monóide reconhece L ⊆ A ∗ se M ( L ) é uma imagem homomórfica de um submonóide de M (escrito como M ( L ) ≺ M ).
O acima é geralmente estados no contexto de linguagens regulares, e os monoides acima são todos finitos.
Agora, suponha que substituamos com um monóide arbitrário N , e dizemos que um subconjunto L ⊆ N é reconhecido por M se existe um morfismo φ : N → M, de modo que L = φ - 1 ( φ ( L ) ) . Ainda temos que, se M reconhece L , então M ( L ) ≺ M (veja S. Eilenberg, Autômatos, Máquinas e Idiomas, Volume B), mas o inverso é válido?
Na prova de o inverso é comprovado pela exploração da propriedade de que se N = φ ( M ) para algum morfismo φ : M → N e ψ : A ∗ → N também é um morfismo, então podemos encontrar ρ : A ∗ → M tal que φ ( ρ ( u ) ) = ψ ( u ) se mantenha, simplesmente escolhendo ρ ( x ) ∈ para cada x ∈ A e prolongando-se este a um morfismo de A * a M . Mas isso não funciona para monoides arbitrários N, então espero que o inverso acima seja falso então. E se for falsa, para que tipo de monoid lado A * é ainda verdadeiro, e que aqueles monoids têm recebido atenção na literatura de pesquisa?
Respostas:
Sim, esses monóides receberam atenção na literatura de pesquisa e, na verdade, levam a perguntas difíceis.
Definição . Um monóide é chamado projetivo se a seguinte propriedade é válida: se f : N → R é um morfismo monóide e h : T → R é um morfismo surjetivo, existe um morfismo g : N → T tal que f = h ∘ g .N f:N→R h:T→R g:N→T f=h∘g
Você pode encontrar uma longa discussão sobre monoides projetivos em [1], logo após a definição 4.1.33. Mostra-se, em particular, que todo semigrupo finito projetivo é uma banda (um semigrupo no qual todo elemento é idempotente). Mas o inverso não é verdadeiro e é realmente um problema aberto decidir se um semigrupo finito é projetivo.
[1] J. Rhodes e B. Steinberg, a teoria- de semigrupos finitosq . Monografias Springer em Matemática. Springer, Nova York, 2009. xxii + 666 pp. ISBN: 978-0-387-09780-0
fonte