border=0

Foarbyld 9.2.

Foar in gegeven tabelere fertsjintwurdiging fan 'e masine, bouwe in systeem fan har kommando's.

Lit de steatmakker alfabetten hat X = { a, b } , Y = { a, b, c } , Q = {1, 2, 3}, en de automatonfunksjes wurde troch de tabellen jûn:

De presintearre twa tabellen kinne kombinearre wurde yn ien, dy't besletten hawwe om de wearde fan Y (qr, xk) yn elke sel yn de earste posysje te setten , en de wearde Q (qr, xk ) om de twadde posysje yn in komma te setten . It resultaat is it folgjende "pivot" tafel:

It kin sjoen wurde dat it tafel hielendal oan 'e tafel wurden is dat it funksjoneel skema fan' e Turing-masine beskiedt (sjoch seksje 7.3.3). Fan it is it maklik om te sjen fan de konvertearjen fan dizze masine:

Tink derom dat by de earste klok de automaton yn 'e steat q 0 = 1 is en de sesje abb oanbrocht wurdt oan syn ynput nei de folgjende kloksynten . Mei de list fan kommando's kinne jo festigje dat de automaton dizze sesje nei bcc konvertearret en tagelyk yn steat 3 stiet.

In oare opsje foar it skriuwen fan automatyske funksjes is grafysk. It hat mear sichtberheid as de tabel. De staten fan 'e automaton <X, Y, Q, Y, Q > wurde definiearre troch middel fan in oriïntearre grafyk, dy't in diagram hjit (krekter, in Moore-diagram). De rintiten fan 'e graf binne markearre mei symboalen fan it alfabet fan' e steaten fan 'e automaton Q , en elke kommando q i x r → q j y s komt oerien mei in kante dy't út it kwestje q i giet nei it vertex q j , en de kante is in etiket x r y s oanwêzich . Sa ûntstiet in kante as de automaton yn 'e state q i kin wurde oerbrocht nei de steat q j mei wat inkelde yntaksaal x r . As sa'n oersetting mooglik is mei ferskate ynfier effekten ( x g ) (1) ..... (x r ) (n) , en dus wurde de útfieringsignalen ( y s ) (1) , ..., (y s ) foarmje (n) , dan wurdt de kante de ekspresje (( x r ) (1) , ( y s ) (1) ) f (( x r ) (2) , ( y s ) (2) ) ... x r ) ( n ) , ( y s ) ( n ) .

Foar diagrams dy't in finite automaton fertsjintwurdigje, binne de neikommende statementen wier:

1. fan ien kertier kin net twa rigen gean mei itselde ynputsymbol (de kondysje fan ienichheid);

2. As yn 'e operaasje fan de automaton de ynfierkombinaasje q i x r realisearre is , dan is der nea in râne kommen fan' e vertex q ik markearre mei it symboal x r (folsleine standert);

3. It oantal stikken en kanten fan it skema is finite.





Sjoch ek:

Presentaasje fan elementêre gegevens yn RAM

Natuer- en keunstmjittige systemen

Klassifikaasje- en gegevensstruktuer-foarbylden

Foarbyld 2.7

Objektfoarming

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info