Autors: ROBERTS GLAUDIŅŠ

Darbā analizēta automāta reprezentācija ar daļēji definētām transformācijām - automāta transformāciju kopa. Konstruēts piemērs, kas parāda, ka attiecībā pret modelēšanu nesalīdzināmiem automātiem transformāciju kopas var sakrist. Vēl vairāk - šis rezultāts ir spēkā arī īpaši reducētiem automātiem.

Citāds stāvoklis ir autonomu automātu klasē, kas pētīta sīkāk. Pamatrezultāts:

Līdzīgas transformāciju kopas ar precizitāti līdz izomorfismam nosaka vienu vienīgu īpaši reducētu autonomu automātu.

APZĪMĒJUMU SARAKSTS.

q ~ q¢ - neatšķirami automāta stāvokļi,

V “ V¢ - neatšķirami automāti,

V¢ŲV - automāts V¢ modelē automātu V,

V¢Ų×V - automāti V¢ un V modelē viens otru,

ļAļ - kopas A apjoms,

įV_gń - automāta V pusgrupa,

A* - visu iespējamo fiksēto A alfabēta vārdu kopa,

B* - visu iespējamo fiksēto B alfabēta vārdu kopa,

JĒDZIENI UN SVARĪGĀKIE APZĪMĒJUMI.

Šajā nodaļā aplūkosim jēdzienus un apzīmējumus, kuri turpmāk tiks izmantoti darbā.

Par alfabētu sauksim grafisku simbolu (burtu) galīgu virkni, kuras locekļi ir cits no cita atšķirami. Piemēram, grafisku zīmju virkne A, kur A={a,b,c}, atskaitot simbolus "{" un "}" , uzskatāma par alfabētu. Par vārdiem dotajā alfabētā A sauksim galīgas simbolu virknes, kuru locekļi ir A burti. Piemēram, alfabētā {a,b,c} par vārdiem uzskatāmas simbolu virknes ab,c,bb,acb u.c. Tukšā vārda apzīmēšanai izmantosim simbolu e. Lai apzīmētu visu iespējamo fiksēta alfabēta A vārdu kopu, lietosim simbolu A*.

Divi dotā alfabēta A vārdi ir vienādi, ja:

1) tie abi ir tukšie vārdi,

2) tos abus veido alfabēta A burtu virknes, kurām ir

vienāds locekļu skaits un vienādi attiecīgie locekļi.

Piemēram, ja apskatam alfabētu A, A={a,b,c}, un tajā definētus vārdus a, bc, ab, bc, cc, tad otrais un ceturtais vārds šajā virknē ir uzskatāmi par vienādiem.

Ja u=a₁....a_n ir dotā alfabēta A vārds, kur “j a_jĻA ,tad par tā garumu sauksim u veidojošās burtu virknes locekļu skaitu n un apzīmēsim to ar l(u). Piemēram, ja dots alfabēts {a,b,c} un tajā vārds u=ccaba, tad l(u)=5. Tukšā vārda e garums, pēc definīcijas, ir 0, t.i., l(e)=0.

Terminu kopa lietosim matemātikā vispārpieņemtajā nozīmē. Ja A- kopa, tad ½A½-šīs kopas apjoms.

Ja A,B- kopas, tad pieraksts AĮB nozīmē, ka A ir kopas B apakškopa.

Kopu A un B Dekarta reizinājumu apzīmēsim ar A ´ B.

Ar simbolu := aizvietosim vārdisku apgalvojumu " ir pēc definīcijas ".

Ar j: A®B apzīmēsim kopas A attēlojumu kopā B.

Pieņemsim, ka j: A®B ir attēlojums. Mēs teiksim, ka :

1) j ir injekcija, ja no a₁¹ a₂ seko j(a₁) ¹ j(a₂);

2) j ir sirjekcija, ja “bĻB eksistē tāds aĻA, ka j(a)=b;

3) j ir bijekcija, ja tas vienlaicīgi ir gan sirjekcija, gan injekcija.

Ja j ir injekcija, tad ar j^-1 apzīmēsim j inverso attēlojumu.

Ar j(A¢) apzīmēsim apakškopu kopā B, kura sastāv no visiem b Ļ B, kuriem atradīsies a Ļ A¢, ka j(A) = b, t.i. , j(A¢) = {b , $ a Ļ A¢ j(a) = b }.

Pieņemsim, ka j:A®B ir attēlojums un B¢- apakškopa kopā B. Ar j^-1(B) apzīmēsim apakškopu kopā A, kura sastāv no visiem tiem a Ļ A, kuriem

j(A)ĻB¢ ,t.i., j^-1(B¢) := { a , j(a)ĻB¢ }.

Pieraksts i= 1 n nozīmē, ka indeksi i

mainās robežās no 1 līdz n pa visiem naturāliem skaitļiem.

Loģiskās operācijas Ś(un), Ū(vai), Ź(seko), Ų(tad un tikai tad), “(visiem), $(eksistē) lietosim vispārpieņemtajā nozīmē.

Zīme o tekstā atzīmē pierādījuma sākumu, bet ¦ pierādījuma beigas.

Netukšu kopu ar tajā uzdotu asociatīvu bināru operāciju sauc par pusgrupu. Pusgrupu sauc par monoīdu, ja tajā ir izdalīts vienības elements. Piemēram, kopa A* ar tajā definētu operāciju " vārdu konkatenācija " ir monoīds. Vienības elements šajā pusgrupā ir e.

Attēlojumu j no pusgrupas A pusgrupā B sauc par homomorfismu,

ja j(xy) = j(x)j(y) katram x,yĻA. Šeit xy nozīmē operāciju pusgrupā A, bet j(x)j(y) operāciju pusgrupā B. Savstarpēji viennozīmīgu homomorfismu sauc par izomorfismu.

Definīcija. Algebrisku sistēmu V=(A,B,Q,*,˚ ) sauc par Milī tipa automātu,ja A,B,Q ir netukšas galīgas kopas, bet *: Q´A®Q, ˚: Q´A®B - attēlojumi, bez tam attēlojums ˚ ir sirjektīvs.

Kopu Q sauc par stāvokļu kopu, A- par ieejas alfabētu, B- izejas alfabētu. Attēlojumu * sauc par pārejas funkciju, ˚- par izejas funkciju.

Turpmāk termina "Milī tipa automāts" vietā lietosim īsāku terminu "automāts".

Ja būs doti vairāki automāti, piemēram, V=(A,B,Q,*,˚) un V¢=(A¢,B¢,Q¢,Ä,:), tad automātus V=(A,B,Q,*,˚) un V¢=(A¢,B¢,Q¢,Ä,:) apzīmēsim arī šādi V=(A,B,Q) un V¢=(A¢,B¢,Q¢). Šai situācijā, mēs nebūt neuzskatām, ka automāta V pārejas un izejas funkcijas sakrīt ar automāta V¢ pārejas un izejas funkcijām , kaut arī atklātā veidā šīs operācijas nenorādam.

Mēs uzskatām, ka no konteksta var atšķirt automātam domātās

operācijas * un ˚ . Ja var rasties pārpratumi, tad lietosim arī citus apzīmējumus, piemēram, Ä un : automātam V' .

Automātu funkcionēšanu raksturo attēlojumu * un ˚ paplašinājumi kopā Q´A^*. Šos paplašinājumus definēsim rekursīvi.

Pieņemsim, ka qĻQ, aĻA un uĻA*.

Definīcija. 1) q*e =q ;

2) ja u¢= ua un q*u definēts, tad q*u¢ = ( q*u ) * a.

Definīcija. 1) q˚e = e ;

2) ja u¢= ua un q˚u definēts, tad q˚u¢= ( q˚u)(( q*u)˚a).

Par funkciju *,˚ definīcijas kopu turpmāk varam uzskatīt Q´A*. Izejas funkcijas * definīcijas kopa tiks paplašināta, tātad tiks paplašināta arī vērtību kopa, t.i., turpmāk tā būs B*. Šo funkcionēšanu visprecīzāk raksturo sekojoša teorēma.

Teorēma. Dots automāts V=(A,B,Q,*,˚), tādā gadījumā katram vārdu pārim (u,v) alfabētā A ir spēkā vienādība :

q*(uv)=(q*u)*v ; (1)

q˚(uv)=(q˚u)((q*u)˚v). (2)

Šīs teorēmas pierādījums atrodams [1] grāmatā (1.6.1. teorēma ).

1. nodaļa.

AUTOMĀTA PUSGRUPA.

1§.Visur definēta pusgrupa.

Dots automāts V=(A,B,Q), kur A={a₁,......,a_n} -ieejas alfabēts B={b₁,.....,b_m} -izejas alfabēts un Q ={q₁,.....,q_k} stāvokļu kopa.

Visur definētus kopas Q attēlojumus sevī sauc par transformācijām. Šo transformāciju veidoto pusgrupu apzīmē ar T_r(Q).

Automāta katram burtam a_i piekārtosim transformāciju

q₁ .......... q_k

q^'_k ......... q^'_k

g_i= ,kur q_j¢=q_j*a_i , i =i k un j = i k

Automātam V definēsim pusgrupu, kuras veidotājelementi būs transformācijas g_i. Šo elementu kopu apzīmēsim ar V_g={g_i i= 1 n }.Transformācijas kopas V_g ģenerēto pusgrupas T_r(Q) apakšpusgrupu ć V_g ń sauc par automāta V pusgrupu. Šādi piekārtojot automātam pusgrupu netiek ņemta vērā tā izejas funkcija.

2§. Daļēji definēta pusgrupa.

Dots automāts V=(A,B,Q), kur A={a₁,...,a_n} -ieejas alfabēts, B={b₁,...,b_m} -izejas alfabēts un Q={q₁,...q_k} -stāvokļu kopa.

Daļēji definētus kopas Q attēlojumus sevī sauc par daļējām transformācijām. Lai būtu īsāk, mēs tās sauksim vienkārši par transformācijām. Šo transformāciju veidoto pusgrupu apzīmēsim ar PT_r(Q).

Automāta katram burtu pārim (a_i,b_j) piekārtosim transformāciju

q_s * a_i , ja q_sŗ a_i = b_j

nav definēts , pretējā gadījumā.

q₁ .......... q_k

q¹_ij ......... q^k_ij

g_ij= , kur g^s_ij :=

Šādā veidā mēs panākam, ka arī izejas funkcija iespaido automāta pusgrupu.

Definīcija. Kopu V_g={ g_ij ł i=1,n; j =1,m } sauc par automāta V

transformāciju kopu.

Definīcija. Transformāciju kopas V_g ģenerēto pusgrupas PT_r(Q) apakšpusgrupu

ć V_g ń sauc par automāta V pusgrupu.

Daļēji definēto transformāciju veidotās pusgrupas ir cieši saistītas ar visur definēto transformāciju veidotajām pusgrupām. Šo saistību raksturo sekojošs apgalvojums.

Pieņemsim, ka A={a₁,....,a_n} un a₀ŁA. A₀:={a₀}Ē A.

Apgalvojums. Katrai pusgrupas PT_r(A) apakšpusgrupai S eksistē pusgrupas

T_r(A₀) izomorfa apakšpusgrupa S₀.

Šī apgalvojuma pierādījums dots I.Balodes maģistra darbā.

Secinājumi:

1) Šajā paragrāfā mēs parādījām , ka daļēji definētās transformācijas labāk raksturo automātu nekā visur definētās transformācijas, kuras aplūkotas iepriek-

šējā paragrāfā, jo automātiem arī izejas funkcija iespaido automāta pusgrupu;

2) Savukārt, pēdējais apgalvojums parāda, ka, no pusgrupu teorijas viedokļa, mēs varam aprobežoties ar visur definētām trasformācijām.

2. Nodaļa.

AUTOMĀTU NEATŠĶIRAMĪBA

Definīcija. Automātus sauc par salīdzināmiem, ja tiem ir vienādi ieejas alfabēti.

Doti divi salīdzināmi automāti V=(A,B,Q,*,˚) un V¢=(A¢,B¢,Q¢,Ä,:).

Definīcija. Stāvokļus q un q¢ sauc par neatšķiramiem stāvokļiem, ja katram

vārdam aĻA* izpildās vienādība q˚a=q¢:a.

(Ievadot vienādus vārdus, izejas vārdi arī būs vienādi.)

