Linguagens regulares que não podem ser expressas com apenas duas operações regex

Eu pensei que todos os idiomas regulares pudessem ser expressos com expressões regulares (se um idioma for regular, pode ser expresso com regex), mas me disseram que você precisa das três operações regulares (concatenação, união e estrela) para isso segurar.

Por exemplo, me disseram que se eu pudesse usar apenas as operações regex de união e concatenação (2 em 3), haveria uma linguagem regular que não posso descrever apenas com essas duas.

O mesmo com apenas a estrela e a união Kleene. Quais são alguns exemplos disso?

Com apenas união e concatenação, você não pode descrever nenhum idioma infinito. A união e concatenação só podem produzir muitas seqüências finitas. Com apenas union e a estrela Kleene, você não pode descrever um idioma como , porque não há como concatenar uma expressão gerando apenas a com uma expressão gerando apenas b . Com apenas concatenação e a estrela Kleene, você não pode descrever um idioma como L = { a , b } .$L = \{ab\}$$a$$b$$L = \{a,b\}$

$(a^*b^*c)^*$$d$$d$$d$$d-1$

$A^*$$(ab)^*$$(a(ab)^*b)^*$$(aa)^*$

Se alguém agora permite usar estrelas em estrela, mas não estrelas aninhadas , é um problema em aberto (por pelo menos 45 anos) saber se é possível obter todos os idiomas regulares. Essa questão é conhecida como problema generalizado da altura da estrela . É semelhante ao problema de altura da estrela mencionado por Yuval Filmus, com a diferença de que a complementação agora é permitida.