Шекті автоматтар теориясының негіздері

фавиті берілсін. А және В алфавиттерінде барлық мүмкін болатын тізбектердің жиындары ретінде сәйкестікпен А^∞ және В^∞ жиындарын анықтаймыз.

( а.-функция) , егер b (t ) кез келген t = 1, 2, … үшін a(1), a(2), …, a(t ) анықталса.

а-функцияны былай белгілейтін боламыз:

a₁(1)…a₁(t )… → b₁(1)… b₁(t)…

φ: ,

a₂(1)…a₂ (2 )… → b₂(1)… b₂(t)…
егер a₁(1)=a₂ (1), онда b₁(1) = b₂(1)

a₁(1)=a₂ (1)

егер a₁(2)=a₂ (2)

, онда b₁(1) = b₂(1)

a₁(t)=a₂ (t)
Анықтама 2. φ: A^∞ → B^∞ а.-функция берілсін

Кез келген сөзін қарастырамыз. функциясын келесі түрде анықтаймыз: a(1), a(2), …, a(t )…— кез келген ену тізбегі болсын. Қарастырамыз:

Онда (a(1), a(2), …, a(t )…)= b(1)b(2)…b(t )…. сөзі бойынша φ функциясы үшін қалдық функция деп аталады.

Автоматтың енуі болып a(1)a(2)a(3)…, a(t )… A * тізбегі қызмет атқарады(шекті немесе шексіз), автоматтың шығуы болып z (t ) тізбегі қызмет атқарады, бұнда автомат

канондық теңдеулер жүйесімен беріледі:
z(t)=F(x(t),q(t-1)),

q(t)=G(x(t),q(t-1)),

q(0)=q₀
Анықтама 5. φ: A^∞ → B^∞ бейнесі автоматты функция деп аталады, егер оны жүзеге асыратын автомат болса.

Тұжырым. Функция тек қана шекті анықталған болғанда ғана автомат болып табылады.

Мысал. A = B = Q = {0, 1} және канондық теңдеулер жүйесі былай берілсін.
z(t)=q( t-1)

q(t)=x(t)

q(0)=q₀

Бұндай автомат a(1)a(2)...→0a(1)a(2)... бейнесін жүзеге асырады және бірлік кедергі деп аталады.

Ерекше түрде бастапқы күйге сәйкес келетін төбе белгіленген. Мур диаграммасы автоматты береді.

Сонда да A = B = {0, 1}, E₂ⁿ

n — n ұзындығы бар барлық бульдік векторлардың жиыны.

Теорема 1. Функционалды элементтерден және кедергілерден тұратын үлгі автоматты бейнелеуді жүзеге асырады.

Дәлелдеу. 1) Мәселен, үлгіде r кедергі элементтері болсын. i-ші кедергі R_i w_i төбесінен доға баратын v_i төбесіне жазылған болсын. Барлық i = 1, …, r үшін

КФЭҮ -ден доғаларды алып тастаймыз. КФЭҮ анықтамасы бойынша алынған графта бейімделген цикл болмайды және ол ФЭҮ -ні көрсететін болады. Бұл ФЭҮ -нің енулері болып алғашқы үлгінің барлық енулері бола алады, сонымен қатар v_i –дің барлық төбелері , i = 1, …, r осы үлгінің енуі бола алады. (ескерейік, олардың барлығы алғашқы үлгінің енуінен ерекше және өзгеше). Алынған ФЭҮ -нің шығысы ретінде алғашқы үлгінің барлық шығыстары мен w_і төбесінің барлық i = 1, …, r шығыстарын аламыз. Алғашқы үлгіге шығыс ретінде z₁, …, z_m айнымалылары жазылсын, ал енуге — x₁, …, x_n айнымалылары жазылсын. v_i төбелеріне q' 1, …, q' r айнымалыларын жазайық та, ал w_і-ға — q1, …, qr айнымалыларын жазайық. ФЭҮ -і функционалдандыру анықтамасына сәйкес fi, gj логика алгебрасының кейбір функциялары үшін былай жазған дұрыс:

