luc_nfa-Automat NFA.pdf

(51 KB) Pobierz
Anon 200xxx
Ściąganie to zuo – nie kopiuj...
Data: xx.xx.2014, xx:xx
(...tak, aby cię złapali:)
Ćwiczenie – Automat NFA
1. Wstęp
Automat niedeterministyczny to taki automat, który posiada co najmniej jeden stan
wewnętrzny, dla którego istnieje więcej niż jedno przejście dla danego sygnału wejściowego.
akceptującego wyrażenie regularne (0+1)*2*.
Naszym zadaniem było zbudowanie automatu z posunięciem pustym (NFA with ξ moves)
2. Graf automatu
Wyrażenie regularne (0+1)*2* można opisać grafem:
z
0
+z
1
start
z
2
ξ
q
0
q
1
Automat posiada jedno „puste” przejście. Stanem końcowym (akceptującym) jest q
1
.
3. Schemat układu
Bazując na schematach układów z instrukcji 204, zaprojektowaliśmy własny układ.
Wykorzystaliśmy wejścia SET i RESET przerzutników JK. Układ można opisać zależnościami:
S
1
= START
R
1
= RESET + Q
2
S
2
= ξ (z
2
+ READ) Q
1
R
2
= RESET + z
0
+ z
1
Na podstawie tych informacji można stworzyć schemat układu.
4. Podsumowanie
Zaprojektowany układ działał zgodnie z założeniami. Po wciśnięciu przycisku RESET, a
następnie START, wprowadzano ciąg za pomocą przycisków 0, 1, 2. Za pomocą przycisku READ
można sprawdzić, czy automat zaakceptował ciąg. Układ poprawnie akceptował słowa takie jak
0000112222, 00222, 0011110001, a także puste ciągi. Natomiast słowa typu 001221,
000222022, 001122001122 nie były akceptowane.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin