Automat ze stosem

[lbn]

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

[norwimaj]

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.

[lbn]

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}\)

[norwimaj]

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ć.