(1)

(2)

(3)

Алынған теңдіктер КФЭҮ -дің функционалдауын анықтайды және оның канондық теңдеуі деп аталады.

2) ∑ үлгісімен жүзеге асатын ψ бейнелеуі (3) канондық теңдеуімен берілсін. E₂ⁿ, E₂^r,E₂^m –дегі сәйкес мәндерді қабылдайтын X=(x₁,…,x_n), Q=(q₁,…,q_r), Z=(z₁,…,z_m) айнымалыларын енгізейік. q₀=(0,...,0) болсын. Сонда (3) теңдікті мына түрде жазуға болады:

Z(t)=F(X(t),Q(t-1)),

Q(t)=G(X(t),Q(t-1)),

Q(0)=q₀
Мұндағы F, G функциялары t –дан тәуелсіз. Осы жерде үлгімен жүзеге асатын бейнелеу автомат беретін (E₂ⁿ, E₂^r, E₂^m ,F, G, q₀ ) бейнелеумен сәйкес келетіні көрініп тұр, яғни автоматты функция болып табылады. Теорема дәлелденді.

§37. Функционалды элементтер мен кедергі элементтері үлгісімен автоматты функцияны модельдеу.

Анықтама. φ автоматты функциясы А шекті алфавитінде тізбекті және В шекті алфавитіндегі тізбектерді көрсетсін. КФЭҮ ∑ E₂ⁿ –нің элементтері тізбегінен E₂^m –нің элементтерінің тізбегіне ψ өзгертуді іске асырсын. Бұны ∑ φ-ті модельдейді дейміз, егер әр түрлі элементтерге әр түрлі элементтерді сәйкес қоятын және А алфавитіндегі кез келген Р= a(1)a(2)...a(t) тізбек үшін егер

φ(Р) =Т= b (1)b (2)…b (t ) болса, онда ψ(К₁(Р)) = К₂(Т) болатын,

мұндағы К₁(Р) = К₁ (а(1))К₁(а(2))... К₁(а(t)), К₂(Т) = К₂ (b(1))К₂(b(2))... К₂(b(t)) қасиеттері бар К₁: А→ E₂ⁿ және К₂: В→ E₂^m бейнелеулері болса.

(1) теңдігі А-дағы кейбір әріптің коды болатын, ал В-дағы кейбір әріптің коды болатын тек қана , жұптары үшін G’және F’ бейнелеулерін анықтайды. Қалған G’ F’ бейнелеулерінің жұптары үшін еркін түрде алдын-ала анықтаймыз. болсын. Канондық теңдеулерімен Н=( E₂ⁿ, E₂^m, E₂^r, G’ , F’, )автоматын қарастырамыз:

Сонымен, (2) теңдікпен белгіленетін автоматты функцияны үлгі арқылы жүзеге асыруға болатынын көрсету жеткілікті. Х айнымалысының мәндері -нің п ұзындықтарының жиынтығы болып табылатындықтан, оны Е₂-ң мәндерін қабылдайтын (х₁, ..., х_п) айнымалыларының жиынтығы ретінде қарастыруға болады. Q мен Z айнымалылары үшін аналогиялық түрде болады. Онда (2) логика алгебрасының қандай да бір f_i, g_j функциялары үшін эквивалентті түрде жазуға болады:

Онда базисіндегі функционалды элементтерден n+r кірісі және m+r шығысы бар, функциялардың келесі тобынан тұратын үлгі құруға болады

Осы ФЭҮ-де кірістік айнымалысы шыңына келтірілген, ал q_j шығыстық айнымалысы w_j шыңына келтірілді. (w_j, ) доғасын қосып, шыңына тоқтау элементін сәйкестендірейік. Осының барлығын жұптарымен істеп, жұмыс істеуі келесі канондық теңдеулермен сипатталатын КФЭҮ аламыз