Definīcija. Stāvokli q sauc par atšķiramu no stāvokļa q¢, ja eksistē tāds vārds aĻA* , ka q˚a ¹ q¢:a. Šajā gadījumā saka, ka stāvokļi q un q¢ atšķirami ar vārdu a vai arī, ka vārds a atšķir stāvokļus q un q¢. Neatšķiramus automāta stāvokļus q un q¢ apzīmē šādi: q~q¢.

Apgalvojums. Attiecība ~ ir ekvivalences tipa predikāts,t.i., izpildās sekojošas

3 īpašības: 1) refleksivitāte;

2) simetrija;

3) transitivitāte.

Definīcija. Automātu V sauc par reducētu automātu, ja šī automāta jebkurš

stāvokļu pāris q un q¢ ir atšķirams.

Definīcija. Pieņemsim, ka TĮA*. Stāvokļus q un q¢ sauc par neatšķiramiem

kopā T, ja “xĻT izpildās q˚a=q¢˚a.

Ērtības labad , lai formulētu sekojošo teorēmu, ievedīsim apzīmējumu: Aⁿ:={aĻA^*ł l(a) = n}. Ar ½Q½ apzīmēsim kopas Q apjomu.

Teorēma. Galīga automāta V=(A,B,Q,*,˚) stāvokļi q un q¢ ir neatšķirami tad un tikai tad, ja tie ir neatšķirami kopā A^ŗQŗ-1.

Šīs teorēmas pierādījums dots [4] grāmatā.

No prakses viedokļa redzēsim, ka pārbaudes procedūra lieliem kopas Q apjomiem praktiski ir grūti veicama.

Apskatīsim divus automātus V= (A,B,Q,*,˚) un V¢= (A,B,Q¢,Ä,:).

Definīcija. Divus automātus sauc par neatšķiramiem pēc iekšējiem stāvokļiem, ja katram viena automāta iekšējam stāvoklim atrodams neatšķirams otra automāta iekšējais stāvoklis. Neatšķiramus automātus apzīmē šādi: V”V¢.

Apgalvojums. Automātu neatšķiramība ir ekvivalences tipa predikāts.

Pierādījums dots grāmatā [4].

Ar K(A,B) apzīmēsim visu to automātu V= (A,B,Q,*,˚ ) klasi, kur Q ir kādas fiksētas sanumurējamas kopas U apakškopa. Pieņemsim, ka VĻK(A,B). Ar K_v(A,B) apzīmēsim visu to automātu V¢ĻK(A,B) kopu, kuriem izpildās nosacījums V”V¢ (automāti ir neatšķirami).

Klasi K_v(A,B) raksturo sekojoša teorēma.

Teorēma. Ja A,B- galīgas netukšas kopas un VĻK(A,B), tad klase K_v(A,B) ar precizitāti līdz izomorfismam satur vienu vienīgu reducētu automātu.

Šīs teorēmas pierādījums dots grāmatā [4].

Definīcija. Automātus V un V¢ sauc par izomorfiem, ja eksistē tādas

bijekcijas:

j₁: Q®Q¢

j₂: A®A¢

j₃: B®B¢ ,ka izpildās sekojoši nosacījumi:

1) j₁(q*a)=j₁(q) Ä j₂(a);

2) j₃(q˚a)=j₁(q) : j₂(a).

Apgalvojums. Izomorfiem automātiem ir izomorfas pusgrupas.

Tālāk skatīt V. Buźas maģistra darbā.

3. nodaļa.

AUTOMĀTU MODELĒŠANA

1.§ Jēdzini un definīcijas.

Definīcija. Saka, ka automāts V¢ modelē automātu V ar attēlojumiem j₁: Q®Q¢, j₂: A®A¢, j₃¢: B¢®B, ja diagramma:

Q ´ A^*¾® B^*

j₁” “ j₂ j₃¢

Q¢´(A¢)^*¾®(B¢)^* ir komutatīva.

Šajā situācijā mēs pieņemam, ka j₂ ir paplašināts kopā A^* ar nosacījumu j₂(ua)=j₂(u)j₂(a), tāpat j₃¢(v¢b¢)=j₃¢(v¢)j₃¢(b¢).

Šajā situācijā lietosim pierakstu V¢ŠV(j₁j₂j₃¢).

Definīcija. Saka, ka V¢ modelē V, ja eksistē tādi attēlojumi j₁, j₂, j₃¢, ka V¢ŠV(j₁j₂j₃¢). Šai situācijā lietosim pierakstu V¢ŠV.

Definīcija. Saka, ka automāti V un V¢ modelē viens otru, ja VŠV¢ un V¢ŠV. Šajā situācijā lietosim pierakstu VŠ×V¢.

Definīcija. Saka, ka automāts V=(A,B,Q) neatšķir ieejas burtus a₁,a₂ĻA, ja “(q,u)ĻQ´A^* izpildās vienādība q˚a₁u=q˚a₂u. Pretējā gadījumā saka, ka automāts V atšķir ieejas burtus a₁, a₂.

Definīcija. Reducētu automātu, kas atšķir visus dažādos ieejas burtus, sauc par

īpaši reducētu automātu.

Lemma. Reducēts automāts V=(A,B,Q) nav īpaši reducēts tad un tikai tad, ja $ (a₁,a₂)ĻA´A ,ka [ a₁¹a₂ Ś “qĻQ ( q*a₁=q*a₂Ś q˚a₁=q˚a₂)].

Definīcija. Teiksim, ka automāts V’= (A’, B’, Q’, ·, Ä )

modelē automāta V’= (A, B, Q, ŗ, * ) stāvokli q Ī Q , ja eksistē

tāds automāta V’stāvoklis q’ Ī Q’ un attēlojumi j₃’: ( B’)^* ® B^*,

j₂: A^* ® ( A’ )^* , ka katram a Ī A^* q ŗ a = j₃’(q’ · j₂( a ))

Pretējā gadījumā teiksim, ka automāts V’ nemodelē automāta V stāvokli q.

Kā sekas no iepriekšējās definīcijas iegūstm šādu

apgalvojumu: Ja automāts V’ nemodelē kādu automāta V stāvokli q, tad

automāts V’ nemodelē automātu V.

2§. _{........................................................}

V. Bužas 1996. gada maģistra darbā nesalīdzināmie automāti sastāv no četriem stāvokļiem, ieejas alfabēts satur trīs un izejas alfabēts divus burtus.

Radās iespaids, ka automāti, kuriem vienādas pusgrupas un tie satur tikai divus ieejas burtus, varētu būt attiecībā pret modelēšanu ekvivalenti.

Apskatām divus automātus, kuriem mazāks ieejas un izejas burtu skaits un tikai divi stāvokļi. Kā redzēsim, tad arī šajā gadījumā automāti ir īpaši reducēti , to pusgrupas ir vienādas, bet tie viens otru nemodelē.

( # ) Ar automāta grafu sapratīsim automāta shematisko zīmējumu, kurā ar aplīšiem attēloti automāta stāvokļi, ar bultiņām norādītas pārejas, alfabēta burti a un b ar indeksiem norāda pie kādas to kombinācijām notiek pāreja.

Piemērs Nr. 1

Apskatam automātus V un V', kuriem A ={ a₁ a₂ } B={b₁ b₂ } un Q= {q₁ q₂ }.

Automāts V. Automāts V’.

a₁

b₂

q₁ q₂

a₂ a₂

b₁ b₂

a₁

b₁

a₂

b₁

q₁ q₂

a₁ a₂

b₂ b₂

a₁

b₁

Pierādīsim, ka šiem automātiem pusgrupas ir vienādas, t. i. _g> = g>.

Konstruēsim daļēji definētas transformācijas, kas ir atbilstošās pusgrupas veidotājelementi.

Ērtības labad turpmāk vienkāršosim pierakstu- pārbaudot pusgrupu veidotāj elementus sapratīsim, ka pārbaudam katra stāvokļa reakciju uz visām iespējamām ieejas un izejas burtu kombinācijām.

Arī “prim” zīmes pie stāvokļu, ieejas un izejas alfabēta burtiem un stāvokļiem

nelietosim, ja nerodas pārpratumu, ka apskatam automātu V’.

Pusgrupas noteikšanas procesā izmantojamo apzīmējumu skaidrojums:

automāta stāvokļi, kuros

ievadam a₁,

a₁ 1 2

b₁ - 1

stāvokļi uz kuriem pāriet automāts

simbols " - " nozīmē, ka pie situācijas, kad ieejā ir a₁ un izejā b₁.

stāvoklī q₁ automātam vainu nav

definēti burti a₁ un b₁, vai arī, ja ir definēti,

tad stāvoklī uz burtu a₁ automāts neizdod b₁.

Pieraksts nozīmē, ka apskatam automāta stāvokļus q₁ un q₂ ar ieejas burtu a₁ un izejas burtu b₁ , redzams, ka stāvoklim q₁ ieejas burts a₁ nav definēts- viņš uz tu nereaģē, bet ja a₁ ievada astāvoklī q₂, tad automāts pāriet uz stāvokli q₁ .

( i ) Apskatāmo automātu atbilstošo pusgrupu veidotājelementi visām

iespējamām ieejas un izejas burtu kombinācijām.

Automātam V : Automātam V’:

a₁ 1 2 a₁ 1 2

b₁ - 1 b₁ - 1

a₁ 1 2 a₁ 1 2

b₂ 2 - b₂ 1 -

a₂ 1 2 a₂ 1 2

b₁ 1 - b₁ 2 -

a₂ 1 2 a₂ 1 2

b₂ - 2 b₂ - 2

Automāta V transformāciju kopa visām dāžādām ieejas un izejas burtu

kombinācijām- V_q= { q1 b₁> q1b₂> q2b₁> q2b₂>}

Automāta V’transformācijas kopa V’_q={ q1 b₁> q1b₂> q2b₁> q2b₂>}

Salīdzinot transformācijas atbilstoši V un V‘ mēs redzam, ka

q1 b₁> = q1 b₁> q1 b₂> = q2 b₁>

q2 b₁> = q1 b₂> q2 b₂> = q2 b₂> tātad V_q= V’_q ,

Tas nozīmē, ka abiem automātiem pusgrupu veidojošās transformācijas ir vienādas.

Tas savukārt nozīmē, ka atbilstošās pusgrupas ir vienādas, t. i. _q> = q>.

( ii ) Tagad pierādīsim, ka automāti V un V’ir reducēti.

1) lai pierādītu, ka automāts V ir reducēts automāts- ir jāpierāda, ka jebkuri

divi stāvokļi šajā automātā ir atšķirami.

Tā kā automāta V stāvokļu kopas apjoms ir divi, tad jāparāda tikai, ka

stāvoklis q₁ ir atšķirams no stāvokļa q₂ .

q₁

a₁ = b₂ ¹ b₁ = q₂

a₁

2) līdzīgi parādīsim, ka automāts V’ arī ir reducēts automāts,

q₁

a₁ = b₂ ¹ b₁ = q₂

a₁

(iii) Tagad pierādīsim, ka abi automāti ir īpaši reducēti .

Abiem automātiem alfabēts sastāv no diviem burtiem A={a₁ a₂ } A’={a₁ a₂ }.

Mums jāparāda, ka abi automāti atšķir šos burtus.

1)Apskatīsim automātu V un parādīsim, ka tas atšķir burtus a₁ un a₂.

q₁

a₁ = b₂ ¹ b₁ = q₁

a₂

Tātad šis ir īpaši reducēts automāts.

2) Apskatīsim automātu V’ un parādīsim, ka tas atšķir burtus a₁ un a₂.

q₁

a₁ = b₂ ¹ b₁ = q₁

a₂

Arī šis automāts atšķir visus ieejas burtus, kas arī ļauj konstatēt, ka V’ ir īpaši reducēts automāts.

( iv ) Tagad pierādīsim, ka automāts V nemodelē automātu V’, t. i. V ćV’

Pieņemsim pretējo, proti, ka V ć V’, tad eksistē tādi attēlojumi j₁, j₂, j_3,

ka diagramma Q’ 5 (A’)^* ® (B’)^*

j₁Æ Æj₂ j‘₃

Q 5 A^* ® B^* ir komutatīva.

Tā kā abi alfabēti B un B’ sastāv no diviem burtiem un attēlojumi Q 5A ·® B un Q’ 5A’ ŗ® B’ ir sirjekcijas, tad arī attēlojums j₃’ ir sirjekcija ( diagramma taču ir komutatīva). No tā seko, ka j₃ ir bijekcija, jo abiem automātiem izejas alfabētu apjomi ir vienādi un to elementu skaits ir galīgs.

