Wykonanie: Krakowian Konrad 140059 Rakowski Bartosz 140116

mgr inż. A. Sterna Poniedziałek, godz. 15.15 15.05.2006r.

Sprawozdanie nr 10

HARDWARE'OWA IMPLEMENTACJA AUTOMATU SKOŃCZONEGO PEŁNIĄCEGO FUNKCJĘ AUTOMATU NIEDETERMISTYCZNEGO „NFA with ξ-moves” (AKCEPTUJĄCEGO DANY JĘZYK REGULARNY)

1. Cel ćwiczenia

Celem ćwiczenia jest praktyczne zapoznanie się ze sposobem

Hardware'owej implementacji automatu skończonego pełniącego funkcję automatu niedetermistycznego z pustymi przejściami.

2. Program ćwiczenia:

• Badanie automatu NFA akceptującego słowa zadane wyrażeniem regularnym 2*(1+0)*:

1. Graf przejść:

0 1+2

start ξ

2. Schemat ideowy:

3. Uwagi i wnioski:

Zmontowany układ akceptuje słowa: 00..0, 0..01..1, 0..02..2, 0..01..12..2, 0..02..21..1, 11..1, 1..12..2, 22..2, 2..21..1, a nie akceptuje: 11..10..00, 22..20..00, 1..12..20..0, 2..21..10..0, 1..0..2, 2..0..1 Zaakceptowanie przez automat danego słowa sygnalizuje zapalanie się diody, po uprzednim włączeniu przycisku READ, który umożliwia odczyt. Przed wprowadzeniem kolejnej sekwencji należy zresetować układ przyciskiem RESET, aby wszystkie przerzutniki przeszły w stan „0” i ustawić początek słowa poprzez podanie impulsu przyciskiem START. Przycisk „ε” jest cały czas wciśnięty, tak aby możliwe było tzw. puste przejście.

2

q₀

q₁