» Sonlu avtomatlar və onların qurulması yolları. Sonlu avtomatların təsviri üsulları. Avtomat nəzəriyyəsinin elementləri

Sonlu avtomatlar və onların qurulması yolları. Sonlu avtomatların təsviri üsulları. Avtomat nəzəriyyəsinin elementləri

Baranov Viktor Pavloviç Diskret Riyaziyyat. Bölmə 6. Sonlu avtomatlar və formal dillər.

Mühazirə 31 Sintez tapşırığı. Elementar avtomatlar

Mühazirə 30

SİNTEZ PROBLEMİ. ELEMENTARY AVTOMATLAR

Mühazirə planı:

1. Sonlu avtomatın tərifi.

2. Sonlu avtomatın təyini üsulları.

  1. Avtomat sintezi problemi.
  2. Elementar maşınlar.
  3. Avtomat əsasının tamlığı problemi.
  4. Avtomat sintezi üçün kanonik üsul.
  1. Dövlət maşınının tərifi

SFE real cihazların vaxtında işləməsini nəzərə almır. SFE ilə müqayisədə sonlu avtomat diskret informasiya çeviricisinin daha dəqiq modelidir. Eyni zamanda, sonlu avtomat konsepsiyası, hər hansı bir model kimi, bir sıra sadələşdirici fərziyyələrlə əlaqələndirilir.

Birincisi, avtomatın giriş və çıxışının istənilən vaxt məhdud sayda müxtəlif vəziyyətlərdən yalnız birində ola biləcəyi güman edilir. Həqiqi çeviricinin davamlı giriş siqnalı varsa, onu sonlu avtomatdan istifadə edərək təsvir etmək üçün bu siqnalı kvantlaşdırmaq lazımdır. Avtomatın formal tərifində avtomatın giriş və çıxış hallarının sonlu çoxluğu müvafiq olaraq giriş və çıxış əlifbası, ayrı-ayrı vəziyyətlər isə bu əlifbaların hərfləri adlanır.

İkincisi, zamanın diskret olaraq dəyişdiyi güman edilir. Giriş və çıxış vəziyyətləri diskret zaman ardıcıllığına uyğundur Zaman anı onun indeksi ilə unikal şəkildə təyin olunduğundan, sadəlik üçün vaxtın 1, 2, ..., ... dəyərlərini aldığını fərz edəcəyik. Vaxt intervalı taktika adlanır.

Maşının işləməsi aşağıdakı kimi təqdim olunur.

Avtomatın girişi giriş əlifbasından siqnalları qəbul edir ki, bu da giriş əlifbasının çıxışında siqnalların görünməsinə səbəb olur. Çıxış ardıcıllığının giriş ardıcıllığından asılılığı avtomatın daxili strukturundan asılıdır. Qeyd edək ki, yaddaşı olmayan SFE-dən fərqli olaraq, avtomat yaddaşa malik bir cihazdır, yəni avtomatın çıxışı təkcə girişlə deyil, həm də tarixdən əvvəlki dövrlə müəyyən edilir. Tarix öncəsi çıxış siqnalının təkcə girişdən deyil, həm də qeyd etdiyimiz cari vəziyyətdən asılılığı ilə nəzərə alınır.

Gəlin avtomatın rəsmi tərifini verək.

Dövlət maşını beş obyektdən ibarət dəstdir

giriş əlifbası adlanan sonlu çoxluq; mümkün giriş dövlətlərindən biri;

çıxış əlifbası adlanan sonlu çoxluq; bu çoxluğun elementləri mümkün çıxış vəziyyətlərini müəyyən edir;

daxili vəziyyətlərin əlifbası adlanan sonlu çoxluq;

avtomat keçid funksiyası: ; bu funksiya hər bir “giriş vəziyyəti” cütlüyünə bir vəziyyət təyin edir;

maşın çıxışlarının funksiyası: ; bu funksiya hər bir giriş-dövlət cütünü çıxış dəyəri ilə əlaqələndirir.

Avtomatın işləmə qanunu: avtomat funksiyaya uyğun olaraq vəziyyətlərini dəyişir və funksiyaya uyğun olaraq çıxış siqnalları yaradır:

  1. Dövlət maşınının müəyyənləşdirilməsi yolları

1. Tənzimləmənin cədvəl üsulu. Funksiyalar üçün həm əhatə dairəsi, həm də qiymətlər sonlu çoxluğa aid olduğundan, onlar cədvəllərdən istifadə etməklə müəyyən edilir.

Misal 1. Avtomatı aşağıdakı kimi təyin edək: , .Funksiyanı keçid cədvəlindən, funksiyanı isə çıxış cədvəlindən istifadə edərək təyin edirik.

Cədvəl 1. Jump cədvəli Cədvəl 2. Çıxış cədvəli

dövlət

dövlət

Avtomatın girişindəki siqnalların ardıcıllığı məlumdursa, çıxış ardıcıllığı keçid və çıxış cədvəlləri ilə unikal şəkildə müəyyən edilir.

2. Qrafik tənzimləmə üsulu. Keçid-çıxış diaqramından istifadə olunur. Bu, avtomatın hər bir daxili vəziyyətinin təpəyə uyğun olduğu yönləndirilmiş multiqrafdır. Avtomatın vəziyyətdən vəziyyətə keçidləri oxlarla təsvir olunur, onların hər birində bu keçidə səbəb olan giriş simvolu və avtomat tərəfindən yaradılan çıxış simvolu yazılır.

Şəkil 1 Keçid-çıxışların diaqramı

Misal 2. Aşağıdakı kimi işləyəcək avtomat qurmaq tələb olunur: hər bir dövrədə terminlərin növbəti ikili rəqəmləri avtomatın girişində alınır, avtomat onların cəminin müvafiq ikilik rəqəmini yaradır. İkirəqəmli şərtlər üçün bizdə: , .

Əvvəlki rəqəmlərin əlavə edilməsi zamanı daşıma baş verərsə, avtomat 1, əks halda isə 0 vəziyyətində olur. Keçid-çıxış diaqramı Şəkildə göstərilmişdir. 2.

  1. Avtomat sintezi problemi

SFE sintezi probleminə bənzətməklə, avtomatlar üçün sintez problemi yarada bilər. Əsas avtomatların limitsiz dəsti var. Əvvəlcədən müəyyən edilmiş funksiyaya malik bir avtomat yığmaq tələb olunur. Eyni zamanda, sintez vəzifəsi müəyyən problemlərlə üzləşir.

Fərz edək ki, avtomatın çıxışını avtomatın girişinə qoşmaq lazımdır. Bu şərtlə mümkündür, çünki əks halda ikinci avtomat birincidən gələn siqnalları başa düşməyəcək. Bu, bəzi əlaqələrin mümkün olmadığı çaşqın vəziyyətə gətirib çıxarır.

Bu maneəni aradan qaldırmaq üçün bütün əlifbaların (giriş, çıxış və daxili vəziyyətlər) ikili sözlərlə kodlandığı struktur avtomatı anlayışı təqdim olunur.

Sonlu elementlər toplusu olsun və uzunluqlu ikili sözlər toplusu olsun, burada. İxtiyari injektif xəritələşdirmə ikili sözlərlə çoxluğun kodlaşdırılması adlanacaq.

İxtiyari avtomat üçün əlifbaları kodlayaq:

Avtomatın müvafiq olaraq zaman anında kodlanmış girişini, çıxışını və vəziyyətini işarə edək. Sonra əməliyyat qanunu formada təqdim olunacaq

Kodlaşdırmadan sonra əldə edilən avtomata struktur avtomat deyilir. Biz güman edirik ki, struktur avtomatının ikili girişləri, ikili çıxışları var və avtomatın daxili vəziyyəti ikili uzunluqlu sözlə verilir. Əncirdə. Şəkil 3-də mücərrəd avtomat və onun müvafiq struktur avtomatı göstərilir.

Struktur avtomata keçid sintez üçün iki mühüm üstünlük verir.

1. Giriş və çıxışların uyğunluğu, çünki binar informasiya onlar vasitəsilə ötürülür. verməyəcəyik ümumi tərif struktur avtomatlardan olan sxemlər SFE-yə bənzəyir.

2. Əlaqələri (2) “koordinatlarda” yazaq:

(3)-dən belə nəticə çıxır ki, struktur avtomatının işləmə qanunu Boolean funksiyalar sistemi ilə verilir.

  1. Elementar avtomatlar

Biz ən sadə struktur avtomatları ayırırıq və onlara ad veririk.

Əvvəlcə qeyd edək ki, yalnız bir vəziyyətə malik olan funksional element yaddaşsız avtomat hesab edilə bilər.

Gəlin iki vəziyyətlə avtomatlara keçək. Avtomatın daxili vəziyyətlə üst-üstə düşən bir ikili giriş və bir ikili çıxışı olsun: :

Şəkildə göstərilən avtomatı təyin etmək üçün. 4, yalnız keçid cədvəlini təyin etmək kifayətdir:

Cədvəl 3

dövlət

Ulduz işarələri yerinə 0 və 1 qoymaq lazımdır. Bunu 16 yolla etmək olar, lakin onların hamısı məqbul deyil. Tutaq ki, məsələn, 3-cü cədvəlin birinci sütununda hər iki element sıfırdır. Belə avtomat 0 vəziyyətində olduqdan sonra artıq ondan çıxmayacaq, yəni funksional element kimi işləyəcək. Oxşar vəziyyətlərin təhlili göstərir ki, yaddaşsız avtomata çevrilməyən avtomatı əldə etmək üçün 3-cü cədvəlin hər sütununda həm sıfırın, həm də birinin olmasını tələb etmək lazımdır. Cəmi dörd belə masa var.

Cədvəl 4 Cədvəl 5

dövlət

dövlət

Cədvəl 6 Cədvəl 7

dövlət

dövlət

Bizdə yalnız iki ən sadə avtomat var, çünki daxili vəziyyətlərin çevrilməsi ilə 4-dən 7, 5-dən isə 6 alınır.

Cədvəl 4-də verilmiş avtomat gecikmə və ya tetikleyici adlanır:

yəni bu avtomat siqnalı bir dövrə gecikdirir.

Cədvəl 5-də göstərilən avtomat sayma girişi və ya -triggeri olan trigger adlanır. Giriş 1 olarsa avtomatın vəziyyəti əksinə dəyişir və giriş 0 olarsa dəyişməz qalır:

Qoy -trigger zamanın ilkin anında 0 vəziyyətində olsun.Əgər zamanın bir nöqtəsində -trigger 0 vəziyyətindədirsə, bu o deməkdir ki, cüt Ədəd vahidlər. 1-ci vəziyyətdədirsə, onda təkdir. Beləliklə, -trigger girişdəki vahidlərin sayını hesablayır, lakin yalnız iki vəziyyətə malik olduğundan, ikiyə qədər sayır.

Tətiklərin fiziki həyata keçirilməsində iki çıxışdan istifadə olunur: birbaşa və tərs (şək. 5). Əgər onları dəyişdirsək, onda -triggerdən Cədvəl 7-də göstərilən avtomatı, -triggerdən isə Cədvəl 6-da göstərilən avtomatı alırıq.

  1. Avtomat əsasının tamlığı problemi

Struktur avtomatlar toplusu tam (və ya avtomat bazası) adlanır, əgər onlardan hər hansı bir struktur avtomat qurmaq olar.

Riyaziyyatçıların avtomatlar üçün Post teoreminin analoqunu əldə etmək cəhdləri uğursuz oldu. 1964-cü ildə M.İ. Sistemin tamlığını təyin etmək üçün alqoritmin mövcud olmadığını qısaca sübut etdi. Bu zaman tamlıq teoreminin sistem haqqında əlavə fərziyyələrlə variantları maraq doğurur. Onlardan ən populyarını nəzərdən keçirək.

Teorem. FE-lərin tam dəstini və -trigger (və ya -trigger) olan avtomatlar sistemi tamamlandı.

Sübut. (2) münasibətləri ilə verilmiş ixtiyari avtomatı nəzərdən keçirək və onun kanonik struktur adlanan göstərilən avtomatların sxemini təsvir edin (şək. 6).

Sxem iki hissədən ibarətdir.

Sol yarısı yaddaş hissəsi adlanır. O, vəziyyətlər dəsti avtomatın vəziyyətini təşkil edən tetikleyicilərdən ibarətdir: əgər zaman anında

onda bu o deməkdir ki, avtomat vəziyyətdədir.

Sağ yarım birləşmə hissəsi adlanır və SFE-ni təmsil edir. Bu dövrənin girişləri:

  1. avtomatın ikili söz daxiletmə siqnalı;
  2. ikili söz avtomatın cari daxili vəziyyəti.
  1. düsturlara (3) uyğun olaraq həyata keçirilən avtomatın ikili söz çıxış siqnalı;
  2. saxlama hissəsində tətiklərin girişlərinə daxil olan və avtomatın yaddaşını idarə edən ikili söz.

Göstərək ki, yaddaşa nəzarət siqnalları avtomatın çıxışı ilə eyni dəyişənlərin Boolean funksiyalarıdır, bu da onların tam FE sistemi ilə həyata keçirilə biləcəyini bildirir.

Zamanın hər anında yaddaşa nəzarət siqnalları avtomatı vəziyyətdən vəziyyətə keçirməlidir. Bunu etmək üçün hər bir tetikleyicinin vəziyyətini dəyişdirməlisiniz

Kanonik sxemdə istifadə olunan -triggers və ya -triggers aşağıdakı xüsusiyyətlərə malikdir: hər hansı bir vəziyyət cütü üçün avtomatı vəziyyətdən vəziyyətə köçürən giriş siqnalı var. Bu siqnalı ilə işarə edək. -trigger üçün, çünki -triggerin qoyulduğu vəziyyət giriş siqnalına bərabərdir. -trigger üçün: nə zaman, girişə 0 tətbiq edilməlidir ki, vəziyyət dəyişməsin; 1-də, beləliklə, tətiyi "çevirir".

Beləliklə, ya da vektor şəklində

Avtomatın işləmə qanunundan (2) ifadə edək. Sonra

Teorem sübut edilmişdir.

  1. Avtomat sintezi üçün kanonik üsul

Bu üsulu konkret bir nümunə üzərində nəzərdən keçirək.

Misal. Konveyerdə iki növ hissələrin hərəkət etdiyi avtomatik bir maşın quraşdırılmışdır, vəzifəsi hissələri maşından keçdikdən sonra qruplar təşkil edəcək şəkildə çeşidləməkdir. Maşın uyğun olmayan hissəni konveyerdən itələyir. Belə bir avtomatın dövrəsini -trigger və "AND", "OR", "NOT" elementlərindən istifadə etməklə qurmaq tələb olunur.

Avtomat sintezi aşağıdakı mərhələlərə bölünür.

1. Abstrakt avtomatın qurulması.

Giriş əlifbası. Çıxış əlifbası , burada C hissənin toqquşması, P onun atlamasıdır. Avtomatın daxili halları onun artıq qrupun hansı hissəsini təşkil etdiyi haqqında yaddaşını əks etdirir: . Qrup formalaşdıqca, avtomat uyğun olmayan hissə gəldikdə vəziyyəti dəyişmədən bu vəziyyətlər arasında dövri olaraq hərəkət edir. Keçid-çıxış diaqramı Şəkildə göstərilmişdir. 7.

2. Əlifbaların kodlaşdırılması.

Biri seçimlər kodlaşdırma aşağıdakı cədvəllərdə verilmişdir.

Giriş Çıxış Vəziyyəti

3. Avtomatın kanonik strukturunun qurulması.

İnkişaf etdirilən avtomatın kanonik quruluşu Şek. səkkiz.

Gəlin əvvəlcə cədvəl şəklində (Cədvəl 8) SFE çıxışlarının dəyişənlərdən asılılığını tapaq, ona uyğun olaraq düsturları daha da quracağıq.

Cədvəl 8

Bu funksiyalar müəyyən edilmədiyi üçün qismən müəyyən edilmiş adlanır. Bu funksiyaları düsturlarla təmsil etmək üçün onlar düsturların daha sadə formasını əldə edəcək şəkildə genişləndirilir.

4. Avtomatın çıxış funksiyalarının və yaddaşa nəzarət funksiyalarının düsturlarla təmsil olunması.

Boolean funksiyalarını minimuma endirmə üsullarından istifadə edərək, mümkünsə, əsasdakı düsturlarla funksiyaların iqtisadi təsvirini qururuq:

5. SFE-nin həyata keçirilməsi və avtomatın yekun sxemi (şək. 9).

SONLU AVTOMATIN TƏYİRİ VƏ TƏYİQ EDİLMƏ METODLARI. SİNTEZ PROBLEMİ. ELEMENTARY AVTOMATLAR

n-in əsas tərifləri Sonlu avtomat M =(А, B, S, y) sistemidir, burada n n n А = (а 1, . . . . , am) sonlu giriş əlifbasıdır, B =(b 1, . . . . , bk ) - sonlu çıxış əlifbası, S =(s 1, . . . , sn) - sonlu vəziyyət əlifbası, : A S S - keçid funksiyası, y: A S B - çıxış funksiyası. n Əgər M avtomatında ilkin vəziyyət adlanan bir vəziyyət seçilibsə (adətən bunun s 1 olduğu nəzərə alınacaq), onda yaranan avtomat ilkin adlanır və (M, s 1) ilə işarələnir. n Avtomat təyin etməyin iki yolu var: Avtomat cədvəli, keçid diaqramı

Avtomat cədvəli n 1) 2) 3) 4) Nümunə: "0" və "1" simvolları daxil edilərsə, avtomatı "001" sözünü oxumaq üçün təyin edin. Giriş əlifbası A=(0, 1) Çıxış əlifbası A=(Y, N) Dövlət əlifbası S=(s 0 "" , s 1 " 0" , s 2 " 00" s 3 "001" ) İki şəkildə avtomatik cədvəl . 1) Sıralar avtomatın vəziyyətləridir. Sütunlar giriş simvollarıdır. Sətir və sütunların kəsişməsində funksiyalar göstərilir, y. 2) S, A, y sütunlarla verilir. 25-ci məşq CAKADU SA 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" sözünü axtarmaq üçün avtomat qurun. " S 1 , N S 0, N S In y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 N S 1 S 2 S 3

Keçid diaqramı n Keçid diaqramı adlanan yönümlü multiqraf, vəziyyətlərə uyğun gələn multiqraf, keçid və ya qrafikdir. Əgər (Si, aj)=Sk, y(Si, aj)=bl olarsa, onda Si təpəsindən Sk təpəsinə qədər (aj, bl) n yazılmış hər si təpəsində düzgünlük şərtləri var. : 0 1 S 0 "" S 1, N S 0, N S 1 "0" n Təpələr, y S 2, N S 0, N S 2 "00" S 2, N S 3, Y S 3 "001" S 1, N S 0, N 1, N yerinə yetirildi 1) hər hansı daxil olan aj hərfi üçün si-dən çıxan qövs var, onun üzərinə aj yazılır (tamlıq şərti); 2) hər hansı aj hərfi yalnız si-dən çıxan bir kənarda baş verir (ardıcıllıq və ya determinizm şərti) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3

Avtomat və giriş sözləri n Verilmiş M avtomatı üçün onun funksiyaları M və y-dir. M yalnız bütün daxil olan hərflərin A çoxluğunda deyil, həm də bütün daxil olan sözlərin A* çoxluğunda müəyyən edilə bilər. n İstənilən giriş sözü üçün = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . , ajk-1), ajk). y (si, aj 1 aj 2. . . ajk) = y((… (si, aj 1), aj 2), . . , ajk-1), ajk).

Nümunə: Avtomat və daxiletmə sözləri Nümunə: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2) , 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) \u003d N, y S 2, N S 3, Y S 3 "001" S 1, N S 0, N

Avtomatik xəritələşdirmə n M-də ilkin vəziyyəti S 0 və hər giriş sözü üçün = a 1 a 2 təyin edək. . ak çıxış əlifbasında söz təyin edirik: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1... ak). (3 a) n Giriş sözlərini çıxış sözləri ilə əlaqələndirən bu uyğunluq avtomat xəritələşdirmə adlanır n Əgər operatorun sözə tətbiqinin nəticəsi çıxış sözüdürsə, bu, müvafiq olaraq M() = ilə işarələnəcəkdir.

Nümunə: Avtomatik Xəritəçəkmə Çıxış əlifbasındakı sözə daxil olan = 0101 sözünü təyin edək: = y (S 0, 0) y(S 0, 01)y(S 0, 0101). y (S 0, 0)= N, y 0 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 "00" S 2, N S 3, Y 1 S 3 "001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S) 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0)) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN

Avtomat ekran xüsusiyyətləri 1) sözlər və = M() eyni uzunluğa malikdir: | | = | | (uzunluğun saxlanma xüsusiyyəti); 2) əgər = 1 2 və M(1 2) = 1 2, burada | 1| = | 1|, onda M(1) = 1; başqa sözlə, uzunluğu i olan seqmentin təsviri eyni uzunluqdakı təsvirin seqmentinə bərabərdir.

Avtomatların növləri n Əvvəllər nəzərdən keçirilən sonlu avtomatın (S-sonlu) ümumi modeli Mealy avtomatı adlanır. n Giriş əlifbası bir hərfdən ibarətdirsə, avtomat avtonom adlanır: A=(a). Avtonom avtomatın bütün giriş sözləri aa formasına malikdir. . . a. n Çıxış funksiyası yalnız vəziyyətlərdən asılıdırsa, yəni hər hansı s, ai, aj y(s, ai) = y(s, aj) üçün sonlu avtomata Mur avtomatı deyilir. Mur avtomatının çıxış funksiyası təbii olaraq bir arqumentdir; adətən hərflə işarələnir və işarə funksiyası adlanır. Moore avtomatının qrafikində çıxış kənarlarda deyil, yuxarıda yazılır.

Mur avtomatı n Teoremi: İstənilən Mealy avtomatı üçün ekvivalent Mur avtomatı mövcuddur. n Avtomatların imkanlarını öyrənərkən Mur avtomatlarından istifadə etmək kifayətdir. Bu rahatdır, çünki Mur avtomatına çıxışı olmayan, vəziyyətləri müxtəlif yollarla işarələnmiş avtomat kimi baxmaq olar.

Avtonom avtomata SA a S 1 S 3, 0 S 2 S 4, 0 S 3 S 4, 0 S 4 S 7, 0 S 5 S 4, 2 S 6 S 5, 0 S 7 S 6, 1 nümunəsi S 8 S 9, 0 S 9, 1 S S S S S A=(a), B=(0, 1, 2), S=(S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S9)

Ayrılmayan Dövlətlər n M və T eyni giriş və çıxış əlifbalarına malik iki avtomat olsun. Hər hansı bir giriş sözü üçün M(s,) = T(r,) olarsa, avtomatın M vəziyyətinin s və T avtomatının r vəziyyətinin fərqləndirilmədiyi deyilir. n M və T avtomatları, M avtomatının hər hansı s vəziyyəti üçün ondan fərqlənməyən T avtomatının r vəziyyəti varsa və əksinə, T-dən hər hansı r üçün M-dən fərqlənməyən s vəziyyəti varsa, M və T avtomatları fərqləndirilməz adlanır. n Ayrılmayan hallar ekvivalent adlanır

Minimal avtomat n M avtomatından ekvivalent avtomata keçid M avtomatının ekvivalent çevrilməsi adlanır. n Verilmiş avtomata ekvivalent olan və xassələri verilmiş avtomatların tapılması üçün müxtəlif problemlər qoya bilər. Belə problemlər arasında ən çox öyrəniləni avtomatın vəziyyətlərinin sayını minimuma endirmək problemidir: M-ə ekvivalent olan avtomatlar arasında ən az vəziyyətə malik avtomatı - minimal avtomatı tapın.

Avtomatların "işinin" aspektləri Avtomatların "işinin" iki əsas aspektini ayırd etmək olar: 1) avtomatlar daxil olan sözləri tanıyır, yəni giriş sözünün verilmiş çoxluğa aid olub-olmaması sualına cavab verir (bunlar tanıyan avtomatlardır) ; 2) avtomatlar giriş sözlərini çıxış sözlərinə çevirir, yəni avtomat xəritələşdirməni həyata keçirirlər (transformator avtomatları).

Metariyaziyyat çərçivəsində TA n Metariyaziyyat çərçivəsində alqoritmlər və formal sistemlər nəzəriyyəsinin mövzusu - onların üzərində hansı obyektlər və hərəkətlər dəqiq müəyyən edilməlidir, elementar hərəkətlərin birləşmələri hansı xüsusiyyətlərə və imkanlara malikdir, nə ola bilər və nə ola bilməz. onların köməyi ilə həyata keçirilir. n Alqoritmlər nəzəriyyəsinin əsas tətbiqi müəyyən riyazi məsələlərin alqoritmik (yəni, dəqiq və birmənalı) həllinin qeyri-mümkünlüyünün sübutudur.

Alqoritm n Alqoritm ilkin verilənlərin tələb olunan nəticəyə çevrilməsi prosesini unikal şəkildə təyin edən reseptdir.

Alqoritmlərin əsas növləri n Alqoritmlər nəzəriyyəsi alqoritmlərin müxtəlif (keyfiyyət və kəmiyyət) xassələrini öyrənən metanəzəriyyədir. n Keyfiyyət xassələrinin öyrənilməsi üçün 3 əsas alqoritm növü müəyyən edilmişdir: 1) Rekursiv funksiyalar 2) Tyurinq maşını 3) Canonical Post sistemləri və normal Markov alqoritmləri.

Ən sadə rekursiv funksiyalar n S 1(x) = x+1 - funksiya bir x dəyişənindən asılıdır və x+1-ə bərabərdir. n On(x 1…xn) =0 - n dəyişəndən asılı olan funksiya və həmişə 0-a bərabərdir. n Imn(x 1…xn) = xm - n dəyişəndən asılı funksiya və həmişə xm dəyişəninin qiymətinə bərabərdir.

Primitiv rekursiya n f(x 1…xn+1) funksiyası g(x 1…xn) və h(x 1…xn+2) funksiyalarından primitiv rekursiya alqoritmi ilə alınır, əgər f(x 1, …xn, 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), burada z=f(x 1, …xn, y) (2) f funksiyası ibtidai rekursiv adlanır, əgər onu ən sadə S 1, On, Imn funksiyalarından sonlu sayda superpozisiya və primitiv rekursiya əməliyyatları ilə əldə etmək olarsa.

Nümunə n Funksiyanın primitiv rekursiv olduğunu sübut etmək üçün: 1) (1) və (2) tənliklərinə əsasən g() və h() funksiyalarını açıq şəkildə təyin edin. 2) g() və h() funksiyalarının ən sadə S 1, On, Imn funksiyaları və ya əvvəllər sübut edilmiş primitiv rekursiv funksiyalar olduğunu göstərin. Tapşırıq 26: f(x, y) = x+y funksiyasının primitiv rekursiv olduğunu sübut edin Kilsənin tezisi: Alqoritmik olaraq hesablana bilən ədədi funksiyalar sinfi bütün rekursiv funksiyaların sinfi ilə üst-üstə düşür.

Tyurinq maşını n Tyurinq maşınına daxildir: n 1) Xarici yaddaş - n hüceyrədən ibarət lent. Hər bir i-ci hüceyrə ai vəziyyətindədir. Dövlətlərin əlifbası təyin olundu. Bant hər iki istiqamətdə sonsuz ola bilər. Boş dövlətlər buraxılıb. n 2) Maşının daxili yaddaşı - cihaz hazırda qi vəziyyətindədir. Daxili dövlətin əlifbası verilir. İlkin vəziyyət q 1, son q 0 və ya qz. n 3) Göstərici - cari xananı göstərir və lent boyunca hərəkət edir. n 4) İdarəetmə qurğusu – göstəricinin göstərdiyi xananın simvolunu oxuyur. Proqrama uyğun olaraq xananın vəziyyətini dəyişir və göstəricini hərəkət etdirir.