Tāpēc diagramma: Q’ 5 (A’)^* •® ( B’)^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q 5 A^* ŗ® B^*

ir komutatīva.

Ņemsim vērā, ka j₃= ( j₃’)^-1, t. i. j₃ ir attēlojuma j₃’ inversais attēlojums.

Tā rezultātā arī j₃ ir bijekcija.

Tagad pievērsīsimies attēlojumam j₂ .

Pierādīsim, ka j₂ ir injekcija. Ja tas tā nebūtu , tad j₂( a₁’ ) = j₂( a₂’ )

Pievēršamies komutatīvai diagrammai ( 1 ) un automāta grafam ( # ) .

No šejienes

j₃ (b₁’) = j₃ (q₁· a₂’) = j₁(q₁) ° j₂(a₂’) = j₁(q₁) ° j₂(a₁’) = j₃(q₁· a₁’) = j₃(b₂’)

Tā ir pretruna, jo j₃ ir bijekcija.

Visbeidzot analizēsim attēlojumu j₁.

Lai pierādītu, ka V nemodelē V’ mums pietiek uzrādīt vismaz vienu stāvokli automātā V un parādīt, ka nevar atrast starp automāta V’ stāvokļiem tādu kurā ievadot kādu vārdu, tas izdotu ārā tādu pašu vārdu, kā automāts V. Tikai jāņem vērā, ka jāapskata arī visas iespējamās ieejas burtu atbilstību kombinācijas.

Pieņemam, ka automāts V modelē automātu V’.

Mēs izvēlamies automāta V’ stāvokli q₁’ un piemeklējam tādu vārdu, kuru ievadot automāta V visos stāvokļos pēc kārtas ,varam parādīt, ka vienam un tam pašam ieejas burtam atbilst dažādi izejas burti, kas norāda, ka j₁ nav bijekcija. Bet iepriekš esam noskaidrojuši, ka j₁ ir bijekcija. Nonākam pie pretrunas, kura liek secināt, ka pieņēmums, ka V modelē V’ bijis kļūdains. Tātad.

1) Pieņemsim, ka j₁( q₁’) = q₁

j₃( b₁’b₂’ ) = j₃( q₁’· a₂’a₂’ ) = j₁( q₁’) q j₂(a₂’a₂’) = q₁q j₂(a₂’a₂’)

a) j₂( a₂’) = a₁ . Šai situācijā j₃(b₁’b₂’) = q₁q a₁a₁ = b₂b₁

Tātad j₃( b₁’ ) = b₂ un b₁ = j₃( b₂’ ).

Tagad apskatisim kaut ko citu, proti,

j₃( b₁’b₂’b₂’ ) = j₃( q₁’· a₂‘a₂’a₂’) = j₁( q₁) q j₂(a₂‘a₂’ a₂’) =

= q₁q a₁‘a₁’a₁’= b₂’b₁’b₂’ .

No šejienes j₃(b₂’) = b₂. Pretruna, jo mēs konstatējām, ka j₃( b₂’ ) = b₁.

Līdz ar to j₂( a₂’) ¹ a₁.

b) j₂(a₂’) = a₂ . Šai situācijā j₃( b'₁ b'₂ ) = q₁q a₂ a₂= b₁b₁ .

Pretruna, jo sanāk, ka j₃( b₁ ) = b₁ un j₃( b₂ ) = b₁ ,

Tātad j₁( q₁’) ¹ q₁

2) Pieņemsim, ka j₁( q₁’) = q₂, tad

j₃( b₁’b₂’ ) = j₃( q₁’· a₂’a₂’ ) = j₁( q₁’) q j₂(a₂’a₂’) = q₂q j₂(a₂’a₂’)

a) Ja j₂( a₂’) = a₁. Šai situācijā j₃( b₁b₂) = q₂q a₁a₁ = b₁b₂

Tagad apskatīsim kaut ko citu, proti,

j₃( b₁’b₂’b₂’ ) = j₃( q₁’· a₂‘a₂’a₂’) = j₁( q₁’) q j₂(a₂‘a₂’ a₂’) =

= q'₁q a₁a₁a₁= b₁b₂b₁ .

No šejienes j₃( b₂’) = b₂ un j₃( b₂’ ) = b₁ . Pretruna!

Līdz ar to j₂( a₂’) ¹ a₁ .

b) Ja j₂(a₂’) = a₂ . Šajā situācijā j₃( b₁’b₂’ ) = q₂q a₂a₂ = b₂b₂.

Pretruna! Jo sanāk, ka j₃( b₁’ ) = b₂ ¹ b₂= j₃( b₂’ )

Tātad j₁( q₁’) ¹ q₂.

Esam konstatējuši, ka j₁( q₁) Ļ { q₁,q₂}.

Tas tā nevar būt, jo j₁ ir visur definēts attēlojums ar vērtību kopu

Q={q₁,q₂}.

Atliek secināt, ka pieņēmums V ć V’ ir bijis kļūdains.

( v ) Tagad parādīsim, ka automāts V’ nemodelē automātu V, t. i., V’ćV.

Līdzīgi, kā ( iv ) pieņemsim pretējo, proti, ka V’ćV,, tad eksistē tādi

attēlojumi j₁,j₂,j₃, ka

diagramma:

Q 5 A^* ŗ® B^*

j₁Æ Æj₂ j₃’

Q’ 5 (A’)^* •® (B’)^* ir komutatīva.

Rīkojoties analogi kā ( iv ) gadījumā secinām, ka diagramma:

Q 5 A^* ŗ® B^*

j₁Æ Æj₂ Æj₃ ( 2 )

Q’ 5 (A’)^*•® (B’)^* ir komutatīva,

attēlojums j₃ ir bijekcija un j₃=(j₃’)^-1, t.i. j₃ir attēlojuma j₃’inversais

attēlojums.

Tagad pievērsīsimies attēlojumam j₂. Parādīsim, ka j₂ ir injekcija.

Ja tas tā nebūtu, tad j₂( a₂ ) = j₂( a₁ ).

Pievēršamies komutatīvai diagrammai ( 2 ) . No šejienes

j₃( b₁) = j₃( q₁q a₂) = j₁( q₁) · j₂( a₂ ) = j₁( q₁) · j₂( a₁ ) =

= j₃( q₁q a₁ ) = j₃( b₂ )

Pretruna! Jo j₃ ir bijekcija.

Visbeidzot pievērsīsimies attēlojumam j₁.

1) Pieņemsim, ka j₁(q₁) = q₁’ , tad

j₃( b₂ b₁) = j₃( q₁q a₁a₁) = j₁( q₁) · j₂( a₁a₁ ) = q₁’· j₂( a'₁a'₁)

a) ja j₂(a₁) = a₁’ j₃( b₂b₁ )= q₁’· a₁’a₁’ = b₂’b₂’

Pretruna, jo sanāk, ka j₃( b₂ ) = b₂’ un j₃( b₁ ) = b₂’

b) ja j₂(a₁)=a₂’ j₃( b₂ b₁ )= q₁’· a₂’a₂’ =b₁’b₂’,

tātad j₃( b₂ ) = b₁’ un j₃( b₁ ) = b₂’

Apskatot citu gadījumu iegūstam-

j₃( b₂ b₁ b₂) = j₃( q₁q a₁a₁a₁) = j₁( q₁) · j₂( a₁a₁a₁) =

=q₁’· j₂( a₂’a₂’a₂’)= b₁’b₂’b₂’.

Tas nozīmē, ka j₃( b₂ ) = b₁’ un j₃( b₂ ) = b₂’ Pretruna!

2) Pieņemsim, ka j₁( q₁) = q₂’, tad

j₃( b₁ b₂) = j₃( q₁q a₂a₁) = j₁( q₁) · j₂( a₂a₁ ) = q₂’· j₂( a'₂a'₁)

a) ja j₂(a₁) = a₁’ ,tad j₃( b₁b₂ )= q₂‘· a₂’a₁’ = b₂’b₁’

un sanāk, ka j₃( b₁ ) = b₂’ un j₃( b₂ ) = b₁’ tādā gadījumā

j₃( b₂’b₁’b₂’) = j₃( q₁’· a₁’a₁’a₁’) = j₁( q₁) q j₂(a₁‘a₁’a₁’) =

= q₂’· a₁‘a₁’a₁’= b₁’b₂’b₂’

un j₃( b₂ ) = b₁’ un j₃( b₂ ) = b₂’ Pretruna!

b) ja j₂( a₁) = a₂’ ,tad j₃( b₁b₂ )= q₂’· a₁’a₂’ = b₁’b₁’ sanāk

ka j₃( b₁ ) = b₁’ un j₃( b₂ ) = b₁’ , bet tā ir pretruna, jo j₃ ir bijekcija!

Esam pierādījuši, ka automāti V un V’viens otru nemodelē!

Salīdzinot ar V. Bužas maģistra darbu mēs šai situācijā pierādījām, ka ieejas un izejas alfabēts var saturēt tikai divus burtus un stāvokļu kopa arī saturēt tikai divus stāvokļus.

Lai labāk izprastu uzkonstruēto automātu darbību, mēģināsim vērot, kā tie

“ uzvedās” pie dažāda ieejas un izejas alfabēta burtu skaita, saglabājot par bāzi pirmo divu stāvokļu konfigurāciju un mēģinot pielikt, ja nepieciešams, klāt stāvokļus tā, lai izpildītos mūsu uzstdīta prasība- automātu pusgrupas būtu vienādas, bet tie viens otru nemodelētu.

Kā vēlāk redzēsim, visos šajos gadījumos mums izdodas uzkonstruēt automātus ar vienādām pusgrupām, kas viens otru nemodelē. Piedevām visi automāti ir īpaši reducēti.

Piemērs Nr. 2

Apskatīsim piemēru ar automātiem V un V’ ,

kuriem A={ a₁, a₂ } un B ={b₁, b₂, b₃, b₄}

Automāts V.

a₁

b₂

q₁ q₂ q₃ q₄

a₂ a₂ a₁a₂ a₁a₂

b₁ b₂ b₃b₃ b₄b₄

a₁

b₁

Automāts V’.

a₂

b₁

q₁ q₂ q₃ q₄

a₁ a₂ a₁a₂ a₁a₂

b₂ b₂ b₃b₃ b₄b₄

a₁

b₁

Pārbaudam vai abiem automātiem sakrīt pusgrupas t. i. _g> = g>.

Automātam V, automātam V’.

a₁ 1 2 3 4 a₁ 1 2 3 4

b₁ - 1 4 4 b₁ - 1 4 4

a₂ 1 2 3 4 a₂ 1 2 3 4

b₁ 1 - - - b₁ 2 - - -

a₃ 1 2 3 4 a₃ 1 2 3 4

b₁ 1 - 4 - b₁ 1 - 4 -

a₁ 1 2 3 4 a₁ 1 2 3 4

b₂ 2 - - - b₂ 1 - - -

a₂ 1 2 3 4 a₂ 1 2 3 4

b₂ - 2 2 4 b₂ - 2 2 4

a₃ 1 2 3 4 a₃ 1 2 3 4

b₂ - 2 - 4 b₂ - 2 - 4

Konstatējam, ka automātiem atbilstošās pusgrupas ir vienādas.

( ii ) Apskatam vai automāti V un V’ ir reducēti, tas ir-

vai tie atšķir visus stāvokļus.

Automāts V , automāts V’

q₁ un q₂ q₁q a₁ = b₂ q₁q a₁ = b₂

q₂q a₁ = b₁ q₂q a₁ = b₁

q₁ un q₃ q₁q a₁ = b₂ q₁q a₁ = b₂

q₃q a₂ = b₃ q₃q a₁ = b₁

q₂ un q₃ q₂q a₃ = b₂ q₂q a₃ = b₂

q₃q a₃ = b₁ q₃q a₃ = b₁

q₁ un q₄ q₁q a₂ = b₁ q₁q a₂ = b₁

q₄q a₂ = b₂ q₄q a₂ = b₂

q₂ un q₄ q₂q a₁a₁ = b₁b₂ q₂q a₁a₁ = b₁b₂

q₄q a₁a₁ = b₁b₁ q₃q a₁a₁ = b₁b₁

q₃ un q₄ q₃q a₃ = b₁ q₃q a₂ = b₁

q₄q a₃ = b₂ q₄q a₂ = b₂

Automāti ir reducēti.

