Automat ze stosem
-
- Użytkownik
- Posty: 18
- Rejestracja: 2 paź 2006, o 17:58
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Automat ze stosem
hej. mam problem ze stworzeniem automatu ze stosem akceptującego język: \(\displaystyle{ a^{i} b^{k}c^{l}: k>l}\) moze ktos pomoc? bez problemu stworzylem automat z warunkiem \(\displaystyle{ k<l}\) a tego jakos nie moge
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Automat ze stosem
A potrafisz z warunkiem \(\displaystyle{ k\ge l}\)? Pewnie wystarczy tylko zmienić stan akceptujący w tym co zrobiłeś dla \(\displaystyle{ k<l}\). Potem już tylko mała modyfikacja i otrzymasz automat, który chcesz.
-
- Użytkownik
- Posty: 18
- Rejestracja: 2 paź 2006, o 17:58
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1 raz
Automat ze stosem
dla \(\displaystyle{ k<l}\) stworzylem automat:
\(\displaystyle{ (s,I) \xrightarrow{a} (s,I)
(s,I) \xrightarrow{b} (p,AI)
(p,A) \xrightarrow{b} (p,AA)
(p,A) \xrightarrow{c} (q,A)
(q,A) \xrightarrow{c} (q,\epsilon)
(q,I) \xrightarrow{c} (q,I)
(q,I) \xrightarrow{\epsilon} (q,\epsilon)
(s,I) \xrightarrow{c} (q,I)}\)
Byc moze nie jest to optymalne rozwiazanie... ale nie wiem jak to mozna dopasowac dla \(\displaystyle{ k>l}\). Jezeli chodzi o \(\displaystyle{ k \ge l}\) to oczywiscie bez problemu dla \(\displaystyle{ k=l}\), ale juz niestety wlasnie mam problem by dolaczyc do tego \(\displaystyle{ k>l}\)
\(\displaystyle{ (s,I) \xrightarrow{a} (s,I)
(s,I) \xrightarrow{b} (p,AI)
(p,A) \xrightarrow{b} (p,AA)
(p,A) \xrightarrow{c} (q,A)
(q,A) \xrightarrow{c} (q,\epsilon)
(q,I) \xrightarrow{c} (q,I)
(q,I) \xrightarrow{\epsilon} (q,\epsilon)
(s,I) \xrightarrow{c} (q,I)}\)
Byc moze nie jest to optymalne rozwiazanie... ale nie wiem jak to mozna dopasowac dla \(\displaystyle{ k>l}\). Jezeli chodzi o \(\displaystyle{ k \ge l}\) to oczywiscie bez problemu dla \(\displaystyle{ k=l}\), ale juz niestety wlasnie mam problem by dolaczyc do tego \(\displaystyle{ k>l}\)
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Automat ze stosem
Nie wiedziałem że automat ma akceptować poprzez pusty stos. Są różne konwencje co do tego.
Proponuję taką modyfikację. Linijkę
\(\displaystyle{ (p,A) \xrightarrow{c} (q,A)}\)
zamienimy na
\(\displaystyle{ (p,A) \xrightarrow{c} (q,\epsilon).}\)
Teraz jeśli zjemy ze stosu wszystkie symbole \(\displaystyle{ A}\), to już jest źle i nie ma sensu się tym dalej zajmować, więc nie będzie linijek:
\(\displaystyle{ (q,I) \xrightarrow{c} (q,I),\\
(q,I) \xrightarrow{\epsilon} (q,\epsilon),\\
(s,I) \xrightarrow{c} (q,I).}\)
Teraz jeszcze gdy jest dobrze, to przejdźmy do jakiegoś nowego stanu \(\displaystyle{ r}\) i usuńmy wszystko ze stosu.
\(\displaystyle{ (q,A) \xrightarrow{\epsilon} (r,\epsilon),\\
(r,A) \xrightarrow{\epsilon} (r,\epsilon),\\
(r,I) \xrightarrow{\epsilon} (r,\epsilon).}\)
To jest niedeterministyczny automat i być może trudność Ci sprawiało uświadomienie sobie, że można z niedeterminizmu skorzystać.
Proponuję taką modyfikację. Linijkę
\(\displaystyle{ (p,A) \xrightarrow{c} (q,A)}\)
zamienimy na
\(\displaystyle{ (p,A) \xrightarrow{c} (q,\epsilon).}\)
Teraz jeśli zjemy ze stosu wszystkie symbole \(\displaystyle{ A}\), to już jest źle i nie ma sensu się tym dalej zajmować, więc nie będzie linijek:
\(\displaystyle{ (q,I) \xrightarrow{c} (q,I),\\
(q,I) \xrightarrow{\epsilon} (q,\epsilon),\\
(s,I) \xrightarrow{c} (q,I).}\)
Teraz jeszcze gdy jest dobrze, to przejdźmy do jakiegoś nowego stanu \(\displaystyle{ r}\) i usuńmy wszystko ze stosu.
\(\displaystyle{ (q,A) \xrightarrow{\epsilon} (r,\epsilon),\\
(r,A) \xrightarrow{\epsilon} (r,\epsilon),\\
(r,I) \xrightarrow{\epsilon} (r,\epsilon).}\)
To jest niedeterministyczny automat i być może trudność Ci sprawiało uświadomienie sobie, że można z niedeterminizmu skorzystać.