Vəziyyət və proqram MT n Turinq maşınının vəziyyəti monitorinq edilən xananın qarşısına daxili vəziyyətin simvolunu daxil etməklə əmələ gələn n n n n a 1…ak-1 qi ak…ar sözü adlanır. Turinq maşını proqramı qi aj qi' aj' D maşını tərəfindən yerinə yetirilə bilən əmrlər toplusudur, burada qi maşının daxili vəziyyətidir aj nəzarət edilən xananın vəziyyəti qi' maşının yeni vəziyyətidir aj' monitorinq edilən xanaya yazılan yeni simvoldur D = ( L, R, E) - göstəricinin müvafiq olaraq bir xana tərəfindən sola, sağa və yerdəyişmənin olmamasını simvolizə edən simvollar.

Nümunə MT İş 27: Turinq maşınının son vəziyyətini tapın İlkin əlifba: A = (0, 1) Daxili dövlət əlifbası: Q = (q 0, q 1, q 2) Proqram: ( 1) q 10 q 20 R, 2)q 20 q 01 E, 3) q 11 R, 4) q 21 R ) Başlanğıc söz: q 111

Misal MT Control 28 Turing maşınının son vəziyyətini tapın İlkin əlifba: A \u003d (0, 1, ) Daxili vəziyyətin əlifbası: Q \u003d (q 0, q 1, q 2, q 3) Proqram: ( 1 ) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L) A) Başlanğıc söz: q 111 1 B) Başlanğıc söz: q 11 111

Tyurinqin tezisi Turinqin tezisi: hər bir A alqoritmi üçün eyni ilkin verilənlər verilməklə, A alqoritmi ilə eyni nəticələri verən Türinq maşını qurula bilər. n Əgər 1 q 1 2 1 qz 2 olarsa, onda biz deyərik ki, maşını T. 1 2 sözünü 1 2 sözünə emal edir və onu T(1 2) = 1 2 işarələyir. n T() işarəsi T maşınının ilkin qiymətlərlə təyin edilməsidir.

Normal Markov Alqoritmləri n Normal Markov Alqoritmləri (NAM) sonlu uzunluqlu sözləri əvəzetmədən istifadə edərək bir-birinə çevirir. n Tapşırıq NAM Əvəzetmə Əlifbası u v Yekun əvəzetmə u v n Nəzarət 29 Normal Markov alqoritmi müəyyən edilmişdir: Əlifba rus dilinin əlifbasıdır. Əvəzetmə sxemi (I U, L U, S M, V B, R T, T R, O X, N A) n İlkin söz SLON. n Son sözü tapın.

Alqoritmlərin mürəkkəbliyinin qiymətləndirilməsi n Tutaq ki, f(n) və g(n) funksiyaları iki alqoritmin icrasını ölçür, onlar adətən zaman mürəkkəbliyi funksiyaları adlanır. Deyəcəyik ki, f(n) funksiyasının artım sırası g(n) funksiyasından böyük deyil, əgər müsbət sabit C var ki, | f(n) |

Alqoritmlərin səmərəliliyi A B C D E n 3 n 2 2 n 2+4 n n 3 2 n 1 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1024 s 100 ms 1024 s 100 ms s 201.5s. günlər 10176 əsrlər 1000 ms 0,83 saat 1 ms

Alqoritmlər nəzəriyyəsi n Alqoritmlər nəzəriyyəsi - problemləri mürəkkəbliyinə görə təsnif edir. Bu halda, yalnız tanınma tapşırıqları təsnif edilir. n Tanınma tapşırığı suala cavab verən tapşırıqdır: daxil edilmiş məlumatların bəzi xassələri varmı. Bizim vəziyyətimizdə: giriş məlumatları bir qrafikdir, bir xüsusiyyətdir - qrafik Hamiltoniandır?

P və NP sinifləri n Mürəkkəblik sinfi P: məsələni polinom zamanda həll edən A alqoritmi var. n Mürəkkəblik sinfi NP - təklif olunan həlli polinom zamanda yoxlayan A alqoritmi var. n Hamilton dövrü problemi verilmiş G qrafikinin NP sinfinə aid Hamilton dövrünə malik olub-olmadığını öyrənməkdir.

NP problemlərinin nümunələri n Məntiqi təminat problemi: verilmiş Boolean düsturundan onu 1-ə çevirən bir sıra dəyişənlərin olub-olmadığını öyrənmək üçün. subqraflar) verilmiş ölçüdə. n Qrafikdə Hamilton dövrünün mövcudluğu problemi. n Xətti bərabərsizliklər sisteminin tam həllinin mövcudluğu.

n-i sadalamaqla NP məsələlərini həll etmək imkanı İlkin olaraq həlli məlum deyil. Buna görə də, Hamilton dövrünün tapılması alqoritmində baş verən n-nin bütün mümkün kombinasiyalarını sadalamaqla NP-sinifinə aid hər hansı bir problemin eksponensial zamanda həll edilməsi vacibdir.

Р və NP arasında əlaqə n P-dən istənilən tapşırıq NP-yə aiddir. n Beləliklə, NP sinfinə P sinfi daxildir. In vaxt verilmişdir, P və NP siniflərinin üst-üstə düşüb-düşmədiyi məlum deyil, lakin əksər ekspertlər onların uyğun gəlmədiyinə inanırlar.

P və NP nisbəti n P = NP olduğu ortaya çıxarsa 1) NP vəzifələri ağlabatan müddətdə həll ediləcəkdir. 2) Eksponensial mürəkkəblik problemlərindən qəsdən istifadə edən bir sıra problemlər var (yəni, problemin həll edilə bilməyəcəyini fərz etməklə). Məsələn, kriptoqrafiyada açıq açarın şifrələnməsi bölməsi var ki, onun şifrəsini açmaq demək olar ki, mümkün deyil. Birdən P = NP olarsa, onda bir çox sirlər belə olmaqdan çıxacaq.

NP-Tam Problemlər n P ≠ NP olduğuna inanmaq üçün ən əsaslı səbəb NP-tam problemlərin mövcudluğudur. n Qeyri-rəsmi!!!, Q problemi hər hansı bir giriş üçün çoxhədli vaxtda həll oluna bilərsə, Q probleminin həllinin hər hansı digər giriş üçün məlum olduğunu fərz etməklə Q probleminə qədər azalır. Məsələn, xətti tənliyin həlli məsələsi kvadrat tənliyin həlli məsələsinə endirilir.

NP-tam problemlər n NP-tam problem NP sinfindən olan problemdir və NP sinfindən hər hansı digər problemə endirilə bilər. n NP-tam problemlər NP sinfində "ən çətin" məsələlərin alt çoxluğunu təşkil edir. Əgər hər hansı NP-tam məsələ üçün çoxhədli həll alqoritmi tapılarsa, o zaman NP sinfindən olan hər hansı digər məsələ çoxhədli zamanda həll edilə bilər. n Bütün sadalanan NP-problemləri NP-tamdır. Hamilton dövrü problemi də daxil olmaqla.

Avtomat nəzəriyyəsinin elementləri

Plan:

1. Avtomat anlayışı, avtomatın iş prinsipi

2. Sonlu avtomatların təyin edilməsi üsulları

3. Ümumi Tapşırıqlar avtomat nəzəriyyəsi

Nəzəri məlumat

İnsan hər zaman öz müdaxiləsi olmadan bəzi mexaniki cihazları ona işlətməklə işini asanlaşdırmağa çalışmışdır. Əvvəlcə nağıl idilər, sonra adi şeylərə çevrilməyə başladılar. Avtomobil, televizor, paltaryuyan maşınlar, bütün sənayelər insan müdaxiləsi olmadan işləyir. Üstəlik, əksər hallarda insan müdaxiləsi tələb olunmur və bəzi hallarda bu cür müdaxilə mənfi hadisələrə səbəb ola bilər. Müəyyən bir hərəkət növünü yerinə yetirən bir cihaz kimi "maşın" anlayışı insanlar tərəfindən çoxdan bu şəkildə şərh edilmişdir.

Avtomat anlayışı, avtomatın iş prinsipi

anlayış maşın iki aspektdə nəzərdən keçirilir:

1. Maşın - cihaz insanın bilavasitə iştirakı olmadan bəzi funksiyaları yerinə yetirən. Avtomat əsl cihazdır, onun niyə və necə işlədiyi başa düşüləndir, heç olmasa onu dizayn edən və istehsal edən insanlar üçün. Maşın, traktor, təyyarə, işıqfor, televizor, telefon - bütün bunlar avtomatik maşınlardır. Bu baxımdan kompüter dedikdə insanın tərtib etdiyi proqram üzrə işləyən avtomat başa düşülməlidir.

2. Avtomatik - riyazi anlayış real texniki cihazların riyazi modelini ifadə edən. Avtomat mücərrəd bir cihazdır, niyə və necə işlədiyi və ümumiyyətlə, nə üçün işləyə biləcəyi aydın deyil. Bu aspektdə avtomat nəzəri cəhətdən müəyyən hərəkətləri yerinə yetirməyə qadir olan “qara qutu”dur. Riyaziyyat nöqteyi-nəzərindən müəyyən hərəkətləri nəyin, necə və nə üçün yaratdığının qətiyyən əhəmiyyəti yoxdur.

İstənilən avtomat müəyyən sayda girişə, müəyyən sayda çıxışa və müəyyən sayda daxili vəziyyətə malik olmalıdır.

