1. Czy istnieje takie wyrażenie regularne \phi, że L_{a\phi} = L_{\phi b}?

Nie.

Załóżmy nie wprost, że istnieje. Rozważmy u\in L_{a\phi}. Wtedy niewątpliwie u \in L_{\phi b}. A więc u zaczyna się od a i kończy na b. Mamy: u = avb dla pewnego v i dodatkowo av \in L_{\phi} (usuwamy końcowe b z wyrazu będącego w L_{\phi b}) oraz vb \in L_{\phi} (usuwamy początkowe a z wyrazu w L_{a\phi}).

Teraz możemy być nieco bardziej bezczelni i napisać, że aav \in L_{a\phi} (dodajemy a na początku wyrazu będącego w L_{\phi}) oraz vbb \in L_{\phi b} (dodajemy b na końcu wyrazu w L_{\phi b}). Och, ale przecież L_{a\phi} = L_{\phi b}, więc aav \in L_{\phi b} oraz vbb \in L_{a\phi}. To by oznaczało, że v = awb dla pewnego w.

Powtarzając powyższe rozumowanie nieskończenie wiele razy moglibyśmy dojść do wniosku, że u=a^\infty b^\infty, ale przecież wyrażenia regularne nie rozpoznają nieskończonych słów. Doprowadzając do sprzeczności kończymy dowód.

2. Czy istnieje takie wyrażenie regularne \phi, że L_{a^*\phi} = L_{\phi b^*}?

Nom.

To wyrażenie to a^*b^*. Jak łatwo zauważyć, L_{a^*\phi} = L_{a^*a^*b^*} = L_{a^*b^*} = L_{a^*b^*b^*} = L_{\phi b^*}.