Automat rozpoznający słowa

[lunex]

Witam, mam zadanka o treści:

Kod: Zaznacz cały

Σ = {0, 1}. Narysuj automat rozpoznający takie słowa, w których liczby symboli 0 i symboli 1 są różne.

Kod: Zaznacz cały

Σ = {0, 1}. Narysuj automat rozpoznający takie słowa, które nie zawierają dokładnie dwóch jedynek.

próbowałem już chyba wszystkiego i dalej mi nie wychodzi ;/
Bardzo proszę o pomoc w rozwiązaniu tych problemów.

[abc666]

Pokaż swoje próby rozwiązania.

[norwimaj]

Nie napisałeś, o jaki automat chodzi.

Pierwszego zadania automatem skończonym się nie da, więc zakładam że chodzi o automat ze stosem. Może być nawet deterministyczny. Na stosie trzymaj informację, który symbol pojawił się więcej razy, i o ile. Na przykład, jeśli zer było o 4 więcej niż jedynek, to na stosie trzymaj 4 zera. Jeśli jedynek było o dwie więcej niż zer, to na stosie trzymaj dwie jedynki. Jeśli jest tyle samo, to pusty stos.

Jeśli na stosie mamy \(\displaystyle{ 0}\) i wczytujemy \(\displaystyle{ 0}\), to odkładamy na stos kolejne \(\displaystyle{ 0}\).
Jeśli na stosie mamy \(\displaystyle{ 0}\) i wczytujemy \(\displaystyle{ 1}\), to zdejmujemy jedno \(\displaystyle{ 0}\) ze stosu.
Jeśli mamy pusty stos i wczytujemy \(\displaystyle{ 0}\), to odkładamy \(\displaystyle{ 0}\) na stos.
Itd.

W zależności od tego, jaki dokładnie model automatu rozważasz, rozwiązanie może się trochę różnić.


W drugim zadaniu wystarczy automat skończony o czterech stanach \(\displaystyle{ q_0,q_1,q_2,q_{\ge3}}\)
Automat jest w stanie \(\displaystyle{ q_i}\), jeśli wczytał \(\displaystyle{ i}\) jedynek. Stan początkowy to \(\displaystyle{ q_0}\), stany akceptujące to wszystkie oprócz \(\displaystyle{ q_2}\). Strzałki pomiędzy stanami są oczywiste.

[lunex]

Strzałki pomiędzy stanami są oczywiste

narysowałem 4 stany połączone strzałkami wczytującymi 0 lub 1 i nadal nie wychodzi
Mógłbyś napisać w jaki sposób mam je połączyć? ;p

[norwimaj]

Strzałki pomiędzy stanami są oczywiste

narysowałem 4 stany połączone strzałkami wczytującymi 0 lub 1 i nadal nie wychodzi
Mógłbyś napisać w jaki sposób mam je połączyć? ;p

A jak Twoim zdaniem powinny być połączone?

[lunex]

No z tego co ja rozumiem każda strzałka musi pozwolić na wczytanie 0 lub 1 czyli jeżeli połączę te 4 stany w "kółeczko" (wynikałoby to ze słowa oczywiste ;p) takimi strzałkami to faktycznie nie da się otrzymać słowa o dokładnie 2 jedynkach ale nie da się również otrzymać słowa 00, 10 czy 01.

[norwimaj]

W drugim zadaniu wystarczy automat skończony o czterech stanach \(\displaystyle{ q_0,q_1,q_2,q_{\ge3}}\)
Automat jest w stanie \(\displaystyle{ q_i}\), jeśli wczytał \(\displaystyle{ i}\) jedynek.

Napisałem wyżej, co mają oznaczać poszczególne stany. Jeśli Ty na podstawie tego "łączysz te stany w kółeczko", to najpierw się cofnij do liceum na lekcje języka polskiego. Dopiero jak opanujesz czytanie tekstu ze zrozumieniem, to przeczytaj jeszcze raz i połącz stany tak, jak to wynika z ich znaczenia.-- 20 mar 2011, o 22:00 --No dobrze, zlituję się.

\(\displaystyle{ \begin{picture}(400,250)
\newsavebox{\looop}
\savebox{\looop}(0,0){
\qbezier(0,0)(-14,10)(0,10)
\qbezier(0,0)(14,10)(0,10)
\put(0,0){\vector(-1,-1){0}}
}


\multiput(20,30)(40,0){4}{\circle{16}}
\multiput(29,30)(40,0){3}{\vector(1,0){22}}
\multiput(37,32)(40,0){3}{$a$}
\multiput(20,38)(40,0){4}{\usebox{\looop}}
\multiput(17,50)(40,0){3}{$b$}
\put(132,50){$a,b$}

\put(16,28){$q_0$}
\put(56,28){$q_1$}
\put(96,28){$q_2$}
\put(133,28){$q_{\ge3}$}

\end{picture}}\)

[lunex]

Już tak zrobiłem, ale dzięki za zamieszczenie - nie wiedziałem, że TeX ma takie możliwości