Cəbr avtomatları nəzəriyyəsi nəzəri kibernetikanın diskret avtomatları mücərrəd cəbr nöqteyi-nəzərindən öyrənən bölməsidir.



Avtomatların ümumi nəzəriyyəsi müxtəlif alt bölmələri ehtiva edir. Tədqiqatın predmetindən asılı olaraq avtomatların abstrakt nəzəriyyəsinə və avtomatların struktur nəzəriyyəsinə bölünür.

Abstrakt avtomat nəzəriyyəsi giriş siqnallarının təsirinə məruz qalan avtomatın etdiyi keçidləri, həmçinin bu keçidlər nəticəsində çıxış siqnallarını öyrənir.

Tədqiqat mövzusu struktur avtomat nəzəriyyəsi avtomatın strukturu, eləcə də giriş və çıxış siqnallarının strukturu, məsələn, giriş və çıxış siqnallarının kodlaşdırılması üsulları və s.

Dövlət maşınlarının tərifi

Maşın- giriş siqnallarının sonlu ardıcıllığını emal edən və onları sonlu çıxış siqnalları (reaksiyaları) ardıcıllığına çevirən diskret zamanda işləyən cihazın mücərrəd modeli.

Sonlu avtomatın işləməsi prosesində onun sonlu sayda daxili vəziyyətləri ardıcıl olaraq dəyişir və avtomatın müəyyən zaman nöqtəsində vəziyyəti giriş və çıxış siqnalları ilə unikal şəkildə müəyyən edilir. Belə avtomatlar bütün müasir kompüter texnologiyalarının və avtomatik idarəetmə və idarəetmənin bütün növ diskret sistemlərinin əsasını təşkil edir.

Avtomat anlayışı o qədər mücərrəddir ki, bir insanın heç bir avtomat olmadan nə vaxt işlədiyini söyləmək çətindir. Avtomatın tərifinə hər hansı bir cihaz, o cümlədən olanlar daxildir ibtidai insanlar ovladılar və ya daş atdılar, evlərini düşməndən qorudular.

Alqoritm- başa düşülən və verilmiş ilkin məlumat dəstini istənilən nəticəyə çevirən əməliyyatların məzmununu və ardıcıllığını birmənalı şəkildə müəyyən edən ifaçıya dəqiq rəsmi göstəriş.

İnsan tərəfindən yaradılan ilk proqram qurğusunun saat olduğuna inanılır. Ötürücüləri idarə edən yayın köməyi ilə mexanizmlərə baxın və cam mexanizmləri, dişlilər və qolları, bir sıra xüsusi hərəkətləri həyata keçirin. Belə bir saat mexanizminin nümunəsi Moskvanın Mərkəzi Kukla Teatrında on iki saat sürən məşhur saatdır. nağıl qəhrəmanları siferblatda yerləşir.

Bir neçə maraqlı məqamı qeyd edirik tarixi faktlar mexaniki qurğular kimi avtomatlarla əlaqələndirilir.

1. Alman filosofu və kimyaçısı Böyük Albert 1216-1246-cı illərdə “dəmir” qulluqçu - evdə qapıçı vəzifələrini yerinə yetirən avtomat yaratmışdır.

2. Astronom İohann Müller (Regiamontanus) (1436-1476) Müqəddəs Roma İmperatoru II Maksimiliyanın Nürnberqə girişini başın əyilməsi və qanadlarının hərəkəti ilə qarşılayan mexaniki qartal yaratmışdır.

3. Mexanik Jak de Vakanson (1709-1782) - dünyada ilk avtomatik dəzgahın müəllifi. O, mexaniki ördək obrazını, canlı həmkarının dəqiq surətini yaratdı - üzdü, lələkləri təmizlədi, ovucunun içindən taxılları uddu. Onun on bir musiqi əsəri ifa edən mexaniki fleyta ifaçısı o uzaq illərdə yaşayan insanları heyrətə gətirirdi.

4. 19-cu əsrin rus ixtiraçısı. A. M. Gamuletsky, onun hazırladığı bir çox avtomatın olduğu bütöv bir mexaniki kabinet yaratdı. Burada, başqa şeylərlə yanaşı, müasirlərin təxəyyülünü heyran edən sehrbazın danışan başı və arfa çalan kapidin var idi.

5. İlk primitiv toplama maşını 1641-ci ildə Blez Paskal tərəfindən hazırlanmışdır. Açılış üçün təkan atasının əzabı oldu - vergi, böyük hesablamalarla gecə-gündüz işləyən müfəttiş. On səkkiz yaşlı oğul toplama maşını ixtira etməklə atasını mürəkkəb hesablamalardan xilas etdi və dünyaya ədədləri toplayan və çıxaran ilk kalkulyator verdi.

6. İlk şahmat maşını 1890-cı ildə ispan mühəndis Torres Kevedo tərəfindən yaradılmışdır. Belə bir avtomat yalnız son oyun oynaya bilər (kral və krala qarşı qala).

7. İlk kompüter avtomatik nəzarət 1822-ci ildə Charles Babbage tərəfindən yaradılmışdır əlavə maşın yaddaş və hesab cihazları olan. Bu qurğular müasir kompüterlərdə oxşar cihazların prototipləri oldu.

Maşınların növləri.

Maşın kimi şərh edilə bilər enerjinin, materialların və ya məlumatların qəbulu, çevrilməsi və ötürülməsi proseslərini onlarda müəyyən edilmiş proqrama uyğun olaraq, lakin şəxsin birbaşa iştirakı olmadan həyata keçirən cihaz.

Hər maşının özünəməxsusluğu var baza dəstləri, bunlara daxildir: giriş əlifbası, çıxış əlifbası, avtomat vəziyyətləri dəsti.

Sonlu avtomatın xarakterik xüsusiyyəti mövcudluğudur yaddaş, zamandan asılı olaraq avtomatın vəziyyətini müəyyən edən. Avtomatın müxtəlif vəziyyətlərinin xarici təzahürü onun eyni tip təsirlərə (siqnallara) reaksiyasıdır.

Sonlu rəqəmsal avtomatların işində mühüm bir anlayışdır vaxt.

Avtomatlar müxtəlif meyarlara görə təsnif edilə bilər.

1. Fəaliyyət növünə görə - avtomatlar bölünür: məlumat, idarəetmə və hesablama.

Kiməinformasiya maşınları müxtəlif istinad cədvəlləri, stadionlarda məlumat lövhələri, siqnalizasiya cihazları daxildir.

Kimə nəzarət maşınları müəyyən bir prosesi idarə etmək üçün cihazları aid etmək adətdir, o cümlədən: lift, konveyer, dəzgah, maneə.

Kimə hesablama maşınları mikrokalkulyatorlar, kompüter prosessorları və hesablamaları yerinə yetirən digər qurğular daxildir.

Ancaq ciddi şəkildə desək, bir çox avtomatlar belədir mürəkkəb sistemlər ki, onlar həm hesablama, həm idarəetmə, həm də informasiya avtomatlarıdır.

2. Sonlu avtomatlar - informatika nöqteyi-nəzərindən bunlar diskret informasiya çeviriciləri olan avtomatlardır. Bunlara sonlu giriş və sonlu çıxış siqnalları, eləcə də sonlu daxili vəziyyətlər dəsti olan çeviricilər daxildir.

3. Rəqəmsal maşınlar- çevirən avtomatlar rəqəmsal məlumat. Belə bir avtomatda giriş siqnalları ani simvolların sonlu dəsti kimi verilir: onların müddəti o qədər kiçikdir ki, onu nəzərə almamaq olar. Sabit bir müddət üçün giriş simvolları çevrilir və çıxış bir vəziyyətdən digər vəziyyətə keçiddir.

4. Abstrakt avtomatlar - giriş əlifbasında sözlər toplusunu göstərir Xinçıxış əlifbası sözləri toplusu Y.

Mücərrəd avtomat belədir:

~ Riyazi model,

~ Alqoritm kod ardıcıllığının bəzi transformasiya hərəkətləri,

~ Qanun giriş əlifbasının çıxış əlifbasına çevrilməsi.

5. Sinxron və asinxron avtomatlar. Giriş siqnalının və vəziyyətin dəyişməsi siqnalının eyni vaxtda və ya ardıcıl olaraq qəbul edilməsindən asılı olaraq, avtomatlar sinxron və asinxron avtomatlara bölünür.

Sinxron maşınlarda giriş siqnallarının müddəti və keçidlərin vaxtı bir-biri ilə əlaqələndirilir. Onlar kompüter sistemlərində, avtomatlaşdırılmış idarəetmə sistemlərində və s.

Asinxron maşınlarda giriş siqnallarının müddəti və keçidlərin vaxtı bir-biri ilə əlaqələndirilmir. Onlar xarici mənbələrdən asılıdır - müxtəlif hadisələr və seçmə intervalı dəyişəndir (məsələn, kombinasiyalı kilidlərdə). Asinxron avtomatlarda, giriş siqnallarının dəyərlərində növbəti dəyişiklik yalnız bu siqnallarda əvvəlki dəyişikliyin səbəb olduğu keçici proses başa çatdıqda baş verə bilər.

6. Avtomatlar sonlu və sonsuz avtomatlara bölünür. Təsnifat əsasında aparılırsa yaddaş ölçüsü, onda fərq avtomatın olub-olmamasındadır final və ya sonsuz daxili dövlətlərin sayı.