( iii ) Pārbaudam vai abi automāti atšķir visus ieejas burtus,

tas ir vai tie ir īpaši reducēti.

Automāts V, automāts V’.

a₁ un a₂ q₃q a₁ = b₁ q₁q a₁ = b₁

q₃q a₂ = b₂ q₁q a₂ = b₂

a₁ un a₃ q₄q a₁ = b₁ q₄q a₁ = b₁

q₄q a₃ = b₂ q₄q a₃ = b₂

a₂ un a₃ q₃q a₂ = b₂ q₃q a₂ = b₂

q₃q a₃ = b₁ q₃q a₃ = b₁

Nosacījums izpildās- tātad abi automāti ir īpaši reducēti.

( iv ) Apskata vai automāti V un V’ nemodelē viens otru.

1. Apskata gadījumu vai V nemodelē V’.

Lai to pierādītu pietiek pierādīt, ka automāts V nemodelē V’ stāvokli q₁ .

Pieņem pretējo, ka V modelē V’ , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q' 5 ( A’)^* ·® ( B’)^*

j₁Æ Æj₂ j'₃

Q 5 A^* q® B^* ir komutatīva.

Tā kā alfabēts B sastāv no diviem burtiem un attēlojums Q’ 5 A’ ·® B’

ir sirjekcija, tad arī attēlojums j₃’ ir sirjekcija ( diagramma taču ir komutatīva ).

No tā seko, ka j₃ ir bijekcija, jo abiem automātiem, taču alfābēti ir vienādi un to elementu skaits ir galīgs.

Tāpēc diagramma :

Q' 5 (A’)^* ·® (B’)^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q 5 A^* q® B^* ir komutatīva.

Ņemot vērā, ka j₃= ( j₃’ )^-1 ,tas ir, j₃ ir attēlojuma j₃’ inversais attēlojums,

secinām: j₃ ir bijekcija.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂(a’₁) = j₂(a’₂) 2) j₂(a’₁) = j₂(a’₃) 3) j₂(a’₂) = j₂(a’₃)

1) j₂(a’₁) ¹ j₂(a’₂), pretējā gadījumā j₂(a’₁) = j₂(a’₂), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₂) = j₃( q’₁· a’₂ ) = j₃( b’₁)

2) j₂(a’₁) ¹ j₂(a’₃), pretējā gadījumā j₂(a’₁) = j₂(a’₃), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₃) = j₃( q’₁· a’₃ ) = j₃( b’₁)

3) j₂(a’₂) ¹ j₂(a’₃), pretējā gadījumā j₂(a’₂) = j₂(a’₃), tad

j₃( b’₁ b’₁ ) = j₃( q’₁· a’₃ a’₂ ) = j₁( q’₁) q j₂( a’₃) j₂( a’₂) =

= j₁( q’₁)q j₂( a’₂) j₂( a’₂)= j₃( q’₁· a’₂ a’₂ ) = j₃( b’₁ b’₂ )

Visos trijos gadījumos mēs iegūstam pretrunas, jo mēs jau esam konstatējuši, ka j₃ ir bijekcija, tāpēc vienādība j₃( b’₂) = j₃( b’₁), visos gadījumos ir pretrunā ar faktu, ka j₃ ir bijekcija.

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V’ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

Ja sīkāk nav paskaidrots, tad secinājumi izdarīti skatoties automātu diagrammas un automātu shematiskos zīmējumus.

1) pieņem, ka j₁(q₁’) = q₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₂ b₁= j₃( b’₂b’₁ ) = j₃( q’₁· a’₁a’₂) = j₁( q’₁) q j₂(a’₁a’₂) =

= q’₁q j₂( a’₁) j₂( a₂’)

No automāta grafa redzam, ka q₁q j₂( a’₁) = b₂ - secinām, ka tas var būt tikai gadījumā, kad j₂(a’₁) = a₁ . Tā rezultātā automāts pāries uz stāvokli q₂ t.i. q₁* a₁ =q₂. Bet no stāvokļa q₂ , lai izejā iegūtu b₁, vajag ievadīt burtu a₁, un no mūsu augstāk apskatītās izteiksmes redzam, ka j₂(a’₂) = a₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b’₂) = b₁

j₃(b’₁) = b₂

b₂ b₁= j₃( b’₁b’₂ ) = j₃( q’₁· a’₂a’₁) = j₁( q’₁) q j₂(a’₂a’₁) =

= q’₁q j₂( a’₂) j₂( a₁’). ( 1 )

Secinājumus izdaram līdzīgi, kā iepriekšējā punktā.

No iegūtās izteiksmes iegūstam, ka b₂ = q’₁q j₂( a’₂).

Tas iespējams tikai vienā situācijā, ja j₂( a’₂) = a₁ .

Tātad q₁* j₂( a’₂) = q₁* a₁ =q₂ , tāpēc q₂q j₂( a’₁) = b₁

Tas iespējams tikai situācijā, ja j₂( a’₁) = a₁ .

Pretruna, jo sanāk- j₂( a’₂) = a₁ = j₂( a’₁)

2) pieņem, ka j₁(q₁’) = q₂ . Secinām j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₁b₂b₁= j₃( b’₁b’₂b’₁ ) = j₃( q’₁· a’₂a’₂a’₁) = q₂ q j₂(a’₂) j₂(a’₂) j₂(a’₁) , tas var iznākt tikai, ja: j₂(a’₂) = a₁ , j₂(a’₂) = a₁ , j₂(a’₁) = a₁ , bet j₂ ir bijekcija, tātad vienam un tam pašam attēlojumam nevar atbilst divas dažādas vērtības , jo j₃ ir bijekcija.

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

b₁b₂b₁= j₃( b’₂b’₁b’₂ ) = j₃( q’₁· a’₁a’₂a’₂) = q₂ q j₂(a’₁) j₂(a’₂) j₂(a’₂) , tas var iznākt tikai, ja: j₂(a’₁) = a₁ , j₂(a’₂) = a₁ , j₂(a’₂) = a₁ , atkal pretruna!

3) pieņem, ka j₁(q₁’) = q₃ . Atkal izmantojam to, ka j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₁b₂b₁= j₃( b’₁b’₂b’₁ ) = j₃( q’₁· a’₂a’₂a’₁) = q₃ q j₂(a’₂) j₂(a’₂) j₂(a’₁) , tas var iznākt tikai, ja: j₂(a’₂) = a₁ , j₂(a’₂) = a₃ , j₂(a’₁) = a₁ , pretruna!

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

b₁b₂b₁= j₃( b’₂b’₁b’₂ ) = j₃( q’₁· a’₂a’₂a’₁) = q₃ q j₂(a’₂) j₂(a’₂) j₂(a’₁) , tas var iznākt tikai, ja: j₂(a’₂) = a₁ , j₂(a’₂) = a₃ , j₂(a’₁) = a₁ , atkal pretruna!

Esam secinājuši, ka pieņāmumi: j₁(q₁’) = q₁

j₁(q₁’) = q₂

j₁(q₁’) = q₃

bijuši maldīgi un mēs nevarējām starp visiem automāta V stāvokļiem atrast tādu, kurš spētu modelēt, automāta V’ stāvokli q₁. Ja jau nevar nomodelēt vienu stāvokli, tad nevar nomodelēt arī visu automātu.

Tātad automāts V nemodelē automātu V’.

2. Apskata gadījumu vai V’ nemodelē V.

Lai to pierādītu rīkojamies līdzīgi, kā pirmajā punktā ( pierādot, ka V

nemodelē V’) pietiek pierādīt, ka automāts V’ nemodelē V stāvokli q₁ .

Pieņem pretējo, ka V’ modelē V , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q 5 A^* q® B^*

j₁Æ Æj₂ j₃’

Q’ 5 ( A’)^* ·® ( B’)^* ir komutatīva.

Rīkojoties analogi kā ( iv ) gadījumā secinām, ka diagramma:

Q 5 A^* q® B^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q’ 5 (A’)^* ·® (B’)^* ir komutatīva,

attēlojums j₃ ir bijekcija un j₃= (j₃’)^-1, t.i.

j₃ir attēlojuma j₃’ inversais attēlojums.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂(a₁) = j₂(a₂) 2) j₂(a₁) = j₂(a₃) 3) j₂(a₂) = j₂(a₃)

1) j₂(a₁) ¹ j₂(a₂), pretējā gadījumā j₂(a₁) = j₂(a₂), tad

j₃( b₂ ) = j₃( q₁ q a₁) = j₁( q₁) • j₂( a₁) =

= j₁( q₁)• j₂( a₂) = j₃( q₁• a₂ ) = j₃( b₁)

2) j₂(a₁) ¹ j₂(a₃), pretējā gadījumā j₂(a₁) = j₂(a₃), tad

j₃( b₂ ) = j₃( q₁ qa₁) = j₁( q₁) • j₂( a₁) =

= j₁( q₁)• j₂( a₃) = j₃( q₁• a₃ ) = j₃( b₁)

3) j₂(a₂) ¹ j₂(a₃), pretējā gadījumā j₂(a₂) = j₂(a₃), tad

j₃( b₂ ) = j₃( q₃ q a₂ ) = j₁( q₃) •j₂( a₂) =

= j₁( q₃)• j₂( a₃) = j₃( q₃• a₃ ) = j₃( b₁)

Visos trijos gadījumos mēs iegūstam pretrunas, jo mēs jau esam konstatējuši, ka j₃ ir bijekcija, tāpēc vienādība j₃( b₂) = j₃( b₁), visos gadījumos ir pretrunā ar faktu, ka j₃ ir bijekcija.

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

1) pieņem, ka j₁(q₁) = q’₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b₁) = b’₁

j₃(b₂) = b’₂

b’₂ b’₁= j₃( b₂b₁ ) = j₃( q₁q a₁a₂) = j₁( q₁) Ÿ j₂(a₁a₂) = q₁Ÿ j₂( a₁) j₂( a₂)

No q₁Ÿ j₂( a₁) = b’₂ secinām, ka j₂(a₁) = a’₁ . Tā rezultātā q₁* a’₁ = q₂.

Sakarā ar to, ka vajag, lai q₂q j₂( a’₂) = b₁, iegūstam j₂(a’₂) = a₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b₂) = b’₁

j₃(b₁) = b’₂

b’₂ b’₁= j₃( b₁b₂ ) = j₃( q₁q a₂a₁) = j₁( q₁) Ÿ j₂(a₂a₁) = q’₁Ÿ j₂( a₂) j₂( a₁) (1)

No šejienes b’₂ = q₁q j₂( a₂). Tas iespējams tikai vienā situācijā, ja

j₂( a₂) = a’₁ . Tātad q’₁* j₂( a’₂) = q’₁* a’₁ =q’₂ , tāpēc q’₂q j₂( a₁) = b’₁

( skatīt vienādību ( 1 ) ). Tas iespējams tikai situācijā, ja j₂( a₁) = a’₁ .

Pretruna, jo j₂( a₂) = a’₁ = j₂( a₁)

2) pieņem, ka j₁(q₁) = q’₂ . Secinām j₃{b₂ ; b₁} = {b’₁ ; b’₂}

Apskatam pirmo apakšgadījumu: j₃(b₁) = b’₁

j₃(b₂) = b’₂

b’₁b’₂b’₁= j₃( b₁b₂b₁ ) = j₃( q₁· a₂a₂a₁) = q’₂ q j₂(a₂) j₂(a₂) j₂(a₁) , tas var iznākt tikai, ja: j₂(a₂) = a’₁ , j₂(a₂) = a’₁ , j₂(a₁) = a’₁ , bet j₂ ir bijekcija, tātad vienam un tam pašam attēlojumam nevar atbilst divas dažādas vērtības un otrādi.

Apskatam otro apakšgadījumu: j₃(b₁) = b’₂

j₃(b₂) = b’₁ , tad

b’₁b’₂b’₁= j₃( b₂b₁b₂ ) = j₃( q₁· a₁a₂a₂) = q’₂ q j₂(a₁) j₂(a₂) j₂(a₂) , tas var iznākt tikai, ja: j₂(a₁) = a’₁ , j₂(a₂) = a’₁ , j₂(a₂) = a’₁ , atkal pretruna!

3) pieņem, ka j₁(q₁) = q’₃ . Atkal izmantojam to, ka j₃{b₂ ; b₁} = {b’₁ ; b’₂}

Apskatam pirmo apakšgadījumu: j₃(b₁) = b’₁

j₃(b₂) = b’₂

