LUC-spr7.pdf

Marek Karpiński (181172), Michał Kaczara(181132)

L.U.C. laboratorium – piątek 7:30 / mgr A. Sterna

SPRAWOZDANIE NR 7

TEMAT: HARDWARE'OWA IMPLEMENTACJA AUTOMATU SKOŃCZONEGO PEŁNIĄCEGO

FUNKCJĘ AUTOMATU NIEDETERMINISTYCZNEGO „NFA with

ξ -moves”

(AKCEPTUJĄCEGO DANY JĘZYK REGULARNY)

1. Automat akceptujący ciągi opisane wyrażeniem regularnym (1+0)*2*

Alfabet wejść: Z = {0, 1, 2}

Alfabet wewnętrzny: Q = {q0, q1}

Zbiór stanów końcowych: F = {q1}

Graf automatu:

Schemat ideowy(bramki AND, OR, przerzutniki typu RS):

Schemat układu do realizacji w technologii TTL(bramki NAND, NOR, NOT, przerzutniki

typu RS):

Słowa akceptowane i nieakceptowane przez automat:

Automat akceptuje słowa zgodne z wyrażeniem regularnym (0+1)*2*, czyli

wszystkie, które są skończonym ciągiem liczb 0 i 1, zaczynają się od liczb 0

lub 1 i są zakończone dowolną ilością 2, lub ciągi 2, np:

• 000....001, 0101....01, 10....111, 111....0...1011, itd.,

• 01......012, 000..1..22, 2......222, 101...........0012, itd.

Automat nie akceptuje słów, które są ciągiem liczb zawierającym

2 „w środku”(dowolna sekwencja 0 i/lub 1 podana na wejście po liczbie 2

spowoduje niezaakceptowanie słowa), np:

• 2.....0100, 101......201, 000..2..01..2, 111...2...10...22, itd.

2. Wnioski

Opracowanie automatu niedeterministycznego akceptującego słowa opisane

wyrażeniem regularnym (0+1)*2*, przygotowaliśmy w ramach siódmych zajęć

laboratoryjnych z logiki układów cyfrowych, na podstawie instrukcji do ćwiczenia.

Naszym zadaniem było odpowiednie przekształcenie schematu automatu

akceptującego słowa opisane wyrażeniem 0*1*2*. Opracowany automat posiada dwa stany

wewnętrzne(q0,q1), zrealizowane w układzie sekwencyjnym jako dwa przerzutniki typu RS.

Przycisk START umożliwia przejście automatu do stanu q0. Jeśli na wejście układu

podamy 0 lub 1, to pierwszy przerzutnik przyjmie stan 1 i będzie go utrzymywał aż do

momentu, kiedy na wejście układu podamy 2 lub nastąpi tzw. „puste przejście”(umożliwia je

wciśnięty cały czas przycisk E). Wtedy przerzutnik pierwszy zostanie zresetowany,

a przerzutnik drugi przyjmie stan 1, który będzie oznaczał akceptację słowa. Jeśli na wejście

układu podamy znów dowolną sekwencję 0 lub 1, przerzutnik drugi także zostanie

zresetowany, co będzie oznaczało nie akceptację słowa. Odczyt umożliwia przycisk READ,

a przycisk RESET powoduje zresetowanie obu przerzutników. Użycie kolejno przycisków

RESET i START umożliwia wprowadzenie na wejście automatu nowego słowa.