Forum Instytutu Matematycznego UWr

Teraz jest niedziela, 21 lipca 2019 17:52

Strefa czasowa: UTC + 1 [ DST ]




Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 5 ] 
Autor Wiadomość
PostNapisane: środa, 17 grudnia 2014 18:12 
Offline

Dołączył(a): wtorek, 04 lutego 2014 20:22
Posty: 30
Skonstruuj automat skończony, który rozpoznaje słowa, w których nie ma obok siebie dwóch takich samych liter.

Nie mam pojęcia, jak się za to zabrać. Na zajęciach skonstruowaliśmy jedynie taki automat dla słów z alfabetu trzyliterowego. Jakieś pomysły?


Góra
 Zobacz profil  
 
PostNapisane: środa, 17 grudnia 2014 23:45 
Offline
Administrator forum

Dołączył(a): wtorek, 16 marca 2004 15:21
Posty: 65
Zakładam że masz zadany alfabet, a sam automat ma być jednotaśmowy, deterministyczny i nie ma żadnej dodatkowej "pamięci". Jeśli takie są wymogi, to musisz w stanie automatu zapamiętać poprzedni symbol. Tu będzie sporo stanów i przejść między nimi.
Rozrysuj sobie najpierw kawałek automatu który po odczytaniu dwóch symboli będzie w takim stanie, że będziesz mógł jednoznacznie określić jakie dwa symbole właśnie przeczytał. Dzięki temu pojawi się grupa stanów osiągalnych po przeczytaniu pierwszego dowolnego symbolu i grupa stanów po przeczytaniu drugiego dowolnego symbolu. Przeczytanie trzeciego symbolu, to będzie "powrót" z grupy drugiej do odpowiedniego stanu z grupy pierwszej, ale reprezentującego właściwy symbol. To sprawi, że automat zacznie czytać słowa dowolnej długości. Ale nie rysuj jeszcze strzałek. Najpierw trzeba wprowadzić wykrywanie par tych samych symboli - interesuje Cię druga grupa stanów. Tworzysz dodatkowy stan "śmieciowy". Z każdego stanu w drugiej grupie, po przeczytaniu drugi raz tego samego symbolu, automat ma wejść w stan śmieciowy, z którego nie będzie mógł już wyjść. Jak to rozrysujesz, rozrysuj sytuację kiedy automat przeczyta dwa różne symbole - czyli te powroty. Jak to zrobisz, pozostaje określenie które stany są akceptujące.
Jeśli może to być automat niedeterministyczny lub taki, który ma jakąś dodatkową formę pamięci (druga taśma, druga głowica itp.) to sprawa jest prosta.
Jak nie jesteś pewien, to wrzuć na forum swoją propozycję automatu, to sprawdzimy czy jest dobry.


Góra
 Zobacz profil  
 
PostNapisane: niedziela, 21 grudnia 2014 0:20 
Offline
Avatar użytkownika

Dołączył(a): sobota, 06 grudnia 2008 20:57
Posty: 285
Lokalizacja: Wrocław
To wyżej wydaje mi się przekombinowane. Wystarczy pamiętać jedną ostatnią literę i mieć n+2 stany (początkowy, jeden dla każdej litery, i "ściek").

_________________
Nie bij manekina, bo Ci się mózg powygina


Góra
 Zobacz profil  
 
PostNapisane: niedziela, 21 grudnia 2014 17:54 
Offline

Dołączył(a): wtorek, 04 lutego 2014 20:22
Posty: 30
Mniej więcej tak chciałbym rozwiązać to zadanie: stany dla każdej litery łączą się każdy z każdym, a to umożliwia mi zapamiętanie ostatniej litery. Na wykładzie niestety nie dostaliśmy definicji automatu, ale własności, jakie powinien posiadać. Problem w tym, że nie wiem, ile tych stanów ma być - w zadaniu nie ma nawet podanego alfabetu.


Góra
 Zobacz profil  
 
PostNapisane: poniedziałek, 22 grudnia 2014 11:39 
Offline
Avatar użytkownika

Dołączył(a): czwartek, 24 września 2009 21:38
Posty: 911
Płeć: mężczyzna
Krasser Rapper napisał(a):
Mniej więcej tak chciałbym rozwiązać to zadanie: stany dla każdej litery łączą się każdy z każdym, a to umożliwia mi zapamiętanie ostatniej litery. Na wykładzie niestety nie dostaliśmy definicji automatu, ale własności, jakie powinien posiadać. Problem w tym, że nie wiem, ile tych stanów ma być - w zadaniu nie ma nawet podanego alfabetu.

Sądzę że bez podanego alfabetu nie da się tego zrobić, zwłaszcza automatem skończonym. Podejrzewam że w tle jest jakieś milczące założenie że jest jakiś ustalony, skończony alfabet.


Góra
 Zobacz profil  
 
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 5 ] 

Strefa czasowa: UTC + 1 [ DST ]


Kto przegląda forum

Użytkownicy przeglądający ten dział: Google [Bot] i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
cron
POWERED_BY
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL