Zwykłe języki, których nie można wyrazić za pomocą tylko 2 operacji wyrażenia regularnego

Myślałem, że wszystkie języki regularne można wyrazić za pomocą wyrażeń regularnych (jeśli język jest regularny, można go wyrazić za pomocą wyrażenia regularnego), ale powiedziano mi, że potrzebujesz do tego wszystkich trzech operacji regularnych (konkatenacji, zjednoczenia i gwiazdki) trzymać.

Powiedziano mi na przykład, że jeśli mogę korzystać tylko z operacji wyrażenia regularnego zjednoczenia i konkatenacji (2 z 3), istniałby zwykły język, którego nie potrafiłbym opisać tylko tymi dwoma.

To samo z gwiazdą Kleene i związkiem. Jakie są tego przykłady?

Tylko zjednoczenie i konkatenacja nie pozwalają opisać żadnego nieskończonego języka. Zjednoczenie i konkatenacja mogą wytworzyć tylko skończenie wiele łańcuchów. Mając tylko związek i gwiazdę Kleene, nie można opisać języka takiego jak , ponieważ nie ma sposobu na połączenie wyrażenia generującego tylko z wyrażeniem generującym tylko . Tylko konkatenacja i gwiazda Kleene nie pozwalają opisać języka takiego jak .a b L = { a , b $L = \{ab\}$$a$$b$$L = \{a,b\}$

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

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

Jeśli teraz pozwala się na używanie gwiazd, ale nie gwiazd zagnieżdżonych , to jest otwarty problem (przez co najmniej 45 lat), aby wiedzieć, czy można uzyskać wszystkie zwykłe języki. To pytanie jest znane jako ogólny problem wysokości gwiazdy . Jest podobny do problemu wysokości gwiazdy wspomnianego przez Yuvala Filmusa, z tą różnicą, że dopełnianie jest teraz dozwolone.