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.
[Automaty] DAS dla słów kończących się dwoma zerami
-
- 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
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}\}}\)
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.
Powód: Poprawa wiadomości.