b’₁b’₂b’₁= j₃( b₁b₂b₁ ) = j₃( q₁· a₂a₂a₁) = q’₃ q j₂(a₂) j₂(a₂) j₂(a₁) , tas var iznākt tikai, ja: j₂(a₂) = a’₁ , j₂(a₂) = a’₂ , j₂(a₁) = a’₁ , pretruna!

Apskatam otro apakšgadījumu: j₃(b ₁) = b’₂

j₃(b ₂) = b’₁ , tad

b’₁b’₂b’₁= j₃( b₂b₁b₂ ) = j₃( q₁· a₂a₂a₁) = q’₃ q j₂(a₂) j₂(a₂) j₂(a₁) , tas var iznākt tikai, ja: j₂(a₂) = a’₁ , j₂(a₂) = a’₂ , j₂(a₁) = a’₁ , atkal pretruna!

Esam secinājuši, ka pieņēmumi: j₁(q₁) = q’₁

j₁(q₁) = q’₂

j₁(q₁) = q’₃

j₁(q₁) = q’₄

bijuši maldīgi un mēs nevarējām starp visiem automāta V’ stāvokļiem atrast tādu, kurš spētu modelēt, automāta V stāvokli q₁. Ja jau nevar nomodelēt vienu stāvokli, tad nevar nomodelēt arī visu automātu.

Tātad automāts V’ arī nemodelē automātu V.

Secinājums: automāti V un V’viens otru nemodelē!

Piemērs Nr. 3

Nākošajā piemērā apskatām automātus V un V’,kuriem ir palielināts ieejas alfabēta burtu skaits.

A={ a₁, a₂, a₃ } un B = { b₁, b₂,}

a₁ Automāts V.

b₂

q₁ q₂ q₃

a₂a₃ a₂ a₃ a₁a₂ a₃

b₁b₁ b₂ b₂ b₁b₁ b₂

a₁

b₁

a₂ Automāts V’.

b₁

q₁ q₂ q₃

a₁a₃ a₂a₃ a₁a₂a₃

b₂b₁ b₂b₂ b₁b₁b₂

a₁

b₁

( i ) Pārbaudam vai abiem automātiem sakrīt pusgrupas t. i. _g> = g>.

Automātam V, automātam V’.

a₁ 1 2 3 a₁ 1 2 3

b₁ - 1 3 b₁ - 1 3

a₂ 1 2 3 a₂ 1 2 3

b₁ 1 - 3 b₁ 2 - 3

a₃ 1 2 3 a₃ 1 2 3

b₁ 1 - - b₁ 1 - -

a₁ 1 2 3 a₁ 1 2 3

b₂ 2 - - b₂ 1 - -

a₂ 1 2 3 a₂ 1 2 3

b₂ - 2 - b₂ - 2 -

a₃ 1 2 3 a₃ 1 2 3

b₂ - 2 3 b₂ - 2 3

Konstatējam, ka automātiem atbilstošās pusgrupas ir vienādas.

( ii ) Apskatam vai automāti V un V’ ir reducēti, tas ir

vai tie atšķir visus stāvokļus.

Automāts V , automāts V’

q₁ un q₂ q₁q a₁ = b₂ q₁q a₁ = b₂

q₂q a₁ = b₁ q₂q a₁ = b₁

q₁ un q₃ q₁q a₁ = b₂ q₁q a₁ = b₂

q₃q a₂ = b₁ q₃q a₁ = b₁

q₂ un q₃ q₂q a₂ = b₂ q₂q a₂ = b₂

q₃q a₂ = b₁ q₃q a₂ = b₁

Automāti ir reducēti.

( iii ) Pārbaudam vai abi automāti atšķir visus ieejas burtus,

tas ir vai tie ir īpaši reducēti.

Automāts V, automāts V’.

a₁ un a₂ q₁q a₁ = b₂ q₁q a₁ = b₂

q₁q a₂ = b₁ q₁q a₂ = b₁

a₁ un a₃ q₃q a₁ = b₁ q₃q a₁ = b₁

q₃q a₃ = b₂ q₃q a₃ = b₂

a₂ un a₃ q₃q a₂ = b₁ q₃q a₂ = b₁

q₃q a₃ = b₂ q₃q a₃ = b₂

Nosacījums izpildās- tātad abi automāti ir īpaši reducēti.

( iv ) Apskata vai automāti V un V’ nemodelē viens otru.

1. Apskata gadījumu vai V nemodelē V’.

Lai to pierādītu pietiek pierādīt, ka automāts V nemodelē V’ stāvokli q₁ .

Pieņem pretējo, ka V modelē V’ , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q' 5 ( A’)^* ·® ( B’)^*

j₁Æ Æj₂ j'₃

Q 5 A^* q® B^* ir komutatīva.

Tā kā alfabēts B sastāv no diviem burtiem un attēlojums Q’ 5 A’ ·® B’

ir sirjekcija, tad arī attēlojums j₃’ ir sirjekcija ( diagramma taču ir komutatīva ).

No tā seko, ka j₃ ir bijekcija, jo abiem automātiem, taču alfābēti ir vienādi un to elementu skaits ir galīgs.

Tāpēc diagramma :

Q' 5 (A’)^* ·® (B’)^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q 5 A^* q® B^* ir komutatīva.

Ņemot vērā, ka j₃= ( j₃’ )^-1 ,tas ir, j₃ ir attēlojuma j₃’ inversais attēlojums,

secinām: j₃ ir bijekcija.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂(a’₁) = j₂(a’₂) 2) j₂(a’₁) = j₂(a’₃) 3) j₂(a’₂) = j₂(a’₃)

1) j₂(a’₁) ¹ j₂(a’₂), pretējā gadījumā j₂(a’₁) = j₂(a’₂), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₂) = j₃( q’₁· a’₂ ) = j₃( b’₁)

2) j₂(a’₁) ¹ j₂(a’₃), pretējā gadījumā j₂(a’₁) = j₂(a’₃), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₃) = j₃( q’₁· a’₃ ) = j₃( b’₁)

3) j₂(a’₂) ¹ j₂(a’₃), pretējā gadījumā j₂(a’₂) = j₂(a’₃), tad

j₃( b’₁ b’₁ ) = j₃( q’₁· a’₃ a’₂ ) = j₁( q’₁) q j₂( a’₃) j₂( a’₂) =

= j₁( q’₁)q j₂( a’₂) j₂( a’₂)= j₃( q’₁· a’₂ a’₂ ) = j₃( b’₁ b’₂ )

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V’ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

Ja sīkāk nav paskaidrots, tad secinājumi izdarīti skatoties automātu diagrammas un automātu shematiskos zīmējumus.

1) pieņem, ka j₁(q₁’) = q₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₂ b₁= j₃( b’₂b’₁ ) = j₃( q’₁· a’₁a’₂) = j₁( q’₁) q j₂(a’₁a’₂) =

= q’₁q j₂( a’₁) j₂( a₂’)

No automāta grafa redzam, ka q₁q j₂( a’₁) = b₂ - secinām, ka tas var būt tikai gadījumā, kad j₂(a’₁) = a₁ . Tā rezultātā automāts pāries uz stāvokli q₂ t.i.

q₁* a₁ =q₂. Bet no stāvokļa q₂ , lai izejā iegūtu b₁, vajag ievadīt burtu a₁, un no mūsu augstāk apskatītās izteiksmes redzam, ka j₂(a’₂) = a₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b’₂) = b₁

j₃(b’₁) = b₂

b₂ b₁= j₃( b’₁b’₂ ) = j₃( q’₁· a’₂a’₁) = j₁( q’₁) q j₂(a’₂a’₁) =

= q’₁q j₂( a’₂) j₂( a₁’). ( 1 )

Secinājumus izdaram līdzīgi, kā iepriekšējā punktā.

No iegūtās izteiksmes iegūstam, ka b₂ = q’₁q j₂( a’₂).

Tas iespējams tikai vienā situācijā, ja j₂( a’₂) = a₁ .

Tātad q₁* j₂( a’₂) = q₁* a₁ =q₂ , tāpēc q₂q j₂( a’₁) = b₁

Tas iespējams tikai situācijā, ja j₂( a’₁) = a₁ .

Pretruna, jo sanāk- j₂( a’₂) = a₁ = j₂( a’₁)

2) pieņem, ka j₁(q₁’) = q₂ . Secinām j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

3) pieņem, ka j₁(q₁’) = q₃ . Atkal izmantojam to, ka j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

Esam secinājuši, ka pieņāmumi: j₁(q₁’) = q₁

j₁(q₁’) = q₂

j₁(q₁’) = q₃

Tātad automāts V nemodelē automātu V’.

2. Apskata gadījumu vai V’ nemodelē V.

Lai to pierādītu rīkojamies līdzīgi, kā pirmajā punktā ( pierādot, ka V

nemodelē V’) pietiek pierādīt, ka automāts V’ nemodelē V stāvokli q₁ .

Pieņem pretējo, ka V’ modelē V , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q 5 A^* q® B^*

j₁Æ Æj₂ j₃’

Q’ 5 ( A’)^* ·® ( B’)^* ir komutatīva.

Rīkojoties analogi kā ( iv ) gadījumā secinām, ka diagramma:

Q 5 A^* q® B^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q’ 5 (A’)^* ·® (B’)^* ir komutatīva,

attēlojums j₃ ir bijekcija un j₃= (j₃’)^-1, t.i. j₃ir attēlojuma j₃’ inversais attēlojums.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂(a₁) = j₂(a₂) 2) j₂(a₁) = j₂(a₃) 3) j₂(a₂) = j₂(a₃)

1) j₂(a₁) ¹ j₂(a₂), pretējā gadījumā j₂(a₁) = j₂(a₂), tad

j₃( b₂ ) = j₃( q₁ q a₁) = j₁( q₁) • j₂( a₁) =

= j₁( q₁)• j₂( a₂) = j₃( q₁• a₂ ) = j₃( b₁)

2) j₂(a₁) ¹ j₂(a₃), pretējā gadījumā j₂(a₁) = j₂(a₃), tad

j₃( b₂ ) = j₃( q₁ qa₁) = j₁( q₁) • j₂( a₁) =

= j₁( q₁)• j₂( a₃) = j₃( q₁• a₃ ) = j₃( b₁)

3) j₂(a₂) ¹ j₂(a₃), pretējā gadījumā j₂(a₂) = j₂(a₃), tad

j₃( b₂ ) = j₃( q₃ q a₂ ) = j₁( q₃) •j₂( a₂) =

= j₁( q₃)• j₂( a₃) = j₃( q₃• a₃ ) = j₃( b₁)

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

1) peiņem, ka j₁(q₁) = q’₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b₁) = b’₁

j₃(b₂) = b’₂

b’₂ b’₁= j₃( b₂b₁ ) = j₃( q₁q a₁a₂) = j₁( q₁) Ÿ j₂(a₁a₂) =

= q₁Ÿ j₂( a₁) j₂( a₂)

No q₁Ÿ j₂( a₁) = b’₂ secinām, ka j₂(a₁) = a’₁ . Tā rezultātā q₁* a’₁ =q₂.

Sakarā ar to, ka vajag, lai q₂q j₂( a’₂) = b₁, iegūstam j₂(a’₂) = a₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b₂) = b’₁

j₃(b₁) = b’₂

b’₂ b’₁= j₃( b₁b₂ ) = j₃( q₁q a₂a₁) = j₁( q₁) Ÿ j₂(a₂a₁) =

= q’₁Ÿ j₂( a₂) j₂( a₁). ( 1 )

No šejienes b’₂ = q₁q j₂( a₂). Tas iespējams tikai vienā situācijā, ja

j₂( a₂) = a’₁ . Tātad q’₁* j₂( a’₂) = q’₁* a’₁ =q’₂ , tāpēc q’₂q j₂( a₁) = b’₁

( skatīt vienādību ( 1 ) ). Tas iespējams tikai situācijā, ja j₂( a₁) = a’₁ .

Pretruna, jo j₂( a₂) = a’₁ = j₂( a₁)

2) peiņem, ka j₁(q₁) = q’₂ . Secinām j₃{b₂ ; b₁} = {b’₁ ; b’₂}

Apskatam pirmo apakšgadījumu: j₃(b₁) = b’₁

j₃(b₂) = b’₂

Apskatam otro apakšgadījumu: j₃(b₁) = b’₂

j₃(b₂) = b’₁ , tad

