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 {0,1}, do którego należą wszystkie słowa
zaczynające się 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 A oraz B (proszę przedstawić propozycje) znajdź automat, który rozpoznaje sumę,
gwiazdkę, dopełnienie, konkatenację oraz przekrój A oraz B. Oprócz
tzw. ‘skrzynek’ podaj opis formalny funkcji przejścia.
Dzięki
