[Teoria złożoności][Automaty] Maszyny Turinga

[Izaizaiza6]

Dzień dobry.
Mam problem z niżej wymienionymi zagadnieniami, które chcialabym pojąć w ramach przedmiotu Teorie Obliczeń na uniwersytecie. Na prawdę nie wiem, do jakiej dziedziny to zaliczyć, bo studiuję Kognitywistykę, więc z gory proszę o ewentualne przekierowanie, jeśli umieściłam w złym dziale.
Uprzejmie proszę o pomoc!

1A. Zaprojektuj automat skończony, który rozpoznaje dany język (przykład do wyboru, proszę o ppdanie,, chciałabym zrozumieć ideę zasad tworzenia takiego automatuna podstawie wybranego języka) deterministyczny.

1B. Zaprojektuj automat skończony, który rozpoznaje dany język (przykład do wyboru, proszę o ppdanie,, chciałabym zrozumieć ideę zasad tworzenia takiego automatuna podstawie wybranego języka) niedeterministyczny.

2. Mając rysunek w/w automatu, podaj jego opis formalny (i odwrotnie).

3. Mając dany niedeterministyczny automat skończony, zbuduj automat deterministyczny, który jest równoważny automatowi wyjściowemu.

4. Podaj wyrażenie regularne odpowiadające podanemu językowi (np. język nad alfabetem \(\displaystyle{ \{0,1\}}\), do którego należą wszystkie słowa zaczynające się \(\displaystyle{ 1}\)). I odwrotnie.

5. Mając wyrażenie regularne zaprojektuj automat skończony, którego język odpowiada temu wyrażeniu regularnemu (również do wymyślenia dla przykładu).

6. Mając dane języki \(\displaystyle{ A}\) oraz \(\displaystyle{ B}\) (proszę przedstawić propozycje) znajdź automat, który rozpoznaje sumę, gwiazdkę, dopełnienie, konkatenację oraz przekrój \(\displaystyle{ A}\) oraz \(\displaystyle{ B}\). Oprócz tzw. ‘skrzynek’ podaj opis formalny funkcji przejścia.

Dzięki