3) peiņem, ka j₁(q₁) = q’₃ . Atkal izmantojam to, ka j₃{b₂ ; b₁} = {b’₁ ; b’₂}

Apskatam pirmo apakšgadījumu: j₃(b₁) = b’₁

j₃(b₂) = b’₂

Apskatam otro apakšgadījumu: j₃(b ₁) = b’₂

j₃(b ₂) = b’₁ , tad

Esam secinājuši, ka pieņēmumi: j₁(q₁) = q’₁

j₁(q₁) = q’₂

j₁(q₁) = q’₃

j₁(q₁) = q’₄

Tātad automāts V’ arī nemodelē automātu V.

Secinājums: automāti V un V’viens otru nemodelē!

Piemērs Nr 4

Apskatīsim piemēru ar automātiem V un V’ ,

kuriem A={ a₁, a₂ a₃} un B ={b₁, b₂, b₃, b₄}

a₁ Automāts V.

b₂

q₁ q₂ q₃ q₄ q₅

a₂ a₂ a₁a₂ a₁a₂ a₁a₂

b₁ b₂ b₃b₃ b₄b₄ b₁b₂

a₁

b₁

a₂ Automāts V’.

b₁

q₁ q₂ q₃ q₄ q₅

a₁ a₂ a₁a₂ a₁a₂ a₁a₂

b₂ b₂ b₃b₃ b₄b₄ b₁b₂

a₁

b₁

( i ) Pārbaudam vai abiem automātiem sakrīt pusgrupas.

Automātam V, automātam V’.

a₁ 1 2 3 4 5 a₁ 1 2 3 4 5

b₁ - 1 - - 5 b₁ - 1 - - 5

a₁ 1 2 3 4 5 a₁ 1 2 3 4 5

b₂ 2 - - - - b₂ 1 - - - -

a₁ 1 2 3 4 5 a₁ 1 2 3 4 5

b₃ - - 4 - - b₃ - - 4 - -

a₁ 1 2 3 4 5 a₁ 1 2 3 4 5

b₄ - - - 4 - b₄ - - - 4 -

a₂ 1 2 3 4 5 a₂ 1 2 3 4 5

b₁ 1 - - - - b₁ 2 - - - -

a₂ 1 2 3 4 5 a₂ 1 2 3 4 5

b₂ - 2 - - 5 b₂ - 2 - - 5

a₂ 1 2 3 4 5 a₂ 1 2 3 4 5

b₃ - - 4 - - b₃ - - 4 - -

a₂ 1 2 3 4 5 a₂ 1 2 3 4 5

b₄ - - - 4 - b₄ - - - 4 -

Automātiem atbilstošās pusgrupas ir vienādas.

( ii ) Apskatam vai automāti V un V’ ir reducēti tas ir- atšķir visus stāvokļus. Automāts V automāts V’q₁ un q₂ q₁q a₂ = b₁ q₁q a₂ = b₁ q₂q a₂ = b₂ q₂q a₂ = b₂q₁ un q₃ q₁q a₂ = b₁ q₁q a₁ = b₂ q₃q a₂ = b₃ q₃q a₁ = b₃q₁ un q₄ q₁q a₂ = b₁ q₁q a₁ = b₂ q₄q a₂ = b₄ q₄q a₁ = b₄q₁ un q₅ q₁q a₂ = b₁ q₁q a₁ = b₂ q₅q a₂ = b₂ q₅q a₁ = b₁q₂ un q₃ q₂q a₂ = b₂ q₂q a₂ = b₂ q₃q a₂ = b₃ q₃q a₂ = b₃q₂ un q₄ q₂q a₂ = b₂ q₂q a₂ = b₂ q₄q a₂ = b₄ q₄q a₂ = b₄q₂ un q₅ q₂q a₁a₁ = b₁b₂ q₁q a₁a₁= b₁b₂ q₅q a₁a₁ = b₁b₁ q₂q a₁a₁= b₁b₁q₃ un q₄ q₃q a₂ = b₃ q₃q a₂ = b₃ q₄q a₂ = b₄ q₄q a₂ = b₄q₃ un q₅ q₃q a₂ = b₃ q₃q a₂ = b₃ q₅q a₂ = b₂ q₄q a₂ = b₂q₄ un q₅ q₄q a₁ = b₄ q₄q a₁ = b₄ q₅q a₁ = b₁ q₅q a₁ = b₁

Konstatējam, ka automātiem atbilstošās pusgrupas ir vienādas.

( iii ) Pārbaudam vai abi automāti atšķir visus ieejas burtus,

tas ir vai tie ir īpaši reducēti.

Automāts V, automāts V’.

a₁ un a₂ q₃q a₁ = b₁ q₁q a₁ = b₁

q₃q a₂ = b₂ q₁q a₂ = b₂

a₁ un a₃ q₄q a₁ = b₁ q₄q a₁ = b₁

q₄q a₃ = b₂ q₄q a₃ = b₂

a₂ un a₃ q₃q a₂ = b₂ q₃q a₂ = b₂

q₃q a₃ = b₁ q₃q a₃ = b₁

Nosacījums izpildās- tātad abi automāti ir īpaši reducēti.

Apskata vai automāti V un V’ nemodelē viens otru.

( iv ) Apskata gadījumu vai V nemodelē V’.

Lai to pierādītu pietiek pierādīt, ka automāts V nemodelē V’ stāvokli q₁ .

Pieņem pretējo, ka V modelē V’ , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q 5 ( A’)^* ·® ( B’)^*

j₁Æ Æj₂ j₃’

Q 5 A^* q® B^* ir komutatīva.

Tā kā alfabēts B sastāv no diviem burtiem un attēlojums Q’ 5 A’ ·® B’

ir sirjekcija, tad arī attēlojums j₃’ ir sirjekcija ( diagramma taču ir komutatīva ).

No tā seko, ka j₃ ir bijekcija, jo abiem automātiem, taču alfābēti ir vienādi un to elementu skaits ir galīgs.

Tāpēc diagramma :

Q 5 (A’)^* ·® (B’)^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q 5 A^* q® B^* ir komutatīva.

Ņemot vērā, ka j₃= ( j₃’ )^-1 ,tas ir, j₃ ir attēlojuma j₃’ inversais attēlojums,

secinām: j₃ ir bijekcija.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂(a’₁) = j₂(a’₂) 2) j₂(a’₁) = j₂(a’₃) 3) j₂(a’₂) = j₂(a’₃)

1) j₂(a’₁) ¹ j₂(a’₂), pretējā gadījumā j₂(a’₁) = j₂(a’₂), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₂) = j₃( q’₁q a’₂ ) = j₃( b’₁)

2) j₂(a’₁)¹j₂(a’₃), pretējā gadījumā j₂(a’₁) = j₂(a’₃), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₃) = j₃( q’₁q a’₃ ) = j₃( b’₁)

3) j₂(a’₂)¹j₂(a’₃), pretējā gadījumā j₂(a’₂) = j₂(a’₃), tad

j₃( b’₁ b’₁) = j₃( q’₁· a’₂a’₁) = j₁( q’₁) q j₂( a’₂) j₂( a’₁) =

= j₁( q’₁)q j₂( a’₃) j₂( a’₁) = j₃( q’₁q a’₃ a’₁) = j₃( b’₁ b’₂)

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V’ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

Ja sīkāk nav paskaidrots, tad secinājumi izdarīti skatoties automātu diagrammas.

1) peiņem, ka j₁(q₁’) = q₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₂ b₁= j₃( b’₂b’₁ ) = j₃( q’₁· a’₁a’₂) = j₁( q’₁) q j₂(a’₁a’₂) =

= q’₁q j₂( a’₁) j₂( a₂’)

No q₁q j₂( a’₁) = b₂ secinām, ka j₂(a’₁) = a₁ . Tā rezultātā q₁* a₁ =q₂.

Sakarā ar to, ka vajag, lai q₂q j₂( a’₂) = b₁, iegūstam j₂(a’₂) = a₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b’₂) = b₁

j₃(b’₁) = b₂

b₂ b₁= j₃( b’₁b’₂ ) = j₃( q’₁· a’₂a’₁) = j₁( q’₁) q j₂(a’₂a’₁) =

= q’₁q j₂( a’₂) j₂( a₁’). ( 1 )

No šejienes b₂ = q’₁q j₂( a’₂). Tas iespējams tikai vienā situācijā, ja

j₂( a’₂) = a₁ . Tātad q₁* j₂( a’₂) = q₁* a₁ =q₂ , tāpēc q₂q j₂( a’₁) = b₁

( skatīt vienādību ( 1 ) ). Tas iespējams tikai situācijā, ja j₂( a’₁) = a₁ .

Pretruna, jo j₂( a’₂) = a₁ = j₂( a’₁)

2) peiņem, ka j₁(q₁’) = q₂ . Secinām j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

3) peiņem, ka j₁(q₁’) = q₃ . Atkal izmantojam to, ka j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₁b₂b₁= j₃( b’₁b’₂b’₁ ) = j₃( q’₁· a’₂a’₂a’₁) = q₃ q j₂(a’₂) j₂(a’₂) j₂(a’₁) , tas var iznākt tikai, ja: j₂(a’₂) = a₁ , j₂(a’₂) = a₂ , j₂(a’₁) = a₁ , pretruna!

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

b₁b₂b₁= j₃( b’₂b’₁b’₂ ) = j₃( q’₁· a’₂a’₂a’₁) = q₃ q j₂(a’₂) j₂(a’₂) j₂(a’₁) , tas var iznākt tikai, ja: j₂(a’₂) = a₁ , j₂(a’₂) = a₂ , j₂(a’₁) = a₁ , atkal pretruna!

4) peiņem, ka j₁(q₁’) = q₄ . Secinām, ka j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₁b₂b₁= j₃( b’₁b’₂b’₁ ) = j₃( q’₁· a’₂a’₂a’₁) = q₄ q j₂(a’₂) j₂(a’₂) j₂(a’₁) , tas var iznākttikai, ja: j₂(a’₂) = a₁ , j₂(a’₂) = a₂ , j₂(a’₁) = a₁ , pretruna!

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

b₁b₂b₁= j₃( b’₂b’₁b’₂ ) = j₃( q’₁· a’₂a’₂a’₁) = q₄ q j₂(a’₂) j₂(a’₂) j₂(a’₁) , tas var iznākt tikai, ja: j₂(a’₂) = a₁ , j₂(a’₂) = a₂ , j₂(a’₁) = a₁ , atkal pretruna!

Esam secinājuši, ka pieņāmumi: j₁(q₁’) = q₁

j₁(q₁’) = q₂

j₁(q₁’) = q₃

j₁(q₁’) = q₄

Tātad automāts V nemodelē automātu V’.

( iiv ) Apskata gadījumu vai V nemodelē V’.

Lai to pierādītu pietiek pierādīt, ka automāts V nemodelē V’ stāvokli q₁ .

Pieņem pretējo, ka V modelē V’ , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q 5 ( A’)^* ·® ( B’)^*

j₁Æ Æj₂ j₃’

Q 5 A^* q® B^* ir komutatīva.

Tā kā alfabēts B sastāv no diviem burtiem un attēlojums Q’ 5 A’ ·® B’

ir sirjekcija, tad arī attēlojums j₃’ ir sirjekcija ( diagramma taču ir komutatīva ).

No tā seko, ka j₃ ir bijekcija, jo abiem automātiem, taču alfābēti ir vienādi un to elementu skaits ir galīgs.

Tāpēc diagramma :

Q 5 (A’)^* ·® (B’)^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q 5 A^* q® B^* ir komutatīva.

Ņemot vērā, ka j₃= ( j₃’ )^-1 ,tas ir, j₃ ir attēlojuma j₃’ inversais attēlojums,

secinām: j₃ ir bijekcija.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂(a’₁) = j₂(a’₂) 2) j₂(a’₁) = j₂(a’₃) 3) j₂(a’₂) = j₂(a’₃)

1) j₂(a’₁) ¹ j₂(a’₂), pretējā gadījumā j₂(a’₁) = j₂(a’₂), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₂) = j₃( q’₁q a’₂ ) = j₃( b’₁)

2) j₂(a’₁)¹j₂(a’₃), pretējā gadījumā j₂(a’₁) = j₂(a’₃), tad

j₃( b’₂ ) = j₃( q’₁· a’₁) = j₁( q’₁) q j₂( a’₁) =

= j₁( q’₁)q j₂( a’₃) = j₃( q’₁q a’₃ ) = j₃( b’₁)

