[Maszyna Turinga] Akceptacja wyrażenia regularnego

[murfy]

Opisz maszynę Turinga, która akceptuje (kończy w stanie TAK) słowa zadane wyrażeniem regularnym \(\displaystyle{ ab^{*}ba^{*}b^{*}a}\) przy czym zakładamy, że zbiór symboli wejściowych jest równy \(\displaystyle{ \left\{ a, b, -\right\}}\), gdzie \(\displaystyle{ -}\) oznacza klatkę pustą.

Zakładam, że nikt mi nie rozwiąże tego zadania, ale proszę chociaż o wytłumaczenie co oznacza to wyrażenie regularne, czym jest \(\displaystyle{ *}\)

[Afish]

\(\displaystyle{ *}\) to gwiazdka Kleena i oznacza dowolną liczbę wystąpień danego znaku. Twoje wyrażenie regularne w dużym uproszczeniu opisuje dowolne słowo mające jedną literkę \(\displaystyle{ a}\), następnie przynajmniej jedną literkę \(\displaystyle{ b}\), dowolną liczbę liter \(\displaystyle{ a}\), dowolną liczbę liter \(\displaystyle{ b}\) a następnie literkę \(\displaystyle{ a}\).