Forum Instytutu Matematycznego UWr

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?

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.

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

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.