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^*}$.