Sonsuzluğun altında avtomat adətən sonsuz sayda vəziyyətə malik olan avtomat haqqında fikirlərin müəyyən riyazi ideallaşdırılması kimi başa düşülür. Belə bir avtomatın yaddaşı qeyri-müəyyən müddətə böyüyə bilər. Məsələn, məşhur Post və Turing mücərrəd avtomatları sonsuz avtomatlardır, lakin kompüterin özü və ya onun ayrı-ayrı hissələri sonlu avtomatlardır.

7. Avtomatlar deterministik və ehtimal avtomatlarına bölünür. Təsnifat əsasında aparılırsa təsadüfi seçim mexanizmi sonra deterministik və ehtimal (stokastik) avtomatlar arasında fərq qoyulur.

Deterministik avtomatlarda zamanın hər anındakı davranış və quruluş, cari giriş məlumatı və vaxtın əvvəlki anında avtomatın özünün vəziyyəti ilə unikal şəkildə müəyyən edilir.

Ehtimallı avtomatlarda bu asılılıq bəzi təsadüfi seçimlə də əlaqələndirilir.

Ehtimal avtomat diskret informasiya çeviricisidir ki, onun fəaliyyəti hər bir zaman anında yalnız yaddaş vəziyyətlərindən asılıdır və statistik qanunlarla təsvir olunur.

8. Universal maşın. Avtomatlar nəzəriyyəsində sübut edilmişdir ki, informasiyanın müxtəlif çevrilmələrini həyata keçirmək üçün sadəcə olaraq, universal hər hansı bir problemi həll etməyə qadir olan bir proqramın və müvafiq kodlaşdırmanın köməyi ilə avtomatik maşın.

Bir girişli rəqəmsal avtomatın riyazi modeli beş obyekt tərəfindən verilir:

X- giriş simvollarının sonlu dəsti, giriş əlifbası:

X \u003d (x 1 (t), x 2 (t), ..., x n (t));

Y- sonlu çıxış simvolları dəsti, çıxış əlifbası:

Y \u003d (y 1 (t), y 2 (t), ..., y n (t));

Q~ avtomat vəziyyətlərinin sonlu dəsti:

Q= (q 0 (t), q 1 (t), q 2 (t), …, q n (t)), q0- ilkin vəziyyət;

δ(q, X) - avtomatın bir vəziyyətdən digərinə keçid funksiyası: ( Q X x)®Q;

λ(q, X) ~ avtomat çıxış funksiyası: ( Q x X) ® Y.

Yəni dövlət maşını C=(X, Q, Y, δ, λ.) rekursiv əlaqələrlə müəyyən edilir

q(0) = q 0 , q(t + I) = δ (g(t), x(t)), y(t) = λ (g(t), x(t)),

t zamanın diskretləşdirilmiş momentidir, yoxsa monoton funksiyanın şəklidir t:. T® N, və T - adi davamlı zaman, N natural ədədlər çoxluğudur.

Bütün iş saatları T sərhədində avtomatın vəziyyəti dəyişən sonlu sayda intervallara bölünür. Eyni zamanda, t(Г 0) G 0 vaxtından əvvəl baş vermiş dəyişikliklərin sayını göstərir.

Diskretləşdirmə nümunəsi adi kinoteatrdır: vaxt 1/24s intervallarına bölünür. İnsan gözü diskret çərçivələrdən sonrakı hərəkətləri davamlı hərəkət kimi qəbul edir.

9. Sinxron avtomatlar Mealy avtomatlarına və Mur avtomatlarına bölünür. -dən asılı olaraq çıxış funksiyasını təşkil etmək üsulu sinxron maşınlar Mealy maşınlarına bölünür ( birinci növ avtomatlar) və Mur avtomatları (ikinci növ avtomatlar).

Mili avtomatlarında- çıxış siqnalı y(t) x(t) və dövlət q(t- 1) əvvəlki vaxtda avtomat (t- 1). riyazi model belə avtomatlar tənliklər sistemidir:

q(t) = δ (q(t-1), x(t)) və y(t) = λ (q(t-1), x(t)),

Moore maşınlarındaçıxış siqnalı y(t) giriş siqnalı ilə unikal şəkildə müəyyən edilir x(t) və dövlət q(t) in Bu an vaxt t. Belə avtomatların riyazi modeli sistemdir:

q(t) = δ (q(t-1), x(t)) və y(t) = λ (q(t)),

Belə avtomatlarda çıxış funksiyası yalnız avtomatın verilmiş vaxtdakı vəziyyətlərindən asılıdır və giriş siqnalından asılı deyildir. Beləliklə, belə avtomatın giriş sətri bir dəfə soldan sağa oxunur, simvollar üzrə skan edilir. Müəyyən bir vaxtda dövlət maşını növbəti simvolu oxuduqdan sonra dəyişən hansısa daxili vəziyyətdədir. Yeni vəziyyət oxunmuş simvol və cari vəziyyətlə xarakterizə edilə bilər.

10. Qarışıq avtomatlar– elə avtomatlar var ki, orada çıxış simvolu onun vəziyyətindən asılı deyil və yalnız cari giriş simvolları ilə müəyyən edilir, yəni. bu avtomatda bütün dövlətlər ekvivalentdir. Belə bir avtomatda keçid funksiyası pozulur, iş zamanı prinsipcə əhəmiyyətsizdir və dəyişməzdir. Buna görə də, minimal kombinasiyalı avtomat yalnız bir vəziyyətə malikdir.

11 Boolean avtomatlar - giriş əlifbası ibarət olan avtomatlar var 2 t ikili uzunluq dəstləri t, və çıxış 2 n uzunluqlu ikili dəstdəndir P.üçün məntiqi birləşmə avtomat, çıxış funksiyası sistem formasına malikdir P məntiq funksiyalarından t dəyişənlər.

Sonlu avtomatın təsviri əslində onu təyin edən avtomat funksiyalarının təsvirinə endirilir.

Sonlu avtomatları təyin etməyin üç yolu var:

· Cədvəl (keçidlərin və çıxışların matrisləri);

Qrafik (qrafiklərdən istifadə etməklə);

· Analitik (düsturlardan istifadə etməklə).

Analitik üsul– avtomat tənliklər sistemi ilə verilir. Belə bir sistemdən belə nəticə çıxır ki, sonlu sayda mümkün daxili vəziyyətlər üçün avtomat funksiyalarının mümkün qiymətlərinin sayı da sonlu olur. Belə tapşırığa misal olaraq Mealy avtomatlarını və Mur avtomatlarını təyin edən tənliklər sistemini göstərmək olar

cədvəl üsulu. Keçid funksiyası - δ və çıxış funksiyası üçün avtomatın vəziyyətinin cədvəli tərtib edilir. Burada:

cədvəlin sütunları giriş əlifbasının elementlərinə uyğun gəlir x,

cədvəl sətirləri vəziyyətlərə uyğundur (sonlu çoxluğun elementləri Q).

i-ci sətirlə j-ci sütunun kəsişməsi avtomatın vəziyyətdə olduğu anda onun 8 və λ funksiyalarının arqumenti olan (i, j) xanasına uyğun gəlir. qi onun girişində - söz x j , və müvafiq xanada 8 və λ funksiyalarının qiymətlərini yazırıq. Beləliklə, bütün cədvəl komplektə uyğun gəlir Q X x.

Keçid cədvəlini doldurarkən, hər bir xana unikal olaraq bir cüt simvolla müəyyən edilir: növbəti vəziyyətin simvolu və çıxış siqnalının simvolu.

Təcrübədə avtomat funksiyaları müvafiq olaraq adlandırılan iki sonlu cədvəllə verilir keçid matrisi və nəticə matrisi. Bu halda sətirlər daxil edilən əlifbanın hərfləri ilə, sütunlar isə daxili əlifbanın hərfləri ilə (avtomatın daxili vəziyyətini kodlayan simvollar) işarələnir.

Keçid matrisində x k sətri ilə q r sütununun kəsişməsində keçid funksiyasının qiyməti δ(q i , X) və nəticə çıxarma funksiyaları λ(q, X). Bəzi hallarda hər iki cədvəl bir cədvəldə birləşdirilir.

Qrafik üsul.

Avtomat qrafikdən, diaqramdan, qrafikdən və s. istifadə etməklə müəyyən edilir. İstiqamətləndirilmiş qrafikdən istifadə edilən tapşırıq avtomatı təsvir etməyin daha rahat və yığcam formasıdır.

avtomat qrafiki ehtiva edir

· zirvələr, dövlətə uyğundur qi OK,

· qövslər, birləşdirən təpələr avtomatın bir vəziyyətdən digərinə keçididir. Qövslərdə giriş və çıxış siqnallarının cütlərini - keçid siqnallarını göstərmək adətdir.

Əgər avtomat dövlətdən keçərsə q 1 bir vəziyyətə q2 bir neçə giriş siqnalının təsiri altında, onda bu variant disjunksiya vasitəsilə qrafikin müvafiq qövsündə təmsil olunacaq. Avtomatı təmsil etmək üçün fərqlənən ilkin və son vəziyyətləri olan bipolyar qrafiklərdən istifadə olunur.

“Tutanım ölçmə aləti” şkalasının işlənib hazırlanması

№ göstərici + - həddindən artıq yüklənmə off ┤
0 ilkin vəziyyət 1 0 0 0 Yox
1 0 2 0 13 0 Bəli
2 50 3 1 13 0 Bəli
3 100 4 2 13 0 Bəli
4 150 5 3 13 0 Bəli
5 200 6 4 13 0 Bəli
6 250 7 5 13 0 Bəli
7 300 8 6 13 0 Bəli
8 350 9 7 13 0 Bəli
9 400 10 8 13 0 Bəli
10 450 11 9 13 0 Bəli
11 500 13 10 13 0 Bəli
12 OV 0 0 0 0 Yox
13 qəza 0 0 0 0 Yox

Şəkil 2.5. Kapasitansı ölçmək üçün cihazın şkalasının qrafiki


Nəticə

Yüksək tezlikli salınımları yaratmaq üçün salınan dövrələri olan generatorların (RC tipli) istifadəsi qane etmədiyindən, hazırlanmış generator üçün LC tipli bir dövrə götürüldü (fazalı dövrə kimi avtotransformator birləşməsi olan üç nöqtəli dövrə götürüldü, aktiv element tranzistordur).

Bunun nəzəri hissəsində kurs işi LC tipli generatorların elementləri nəzərdən keçirilmişdir. LC tipli generatorların təsnifatı, təyinatı, həmçinin müxtəlif generator sxemləri də nəzərdən keçirilmişdir. Eləcə də spesifikasiyalar generator elementləri.

Praktiki hissədə enkoderlər, dekoderlər, onların təyinatı haqqında mövzu açıqlanmış, həmçinin kodlayıcı və dekoderlərin elektrik funksional və elektrik sxemləri tərtib edilmişdir. Karnot xəritələrinin mövzusu açıldı. Yeddi seqmentli indikatorun “b” seqmenti də işlənib hazırlanmışdır. Kapasitansı ölçmək üçün alətin miqyası üçün dövlət maşını, eləcə də onun qrafiki hazırlanmışdır.


Baranov Viktor Pavloviç Diskret Riyaziyyat. Bölmə 6. Dövlət maşınlarıvə rəsmi dillər.

Mühazirə 31 Sintez tapşırığı. Elementar avtomobillər və sən

Mühazirə 30 SONLU AVTOMATIN TƏYİRİ VƏ TƏYİQ EDİLMƏ METODLARI.

SİNTEZ PROBLEMİ. ELEMENTARY AVTOMATLAR

Mühazirə planı:

1. Sonlu avtomatın tərifi.

2. Sonlu avtomatın təyini üsulları.

  1. Avtomat sintezi problemi.
  2. Elementar maşınlar.
  3. Avtomat əsasının tamlığı problemi.
  4. Avtomat sintezi üçün kanonik üsul.
  1. Dövlət maşınının tərifi

SFE real cihazların vaxtında işləməsini nəzərə almır. SFE ilə müqayisədə sonlu avtomat diskret çeviricinin daha dəqiq modelidir. b məlumat tərtibatçısı. Eyni zamanda, hər hansı bir model kimi, sonlu avtomat anlayışı da var I lakin bir sıra sadələşdirici fərziyyələrlə.

Birincisi, avtomatın giriş və çıxışının istənilən vaxt məhdud sayda müxtəlif vəziyyətlərdən yalnız birində ola biləcəyi güman edilir. Real olsa b Konvertorda davamlı giriş siqnalı varsa, onu sonlu avtomatdan istifadə edərək təsvir etmək üçün bu siqnalı kvantlaşdırmaq lazımdır. Avtomatın formal tərifində avtomatın giriş və çıxış vəziyyətlərinin sonlu dəsti coo adlanır. t daxilinə məsuliyyətlə və çıxış əlifbası, və ayrı-ayrı dövlətlər bu alfa və vits hərfləri.

İkincisi, zamanın diskret olaraq dəyişdiyi güman edilir. Giriş və çıxış vəziyyətləri diskret vaxt ardıcıllığına uyğundur. b Zaman anı onun indeksi ilə unikal şəkildə təyin olunduğundan, sadəlik üçün zamanın 1, 2, ..., dəyərlərini qəbul etdiyini güman edəcəyik ... Zaman intervalı adlanır. nəzakət.

Maşının işləməsi aşağıdakı kimi təqdim olunur.

Avtomatın girişi giriş əlifbasından siqnalları qəbul edir ki, bu da giriş əlifbasının çıxışında siqnalların görünməsinə səbəb olur. W a Çıxış ardıcıllığının giriş ardıcıllığından asılılığı avtomatın daxili strukturundan asılıdır. Qeyd edək ki, yaddaşı olmayan SFE-dən fərqli olaraq avtomat pre d yaddaşa malik bir cihazdır, yəni avtomatın çıxışı təkcə müəyyən edilmir b girişə, həm də arxa tərəfə. Tarix mühasibatlığı I çıxış siqnalının təkcə girişdən deyil, həm də işarə etdiyimiz cari vəziyyətdən asılılığı ilə müəyyən edilir.

Gəlin avtomatın rəsmi tərifini verək.

dövlət maşınıbeş obyekti adlandırın

, (1)

harada

giriş əlifbası; mümkün giriş dövlətlərindən biri;

adlı sonlu çoxluqçıxış əlifbası; element bu dəstdən siz mümkün çıxış vəziyyətlərini müəyyənləşdirirsiniz;

adlı sonlu çoxluqdaxili dövlətlərin əlifbası mən nii;

– keçid funksiyasımaşın: ; bu funksiya hər bir “giriş vəziyyəti” cütlüyünə bir vəziyyət təyin edir;

çıxış funksiyası maşın: ; bu funksiya hər bir giriş-dövlət cütünü çıxış dəyəri ilə əlaqələndirir.

Avtomatın işləmə qanunu: avtomat öz vəziyyətlərini uyğun olaraq dəyişir t funksiyasını yerinə yetirir və funksiyaya uyğun olaraq çıxış siqnalları yaradır hərəkətə:

  1. Dövlət maşınının müəyyənləşdirilməsi yolları

1. Cədvəl tapşırığı üsulu. Çünki funksiyalar və əhatə dairəsi üçün e qiymətlər və dəyərlər sonlu çoxluğa aiddir, sonra cədvəllərdən istifadə etməklə müəyyən edilir.

Misal 1 Biz avtomatı aşağıdakı kimi təyin edirik: , .. istifadə edərək funksiyanı təyin edintullanma masaları,və istifadə edilən funksiyaçıxış masaları.

Cədvəl 1. Jump cədvəli Cədvəl 2. Çıxış cədvəli

Giriş

dövlət

Giriş

dövlət

Əgər avtomatın girişindəki siqnalların ardıcıllığı məlumdursa, onda cədvəllər e hərəkət və çıxışlar çıxış ardıcıllığını unikal şəkildə müəyyən edir.

2 . Quraşdırmanın qrafik yolu. istifadə olunur keçid-çıxış diaqramı.Bu, hər bir daxili olan yönəldilmiş multiqrafdır t zirvəsi avtomatın ilkin vəziyyətinə uyğundur. Avtomatın vəziyyətdən vəziyyətə keçidləri hər birində bir giriş simvolu yazılmış oxlarla təsvir edilmişdir. s bu keçidi çağırır və avtomat tərəfindən yaradılan çıxış simvolu.

| | |

Şəkil 1 Keçid-çıxışların diaqramı

Misal 2 Aşağıdakı kimi işləyəcək bir avtomat qurmaq tələb olunur a zom: hər dövrədə terminlərin növbəti ikili rəqəmləri avtomatın girişində qəbul edilir və in pomidor onların cəminin müvafiq ikili rəqəmini çıxarır. İki üçün h sıra şərtlərimiz var: , .

Əvvəlki rəqəmləri əlavə edərkən, avtomat 1 vəziyyətdədir və daşıyır və əks halda 0 vəziyyətindədir. Keçid-çıxış diaqramı və əncirdə zana. 2.

00|0 11|1 01|0

01|1 10|0

10|1 00|1 11|1

düyü. 2

  1. Avtomat sintezi problemi

SFE-nin sintezi probleminə bənzətməklə, avtomatik sistem üçün sintez problemi qoyula bilər. a yoldaş Əsas avtomatların limitsiz dəsti var. Əvvəlcədən müəyyən edilmiş funksiyaya malik bir avtomat yığmaq tələb olunur. Bu zaman sintez problemi toqquşur t müəyyən problemlərlə.

Fərz edək ki, avtomatın çıxışını avtomatın girişinə qoşmaq lazımdır. Bu başqa bir şərtlə mümkündür haqqında sürü maşını birincidən gələn siqnalları başa düşməyəcək. Bu, çaşqınlığa gətirib çıxarır və bəzi əlaqələrin mümkün olmadığı vəziyyətlər.

Bu maneəni aradan qaldırmaq üçün struktur avtomatı konsepsiyası təqdim olunur haqqında bütün əlifbalar (giriş, çıxış və daxili vəziyyətlər) ikili sözlərlə kodlanır.

Elementlərin sonlu çoxluğu olsun və çoxluq olsun e uzunluqlu ikili sözlər toplusu, burada. İxtiyari injektiv xəritələşdirmə çağırılacaqçoxluğun ikili sözlərlə kodlaşdırılması.

İxtiyari avtomat üçün əlifbaları kodlayaq:

Avtomatın müvafiq olaraq zaman anında kodlanmış girişini, çıxışını və vəziyyətini işarə edək. Sonra əməliyyat qanunu formada təqdim olunacaq

(2)

Kodlaşdırmadan sonra əldə edilən avtomat adlanır struktur . Biz güman edirik ki, struktur avtomatının ikili girişləri, ikili çıxışları var və avtomatın daxili vəziyyəti ikili uzunluqlu sözlə verilir. Əncirdə. 3 göstərilir mücərrəd avtomat və ona uyğun struktur avtomatı.

… …

düyü. 3

Struktur avtomata keçid sintez üçün iki mühüm üstünlük verir. e stva.

1 . Giriş və çıxışların uyğunluğu, ikili və n formalaşması. SFE-yə bənzəyən struktur avtomatlardan bir dövrənin ümumi tərifini verməyəcəyik.

2 . Əlaqələri (2) “koordinatlarda” yazaq:

(3)

(3) dən belə nəticə çıxırkonstruktiv avtomatın işləmə qanunu ilə verilir və Boolean Funksiya Kök.

  1. Elementar avtomatlar

Biz ən sadə struktur avtomatları ayırırıq və onlara ad veririk.

Əvvəlcə qeyd edək ki, yalnız bir vəziyyətə malik olan funksional element yaddaşsız avtomat hesab edilə bilər.

Gəlin iki vəziyyətlə avtomatlara keçək. Avtomatın daxili vəziyyətlə üst-üstə düşən bir ikili giriş və bir ikili çıxışı olsun: :

düyü. dörd.

Şəkildə göstərilən avtomatı təyin etmək üçün. 4, yalnız p cədvəlini göstərmək kifayətdir e keçidlər:

Cədvəl 3

Giriş

dövlət

Ulduz işarələri yerinə 0 və 1 qoymaq lazımdır. Bunu 16 yolla etmək olar, lakin onların hamısı məqbul deyil. Tutaq ki, məsələn, cədvəl 3-ün birinci sütununda hər iki element var n sən sıfırsan. Belə avtomat 0 vəziyyətində olduqdan sonra artıq ondan çıxmayacaq, yəni funksional element kimi işləyəcək. Oxşar vəziyyətlərin təhlili göstərir ki, yaddaşsız avtomata çevrilməyən avtomat əldə etmək üçün tələb etmək lazımdır. haqqında Cədvəl 3-ün hər bir sütununda həm sıfır, həm də bir olması təmin edilməlidir. Belə cədvəllər ego h e şin.

Cədvəl 4 Cədvəl 5

Giriş

dövlət

Giriş

dövlət

Cədvəl 6 Cədvəl 7

Giriş

dövlət

Giriş

dövlət

Bizdə yalnız iki ən sadə avtomat var, çünki daxili vəziyyətlərin çevrilməsi ilə 4-dən 7, 5-dən isə 6 alınır.

Cədvəl 4-də verilmiş avtomat adlanır gecikmə və ya tetikleyici:

yəni bu avtomat siqnalı bir dövrə gecikdirir.

Cədvəl 5-də göstərilən avtomat çağırılırsayğac girişi ilə işə salın və ya - tetikleyici . Giriş 1 olarsa avtomatın vəziyyəti əksinə dəyişir və giriş 0 olarsa dəyişməz qalır:

İlkin vaxtda icazə verin- trigger 0 vəziyyətindədir. Əgər n e hansı vaxtda- trigger 0 vəziyyətindədir, bu o deməkdir ki, avtomatın girişində cüt sayda birlər qəbul edilmişdir. 1-ci vəziyyətdədirsə, onda təkdir. Beləliklə, arr və zom, - trigger girişdəki vahidlərin sayını hesablayır, lakin onun yalnız iki vəziyyəti olduğu üçün I niya, sonra ikiyə qədər sayır.

Tətiklər fiziki olaraq həyata keçirildikdə, iki çıxış istifadə olunur: birbaşa və tərs (şək. 5). Onları dəyişdirsək, onda- trigger, siz cədvəl 7 ilə müəyyən edilmiş avtomat əldə edirsiniz və buradan- Cədvəl 6-da göstərilən trigger avtomatı.

düyü. 5.

  1. Avtomat əsasının tamlığı problemi

Struktur avtomatlar toplusu tam adlanır (və ya avtomat b a zisom) əgər onlardan əvvəlcədən müəyyən edilmiş hər hansı struktur avtomatını qurmaq mümkündürsə.

Avtomatlar üçün Post teoreminin analoqunu əldə etmək üçün riyaziyyatçıların səyləri artırılmır. n uğur qazandırdı. 1964-cü ildə M.İ. Müəyyən etmək üçün alqoritmin mövcud olmadığını qısaca sübut etdi e sistemin tamlığı. Bu zaman tamlıq teoreminin sistem haqqında əlavə fərziyyələrlə variantları maraq doğurur. Onlardan ən populyarını nəzərdən keçirək.

Teorem. avtomatik sistem,PV-nin tam dəstini ehtiva edir və -trigger (və ya -trigger) tamamlandı.

Sübut. Münasibətlə verilmiş ixtiyari avtomatı nəzərdən keçirək e (2) və adlanan göstərilən avtomatların sxemini təsvir edinkanonik quruluş(Şəkil 6) .

Sxem iki hissədən ibarətdir.

…

…

…

düyü. 6.

Sol yarısı yaddaş hissəsi adlanır. O, vəziyyətlər dəsti avtomatın vəziyyətini təşkil edən tetikleyicilərdən ibarətdir: əgər zaman anında

, …,

onda bu o deməkdir ki, avtomat vəziyyətdədir.

Sağ yarım birləşmə hissəsi adlanır və SFE-ni təmsil edir. Bu dövrənin girişləri:

  1. avtomatın ikili söz daxiletmə siqnalı;
  2. ikili söz avtomatın cari daxili vəziyyəti.

Çıxışlar:

  1. həyata keçirilən avtomatın ikili söz çıxış siqnalı t düsturlara görə (3);
  2. yaddaşa triggerlərin girişlərinə daxil olan ikili söz a cari hissədir və maşının yaddaşına nəzarət edir.

Göstərək ki, yaddaşa nəzarət siqnalları avtomatın çıxışı ilə eyni dəyişənlərin Boolean funksiyalarıdır, bu da onların tam şəkildə həyata keçirilə biləcəyini bildirir. və FE kökü.

Zamanın hər anında yaddaşa nəzarət siqnalları a tərcümə etməlidir in əyalətdən əyalətə pomidor. Bunu etmək üçün hər bir tetikleyicinin vəziyyətini dəyişdirməlisiniz

, .

Kanonik sxemdə istifadə olunan -triggers və ya -triggers aşağıdakılara malikdir e növbəti xüsusiyyət: hər hansı bir cüt dövlət üçün giriş siqnalı var, e dövlətdən ştata maşın sürmək. Bu siqnalı ilə işarə edək. -trigger üçün, çünki -triggerin qoyulduğu vəziyyət giriş siqnalına bərabərdir. -trigger üçün: n daxil etmək lazım olduqda haqqında vəziyyəti dəyişməz saxlamaq üçün 0 verin; 1-də, beləliklə, tətiyi "çevirir".

Beləliklə, ya da vektor şəklində

Avtomatın işləmə qanunundan (2) ifadə edək. Sonra

Teorem sübut edilmişdir.

  1. Avtomat sintezi üçün kanonik üsul

Bu üsulu konkret bir nümunə üzərində nəzərdən keçirək.

Misal. İki növ hissələrin hərəkət etdiyi və quraşdırıldığı konveyerdə in kətan maşını, vəzifəsi hissələri keçdikdən sonra elə bir şəkildə çeşidləməkdir e maşının yanından keçərək qruplar yaratdılar. Yanlış hissə maşın sta l montaj xəttindən başını yelləyir. Belə bir avtomatın dövrəsini -trigger və "AND", "OR", "NOT" elementlərindən istifadə etməklə qurmaq tələb olunur.

Avtomat sintezi aşağıdakı mərhələlərə bölünür.

1 . Abstrakt avtomatın qurulması.

Giriş əlifbası. Çıxış əlifbası, harada C hissəsinin toqquşması, P onun keçidi. Avtomatın daxili halları onun artıq qrupun hansı hissəsini təşkil etdiyi haqqında yaddaşını əks etdirir: . Qrup formalaşdıqca, avtomat uyğun olmayan hissə gəldikdə vəziyyəti dəyişmədən bu vəziyyətlər arasında dövri olaraq hərəkət edir. Keçid-çıxış diaqramı Şəkildə göstərilmişdir. 7.

| | |

düyü. 7.

2 . Əlifbanın kodlaşdırılması.

Mümkün kodlaşdırma seçimlərindən biri aşağıda verilmişdir. e üfürmə masaları.

Giriş Çıxış Vəziyyəti

3 . Avtomatın kanonik strukturunun qurulması.

İnkişaf etdirilən avtomatın kanonik quruluşu Şek. səkkiz.

düyü. səkkiz.

SFE çıxışlarının dəyişənlərdən asılılıqlarını k-yə uyğun olaraq əvvəlcə cədvəl şəklində tapaq (Cədvəl 8). haqqında sonra düsturları quracağıq

, .

Cədvəl 8

Bu funksiyalar adlanırqismən müəyyən edilmişdir, çünki onlar müəyyən edilməmişdir. Bu funksiyaları düsturlarla təmsil etmək üçün onlar düsturların daha sadə formasını əldə edəcək şəkildə genişləndirilir.

4 . Avtomat çıxış funksiyalarının və yaddaş idarəetmə funksiyalarının təmsil olunması r qatır.

Boolean funksiyalarını minimuma endirmək üsullarından istifadə edərək, mümkünsə, ek qururuq haqqında əsasda funksiyaların, düsturların nominal təqdimatı:

5 . SFE-nin həyata keçirilməsi və avtomatın yekun sxemi (şək. 9).

düyü. 9.

SFE

SFE

YOX

YA

 


Bölmələr



Reklam