3) j₂(a’₂)¹j₂(a’₃), pretējā gadījumā j₂(a’₂) = j₂(a’₃), tad

j₃( b’₁ b’₁) = j₃( q’₁· a’₂a’₁) = j₁( q’₁) q j₂( a’₂) j₂( a’₁) =

= j₁( q’₁)q j₂( a’₃) j₂( a’₁) = j₃( q’₁q a’₃ a’₁) = j₃( b’₁ b’₂)

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V’ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

Ja sīkāk nav paskaidrots, tad secinājumi izdarīti skatoties automātu diagrammas.

1) peiņem, ka j₁(q₁’) = q₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₂ b₁= j₃( b’₂b’₁ ) = j₃( q’₁· a’₁a’₂) = j₁( q’₁) q j₂(a’₁a’₂) =

= q’₁q j₂( a’₁) j₂( a₂’)

No q₁q j₂( a’₁) = b₂ secinām, ka j₂(a’₁) = a₁ . Tā rezultātā q₁* a₁ =q₂.

Sakarā ar to, ka vajag, lai q₂q j₂( a’₂) = b₁, iegūstam j₂(a’₂) = a₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b’₂) = b₁

j₃(b’₁) = b₂

b₂ b₁= j₃( b’₁b’₂ ) = j₃( q’₁· a’₂a’₁) = j₁( q’₁) q j₂(a’₂a’₁) =

= q’₁q j₂( a’₂) j₂( a₁’). ( 1 )

No šejienes b₂ = q’₁q j₂( a’₂). Tas iespējams tikai vienā situācijā, ja

j₂( a’₂) = a₁ . Tātad q₁* j₂( a’₂) = q₁* a₁ =q₂ , tāpēc q₂q j₂( a’₁) = b₁

( skatīt vienādību ( 1 ) ). Tas iespējams tikai situācijā, ja j₂( a’₁) = a₁ .

Pretruna, jo j₂( a’₂) = a₁ = j₂( a’₁)

2) peiņem, ka j₁(q₁’) = q₂ . Secinām j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

3) peiņem, ka j₁(q₁’) = q₃ . Atkal izmantojam to, ka j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

4) peiņem, ka j₁(q₁’) = q₄ . Secinām, ka j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

Esam secinājuši, ka pieņāmumi: j₁(q₁’) = q₁

j₁(q₁’) = q₂

j₁(q₁’) = q₃

j₁(q₁’) = q₄

Tātad automāts V nemodelē automātu V’.

3.§ Vispārīgāis gadījums.

Analizējot iepriekšējos piemērus rodas iespaids, ka, izmantojot par bāzi mūsu uzkonstruētā automāta pirmos divus stāvokļus, varētu uzkonstruēt arī automātus vispārīgam gadījumam, kuriem arī izpildītos mūsu uzstādītās prasības.

Šo rezultātu varētu noformulēt teorēmas veidā, kurai kā pierādījums kalpotu mūsu nākošā piemēra apskats.

Definīcija. Teiksim, ka automāts V= ( Q,A,B, ŗ,* )pieder klasei K(m,n ), ja

½A½= m un ½B½= n .

Simboliski mēs šo faktu pierakstīsim šādi: VĪ K(m,n)

Teorēma. Katram pārim ( m,n ) ³ ( 2,2 ) eksistē tādi īpaši reducēti klases

K( m,n ) automāti ar vienādām pusgrupām, kas viens otru nemodelē.

Analizējot iepriekšējos piemēros uzkonstruētos automātus, ievērojam, ka varēs vispārināt likumsakarības pēc kurām veicām automātu pusgrupu noteikšanu un salīdzināšanu. Kā redzēsim, arī noteikšanu vai automāti ir reducēti, īpaši reducēti un vai tie viens otru nemodelē varēs noteikt vispārīgam gadījumam.

( i ) Apskatam vai automātu V un V' pusgrupas sakrīt.

Lai varētu parādīt, ka automātu pusgrupas būs vienādas mēs sadalam pierādījumu daļās.

Pirmajā daļā apskatam stāvokļu pārejas pie visām iespējamām ieejas burtu a₁ a₂ un izejas burtu b₁ b₂ kombinācijām, ievērojot , ka (pēc automātu konstrukcijas) stāvokļi un arī pārejas abiem automātiem sākot ar stāvokli q₃ sakrīt. Tādā gadījumā pusgrupu veidojošie elementi abiem automātiem sakritīs. To var konstatēt apskatot piemēru Nr. 1 Arī turpmāk ievērosim, ka atšķirības abiem automātiem "pārejās" var veidoties tikai automātu pirmajos divos stāvokļos.

Tālāk analizējam pusgrupu veidojošo elementu veidošanās mehānismu pie stāvokļu pārejām, kad ieejas un izejas alfabēta burtu kombinācijas ir a_s b_k,

kur ( s, k ) Ļ { ( a₁ b₁ ), ( a₁ b₂ ), ( a₂ b₁ ), ( a₂ b₂ )}

No automātu grafiem redzam, ka situācijas, kad b = 3,n stāvokļiem q₁ q₂ nav definētas, tātad visos gadījumos, kad a = 1,2 un b = 1, n pusgrupu veidojošie elementi abiem automātiem sakritīs. Bet, analizējot tālāk automāta grafu , redzam, ka pirmajos divos stāvokļos pie situācijas, kad a_s, kur s = 3,m , izejās vienmēr būs: stāvoklī q₁ pāreja uz stāvokli q₁ un arī stāvoklī q'₂ pāreja uz q'₂

Līdz ar to esam parādījuši, ka automātu V un V' pusgrupas ir vienādas.

( ii ) Tālāk, izdarot līdzīgus spriedumus parādam, ka automāti ir reducēti-

jebkuri divi stāvokļi automātā ir atšķirami.

Atkal pierādījumu sadalam pa daļām.

Pirmajā daļā apskatamies kā atšķirt stāvkoli q₁ no q₂.

1) automātam V q₁ ŗ a₁ =b₂ ¹ b₁= q₂ ŗ a₁

2) automātam V ' q₁ ŗ a₁ =b₂ ¹ b₁= q₂ ŗ a₁

Otrajā daļā apskatam gadījumus, kuros parādam, kā atšķirt stāvokli q₁ no stāvokļiem q₃ līdz q_n ievērojot ka automātu stāvokļu atšķiramība abiem automātiem V un V'ir vienāda: q₁ŗ a₂ = b₁ ¹ b_s= q_sŗ a₂ , ja s = 3,n

Trešajā daļā apskatam gadījumus, kad parādam, kā atšķirt q₁ no stāvokļiem

q_n+1 līdz q_n+m-2. .

q₁ŗ a₁ = b₂ ¹ b₁= q_dŗ a₂ , ja d = n+1, n+m-2

Ceturtajā daļā, līdzīgi, kā iepriekš, parādam kā atšķirt q₂ no visiem citiem stāvokļiem:

1) q₂ŗ a₂ = b₂ ¹ b_s= q_sŗ a₂ , ja s = 3,n

2) q₂ŗ a_d+1 = b₂ ¹ b₁= q_d+nŗ a_d+1 , ja d = 1, m -2

Piektajā daļā apskatam, kā atšķirt pārējos stāvokļus vienu no otra:

q_sŗ a₁ = b_s ¹ b_d= q_dŗ a₁ , s = 3,n -1 d = s+1, n

q_sŗ a₁ = b_s ¹ b₁= q_iŗ a₁ , i = n+1, n+m-2

q_sŗ a₁ = b_s ¹ b_d= q_dŗ a₁ , ja s = n +1, n+m-3 d = s, n+m-2

q_n+s-1ŗ a_s = b₁ ¹ b₂= q_n+s-1+iŗ a_s , ja s = 2,..., m-2 i = 1, m-s-1

( iii ) Parādam, ka automāti ir īpaši reducēti - tie atšķir visus ieejas burtus.

Arī šoreiz atsevišķi parādam kā atšķirsim burtus a₁ un a₂.

q₁ŗ a₁ = b₂ ¹ b₁= q₁ŗ a₂ ,

Tālāk, līdzīgi, kā iepriekš apskatam pārējo ieejas burtu atšķiramību:

q_n+1ŗ a₁ = b₁ ¹ b₂= q_n+1ŗ a_s , ja s = 3,m

q_n+d-1ŗ a_d = b₁ ¹ b₂= q_n+d-1ŗ a_i , ja d = 2, m-1 i = d+1, m

( iv ) Apskatam vai automāti V un V' viens otru modelē.

1.Vispirms apskatīsim gadījumu vai V nemodelē V'. Līdzīgi, kā iepriekš apskatītajos piemēros izvēlēsimies vienu stāvokli automātā V' un pierādīsim, ka starp automāta V stāvokļiem nevarēs atrast tādu stāvokli, kurš spētu modelēt šo automāta V' stāvokli.

Tas arī ļaus izdarīt vispārīgu secinājumu, ka V nemodelē V'.

Pieņem pretējo, ka V modelē V’ , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q' 5 ( A’)^* ·® ( B’)^*

j₁Æ Æj₂ j'₃

Q 5 A^* q® B^* ir komutatīva.

Tā kā alfabēts B sastāv no 1,n burtiem un attēlojums Q’ 5 A’ ·® B’

ir sirjekcija, tad arī attēlojums j₃’ ir sirjekcija ( diagramma taču ir komutatīva ).

No tā seko, ka j₃ ir bijekcija, jo abiem automātiem, taču alfābēti ir vienādi un to elementu skaits ir galīgs.

Tāpēc diagramma :

Q' 5 (A’)^* ·® (B’)^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q 5 A^* q® B^* ir komutatīva.

Ņemot vērā, ka j₃= ( j₃’ )^-1 ,tas ir, j₃ ir attēlojuma j₃’ inversais attēlojums,

secinām: j₃ ir bijekcija.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂( a'₁ ) ¹ j₂( a'₂ ), pretējā gadījumā j₂( a'₁ ) = j₂( a'₂ ) , tad

j₃ (b'₂) = j₃ (q'₁· a'₁) = j₁(q'₁) ° j₂(a'₂) =

= j₁(q'₁) ° j₂(a'₁) = j₃(q'₁· a'₁) = j₃(b'₁)

Pretruna!

2)Pārējos gadījumos apskatīsim vai- j₂(a’_i) ¹ j₂(a’_j),

Pieņem, ka j₂(a’_i) = j₂(a’_j) i¹j , konkrētības labad var pieņemt, ka i

(i,j)¹(1,2), jo to jau mēs esam izanalizējuši:

j₃ (b'₁) = j₃ (q'_n+i-1· a'_i) = j₁(q'_n+i-1) ° j₂(a'_i) =

= j₁(q'_n+i-1) ° j₂(a'_j) = j₃(q'_n+i-1· a'_j) = j₃(b'₃)

Iegūtais rezultāts ir pretrunā ar faktu, ka j₃ ir bijekcija.

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V’ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

1) pieņem, ka j₁(q₁’) = q₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b’₁) = b₁

j₃(b’₂) = b₂

b₂ b₁= j₃( b’₂b’₁ )= j₃( q’₁· a’₁a’₂)= j₁( q’₁) q j₂(a’₁a’₂)= q’₁q j₂( a’₁) j₂( a₂’)

No automāta grafa redzam, ka q₁q j₂( a’₁) = b₂ - secinām, ka tas var būt tikai gadījumā, kad j₂(a’₁) = a₁ . Tā rezultātā automāts pāries uz stāvokli q₂ t.i.

q₁* a₁ =q₂. Bet no stāvokļa q₂ , lai izejā iegūtu b₁, vajag ievadīt burtu a₁, un no mūsu augstāk apskatītās izteiksmes redzam, ka j₂(a’₂) = a₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b’₂) = b₁

j₃(b’₁) = b₂

b₂ b₁= j₃( b’₁b’₂ )= j₃( q’₁· a’₂a’₁)= j₁( q’₁) q j₂(a’₂a’₁)= q’₁q j₂( a’₂) j₂( a₁’).

Secinājumus izdaram līdzīgi, kā iepriekšējā punktā. No iegūtās izteiksmes iegūstam, ka b₂ = q’₁q j₂( a’₂). Tas iespējams tikai vienā situācijā,

ja j₂( a’₂) = a₁ . Tātad q₁* j₂( a’₂) = q₁* a₁ =q₂ , tāpēc q₂q j₂( a’₁) = b₁

