[Automaty] DAS dla słów kończących się dwoma zerami

rajkowski
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 14 paź 2009, o 11:17
Płeć: Mężczyzna
Lokalizacja: /dev/null
Podziękował: 2 razy

[Automaty] DAS dla słów kończących się dwoma zerami

Post autor: rajkowski »

Mam takie zadanie:

Skonstruuj DAS akceptujący język L nad alfabetem S={0,1} złożony ze słów kończących się dwoma zerami.

Jednak nie wiem zupełnie jak się za nie zabrać, to co odbywa się na wykładzie w ogóle nie przydatne.... Proszę o jakąś pomoc w formie wskazówek co do rozwiązania.
Ostatnio zmieniony 19 sty 2014, o 12:46 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Crizz
Użytkownik
Użytkownik
Posty: 4094
Rejestracja: 10 lut 2008, o 15:31
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 12 razy
Pomógł: 805 razy

[Automaty] DAS dla słów kończących się dwoma zerami

Post autor: Crizz »

Tutaj masz diagram przejścia przykładowego automatu realizującego założenia.


Stanem początkowym jest \(\displaystyle{ q_{0}}\), a stanem końcowym \(\displaystyle{ q_{2}}\).

Cały dowcip polega na tym, żeby w dowolnym momencie (tzn z dowolnego stanu) można było wybrać zarówno 0, jak i 1, ale żeby jednocześnie do stanu końcowego można było wejść tylko poprzez (co najmniej) dwukrotne wybranie etykiety przejścia 0. Zauważ, że tutaj kręcisz się między q0 a q1 dopóki w słowie nie pojawią się dwa zera obok siebie. Wtedy automat jest w stanie q2 i ma do wyboru: albo zakończyć pracę (prawidłowo, bo w słowie właśnie są na końcu dwa zera), albo dostawić dowolną ilość zer i zakończyć pracę, albo po ciągu dowolnej ilości zer wybrać etykietę 1 i wrócić do q0 (skąd znowu możesz wybrać albo 0 albo 1 itd.). Po chwili zastanowienia można dojść do wniosku, że ten automat akceptuje dowolny ciąg znaków, o ile kończy się dwoma zerami.

Automat skończony opisują nastepujące parametry:
zbiór dopuszczalnych stanów: \(\displaystyle{ \{q_{0},q_{1},q_{2}\}}\)
alfabet wejściowy: \(\displaystyle{ \{0,1\}}\)
funkcja przejścia:
\(\displaystyle{ \begin{tabular}{c|cc}

& 0 & 1 \\ \hline
q_0 & q_1 & q_0 \\
q_1 & q_2 & q_0 \\
q_2 & q_2 & q_0 \\
\end{tabular}}\)

(funkcja przejścia pokazuje, do jakiego stanu można przejść, używając danej etykiety przy danym obecnym stanie automatu)
stan początkowy: \(\displaystyle{ q_{0}}\)
zbiór stanów końcowych: \(\displaystyle{ \{q_{2}\}}\)
Ostatnio zmieniony 25 paź 2009, o 01:24 przez czeslaw, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
chrumek
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 1 lut 2013, o 22:36
Płeć: Mężczyzna
Podziękował: 12 razy

[Automaty] DAS dla słów kończących się dwoma zerami

Post autor: chrumek »

Czy mogę jeszcze raz prosić o rysunek.
ODPOWIEDZ