Wątek przeniesiony 2015-11-23 00:38 z Edukacja przez somekind.
Witam, czy mógłby ktoś mi podpowiedzieć a najlepiej wytłumaczyć (w miarę możliwości) jak sprawdzić czy napis składający się z liter: "a", "b", "c" jest poprawny jeśli spełnione są 2 warunki:
Napisy poprawne: abc, aabac, cab, ccabaab
Niepoprawne: aab, acb, aba, bac
Nie będę ukrywał, że kompletnie nie mam na to pomysłu.
Sprawdzałbym to w dwóch etapach (pewnie da sie w jednym ale nie chce mi sie kombinować):
b to przesuwa sie w prawo znów do stanu S1, a jeśli jest nim b to przesuwa sie w lewo do stanu S2. Stan S2 sprawdza czy symbol na którym stoi jest równy a, jeśli jest to przesuwa się w prawo do stanu S3, jeśli nie jest to kończy obliczenia bo warunek nie jest spełniony. Stan S3 po prostu przesuwa się w prawo do stanu S1 (jest tylko po to żeby pominąć już sprawdzony symbol). To nam generalnie załatwia warunek 1a. Idziemy sobie więc stanem T1 po ciągu wejsciowym i szukamy a. Jeśli mamy coś innego to przesuwamy sie dalej w stanie T1, jeśli trafimy na a to wchodzimy do stanu T2 który szuka "pary" dla a. W stanie T2 przesuwamy się tak samo jak w T1, ale jak znajdziemy a to przechodzimy znów w stan T1. Czyli jeśli jesteśmy w stanie T1 to znaczy że szukamy pierwszego a a jak w stanie T2 to szukamy drugiego a. I teraz jeśli dojdziemy do końca wejścia i jesteśmy w stanie T1 to znaczy że była przysta ilość a i wejście nie jest poprawne, a jeśli jesteśmy w stanie T2 to znaczy że a były nieparzyste i wejście jest poprawne.Jak bym to zrobił w następujący sposób:
masz 4 stany zależne od tego czy wczytana była parzysta/nieparzysta liczba "a" oraz czy ostatnią wczytaną literą było "a" czy coś innego
do tego 2 stany kończące: jeden dla akceptacji drugi dla braku
zaczynasz od stanu odpowiadającego parzystej liczbie "a" i ostatniej literze różnej od "a"
Wypełnienie tabelki przejść takiej MT wydaje się być dość oczywiste.