Tas iespējams tikai situācijā, ja j₂( a’₁) = a₁ .

Pretruna, jo sanāk- j₂( a’₂) = a₁ = j₂( a’₁)

2) pieņem, ka j₁(q₁’) = q₂. Secinām j₃{b’₂ ; b’₁} = {b₁ ; b₂}

Apskatam pirmo apakšgadījumu: j₃(b’₁) = b₁

j₃(b’₂) = b₂

Apskatam otro apakšgadījumu: j₃(b’₁) = b₂

j₃(b’₂) = b₁ , tad

3)Pārējo gadījumu apskatu varam vispārināt: j₁(q₁’) = q_s s =3,n

pierādījumā izmantosim vārdu u' = a'₁^n-sa'₂ a'₁

j₃( b'₂^k-2) j₃( b’₁b’₂ ) =j₃( b'₂^k-2 b’₁b’₂ )= j₃( q’₁· u' ) = q_s q j₂(a’₁^n-s) j₂(a’₂a’₁)=

= q_s q j₂(a’₁^n-s) # q_s q j₂(a’₁^n-s) j₂(a’₂a’₁) , kur ar # sapratīsim konkatenāciju.

q_s q j₂(a’₁^n-s)=q_n un iegūstam q_n qj₂(a’₂a’₁)= j₃( b’₁ ) j₃( b’₂ )

Tā, kā j₃ ir bijekcija, tad j₃( b’₁ ) ¹j₃( b’₂ ), bet q_n qj₂(a’₂)= q_n qj₂(a’₁)=b_n

Sīkāk paskaidrojot var teikt- pateicoties mūsu izvēlētajām automātu konstrukcijām var ievērot, ka mums vienmēr izdosies atrast tādu vārdu , kuru ievadot automātā varēsim iegūt rezultātu, ka stāvokli q'₁ nevarēs modelēt neviens automāta V stāvoklis.

Sākot ar stāvokli q₃ mums ir jānorāda vārds u tik garš, lai ievadot automātā mēs nokļūtu stāvoklī q_n+m-2 pievienojot u vēl divus burtus a₂a₁ varēsim iegūt vajadzīgo pretrunu, jo ievadot šo pašu vārdu u stāvoklī q'₁ automāts visu laiku atradīsies šajā stāvoklī . Ar tālākajiem diviem burtiem , kurus pievienosim vārdam u varēsim nodrošināt situāciju, kad radīsies pretruna, ka j₃ ir bijekcija.

2) Līdzīgi apskatīsim vai V' nemodelē V. Izvēlēsimies stāvokli q₁

automātā V un pierādīsim, ka starp automāta V' stāvokļiem nevarēs atrast

tādu stāvokli, kurš spētu modelēt šo automāta V stāvokli.

Pieņem pretējo, ka V modelē V’ , tad eksistē attēlojumi j₁, j₂, j₃, tādi, ka

diagramma:

Q' 5 ( A’)^* ·® ( B’)^*

j₁Æ Æj₂ j'₃

Q 5 A^* q® B^* ir komutatīva.

Tā kā alfabēts B sastāv no 1,n burtiem un attēlojums Q’ 5 A’ ·® B’

ir sirjekcija, tad arī attēlojums j₃’ ir sirjekcija ( diagramma ir komutatīva ).

No tā seko, ka j₃ ir bijekcija, jo abiem automātiem, taču alfābēti ir vienādi un to elementu skaits ir galīgs.

Tāpēc diagramma :

Q' 5 (A’)^* ·® (B’)^*

j₁Æ Æj₂ Æj₃ ( 1 )

Q 5 A^* q® B^* ir komutatīva.

Ņemot vērā, ka j₃= ( j₃’ )^-1 ,tas ir, j₃ ir attēlojuma j₃’ inversais attēlojums,

secinām: j₃ ir bijekcija.

Pievēršamies attēlojumam j₂ ,mēs pierādīsim, ka j₂ arī ir bijekcija.

Ja tas tā nebūtu, tad izpildītos vismaz viena no sekojošām vienādībām:

1) j₂( a₁ ) ¹ j₂( a₂ ), pretējā gadījumā j₂( a₁ ) = j₂( a₂ ) , tad

j₃ (b₂) = j₃ (q₁ŗ a₁) = j₁(q₁) · j₂(a₂) = j₁(q₁) · j₂(a₁) = j₃(q₁ŗ a₁) = j₃(b₁)

Pretruna!

2) Pārējos gadījumos apskatīsim vai- j₂(a_i) ¹ j₂(a_j),

Pieņem, ka j₂(a_i) = j₂(a_j) i¹j , konkrētības labad var pieņemt, ka i

(i,j)¹(1,2), jo to jau mēs esam izanalizējuši.

j₃ (b₁) = j₃ (q_n+i-1ŗ a_i) = j₁(q_n+i-1) · j₂(a_i) =

= j₁(q_n+i-1) · j₂(a_j) = j₃(q_n+i-1ŗ a_j) = j₃(b₃)

Iegūtais rezultāts ir pretrunā ar faktu, ka j₃ ir bijekcija.

Esam pierādījuši, ka j₂ ir injekcija, bet tas savukārt nozīmē, ka j₂ ir bijekcija.

Tā kā V’ir reducēts automāts, tad j₁ ir injekcija. Tā kā kopas Q abiem automātiem ir vienādas un galīgas, tad tas nozīmē, ka j₁ ir bijekcija.

Apskatam attēlojumu j₁.

1) pieņem, ka j₁(q₁) = q'₁ , tad iespējamas tikai divas situācijas, jo atrodoties

stāvokļos q₁ un q₂ izejā ir tikai b₁ un b_2.

Apskatam gadījumu, kad: j₃(b₁) = b'₁

j₃(b₂) = b'₂

b'₂ b'₁= j₃( b₂b₁ )= j₃( q₁ŗ a₁a₂)= j₁( q₁) · j₂(a₁a₂)= q₁· j₂( a₁) j₂( a₂)

No automāta grafa redzam, ka q₁q j₂( a₁) = b'₂ - secinām, ka tas var būt tikai gadījumā, kad j₂(a₁) = a'₁ . Tā rezultātā automāts pāries uz stāvokli q₂ t.i.

q₁* a'₁ =q₂. Bet no stāvokļa q₂ , lai izejā iegūtu b₁, vajag ievadīt burtu a₁, un no mūsu augstāk apskatītās izteiksmes redzam, ka j₂(a₂) = a'₁.

Pretruna, jo j₂ ir bijekcija!

Apskatam gadījumu, kad: j₃(b₂) = b'₁

j₃(b₁) = b'₂

b'₂ b'₁= j₃( b₁b₂ )= j₃( q’₁ŗ a₂a₁)= j₁( q₁) · j₂(a₂a₁)= q₁q j₂( a₂) j₂( a₁).

Secinājumus izdaram līdzīgi, kā iepriekšējā punktā. No iegūtās izteiksmes iegūstam, ka b'₂ = q₁q j₂( a₂). Tas iespējams tikai vienā situācijā,

ja j₂( a₂) = a'₁ . Tātad q'₁* j₂( a₂) = q'₁* a₁ =q'₂ , tāpēc q'₂q j₂( a₁) = b'₁

Tas iespējams tikai situācijā, ja j₂( a₁) = a'₁ .

Pretruna, jo sanāk- j₂( a₂) = a'₁ = j₂( a₁)

2) pieņem, ka j₁(q₁) = q'₂. Secinām j₃{b₂ ; b₁} = {b'₁ ; b'₂}

Apskatam pirmo apakšgadījumu: j₃(b₁) = b'₁

j₃(b₂) = b'₂

b'₁b'₂b'₁= j₃( b₁b₂b₁ ) = j₃( q₁ŗ a₂a₂a₁) = q₂ · j₂(a₂) j₂(a₂) j₂(a₁) , tas var iznākt tikai, ja: j₂(a₂) = a'₁ , j₂(a₂) = a'₁ , j₂(a₁) = a'₁ , bet j₂ ir bijekcija, tātad vienam un tam pašam attēlojumam nevar atbilst divas dažādas vērtības , jo j₃ ir bijekcija.

Apskatam otro apakšgadījumu: j₃(b₁) = b'₂

j₃(b₂) = b'₁ , tad

b'₁b'₂b'₁= j₃( b₂b₁b₂ ) = j₃( q₁ŗ a₁a₂a₂) = q₂ · j₂(a₁) j₂(a₂) j₂(a₂) , tas var iznākt tikai, ja: j₂(a₁) = a'₁ , j₂(a₂) = a'₁ , j₂(a₂) = a'₁ , atkal pretruna!

3)Pārējo gadījumu apskatu varam vispārināt: j₁(q₁) = q'_s s =3,n

pierādījumā izmantosim vārdu u = a₁^n-sa₂ a₁

j₃( b₂^k-2) j₃( b₁b₂ ) =j₃( b₂^k-2 b₁b₂ )= j₃( q₁ŗ u ) = q_s · j₂(a₁^n-s) j₂(a₂a₁)=

= q_s · j₂(a₁^n-s) # q_s · j₂(a₁^n-s) j₂(a₂a₁) , kur ar # sapratīsim konkatenāciju.

q_s q j₂(a₁^n-s)=q_n un iegūstam q_n qj₂(a₂a₁)= j₃( b₁ ) j₃( b₂ )

Tā, kā j₃ ir bijekcija, tad j₃( b₁ ) ¹j₃( b₂ ), bet q_n qj₂(a₂)= q_n qj₂(a₁)=b'_n

NOBEIGUMS

Ja mēs vēlamies paturēt saiti ar reālām kibernētiskām iekārtām, tad algebriskā automātu teorijā modelēšanas attiecībai visu laiku jābūt uzmanības lokā. Šai skatījumā arī organizēts maģistradarbs. Pievērsīsimies svarīgāko momentu apskatam.

1. Eksistē attiecībā pret modelēšanu nesalīdzināmi automāti ar vienādām pusgrupām. Šis rerezultāts parāda, ka pāreja : automāts - pusgrupa, vismaz modelēšanas aspektā, nav visai sekmīga. Maģistra darbā apskatīti automāti ar minimālu ieejas (2), izejas (2) burtu un stāvokļu (2) skaitu.Un konstatēts, ka arī šajā gadījumā izpildās nosacījums- automāti ir īpaši reducēti, to pusgrupas sakrīt, bet tie viens otru nemodelē.Tika apskatīti arī izvērstāki piemēri - ar dažādu ieejas, izejas un stāvokļu skaitu, līdz nonākts pie vispārīgā automātu veida , kuram arī izpildās augstāk pieminētais nosacījums. Mūsdienās datori galvenokārt strādā ar bināru informāciju, tāpēc tas bija vēl viens arguments V. Bužas darba turpināšanai šai virzienā.

Kaut arī vispārīgā situācijā, automāta vietā apskatot tā pusgrupu, modelēšanas aspektā iespējams zaudēt būtisku informāciju, tomēr atsevišķām automātu klasēm šī pāreja var izrādīties auglīga (piemēram, autonomiem automātiem).

LITERATŪRA

1. Lorencs A. A. // Automātu kontrole un diagnostika:-

Rīga : Pētergailis - 1993.

2. Balode I. // Automāta pusgrupas reprezentācija.-

maģistra darbs - Rīga. - 1995.

3. Skorņakovs L.A. // Algebras elementi.- Maskava:

Zinātne.-1986.

4. Kudrjavcevs V.B. Aļošins S.V. Podkolzans A.S. // Ievads automātu

teorijā.- Maskava: Zinātne-1985.

5. Buža V. // Automātu pusgrupas un modelēšana:-

maģistra darbs - Rīga. - 1996.

Bezmaksas referāti skolai

AUTOMĀTU PUSGRUPAS UN MODELĒŠANA (1997)

APZĪMĒJUMU SARAKSTS.

JĒDZIENI UN SVARĪGĀKIE APZĪMĒJUMI.

1. nodaļa.

AUTOMĀTA PUSGRUPA.

1§.Visur definēta pusgrupa.

2§. Daļēji definēta pusgrupa.

Šādā veidā mēs panākam, ka arī izejas funkcija iespaido automāta pusgrupu.

2. Nodaļa.

AUTOMĀTU NEATŠĶIRAMĪBA

3. nodaļa.

AUTOMĀTU MODELĒŠANA

NOBEIGUMS

LITERATŪRA

Nav komentāru:

Ierakstīt komentāru