Метода

NEDOOPREDELENNYM; ESLI VE FUNKCIQ ' OPREDELENA DLQ WSEH q 2 Q I a 2 A , TO AWTOMAT K NAZYWA@T OPREDELENNYM ILI POLNYM.

wMESTO qk = '(qi; aj) BUDEM ^ASTO PISATX qiaj ! qk I NAZYWATX \TU ZAPISX PRAWILOM PEREHODA ILI KOMANDOJ.

zADAWATX FUNKCI@ PEREHODOW MOVNO

1)SPISKOM PRAWIL PEREHODOW,

2)TABLICEJ ZNA^ENIJ FUNKCII ' ,

3)ORIENTIROWANNYM GRAFOM, U KOTOROGO WER[INAMI QWLQ@TSQ

q1; q2; : : : ; qn , A KAVDOE PRAWILO PEREHODA giaj ! qk IZOBRAVAETSQ W WIDE DUGI (qi; qk) S OTMETKOJ aj .

kONE^NYJ AWTOMAT NA^INAET RABOTU W NA^ALXNOM SOSTOQNII q1 I POSLEDOWATELXNO ^ITAET BUKWY NEKOTOROGO WHODNOGO SLOWA W ALFAWITE A , IZMENQQ SWOE TEKU]EE SOSTOQNIE. eSLI AWTOMAT W SO-

62

STOQNII qi ^ITAET SIMWOL aj , TO ON WYPOLNQET ODNO IZ PRAWIL ! qk , PEREHODQ W NOWOE SOSTOQNIE qk , I ^ITAET SLEDU@]IJ

SIMWOL SLOWA .

kONFIGURACIEJ AWTOMATA K NAZYWAETSQ SLOWO WIDA q! , GDE q | TEKU]EE SOSTOQNIE, ! | NEDO^ITANNAQ ^ASTX SLOWA WKL@^AQ ^ITAEMYJ SIMWOL. nA^ALXNAQ KONFIGURACIQ IMEET WID q1 . eSLI IZ KONFIGURACII C1 AWTOMAT PEREHODIT ZA NESKOLXKO [AGOW K KONFIGURACII C2 , TO PI[UT C1 ) C2 . eSLI ZA NESKOLXKO [AGOW AWTOMAT K IZ NA^ALXNOJ KONFIGURACII C1 PRIHODIT K KONFIGURACII C2 = qi" , GDE qi 2 Qc , TO PI[UT K : C1 ` C2 ILI K : C1 ) C2 . w \TOM SLU^AE GOWORQT, ^TO KONE^NYJ AWTOMAT WOSPRINIMAET ILI DOPUSKAET SLOWO . pOD QZYKOM, WOSPRINIMAEMYM AWTOMATOM, PONIMA@T MNOVESTWO L(K) WSEH WOSPRINIMAEMYH IM SLOW.

pRIMER 1. pUSTX K = (A; Q; ') , GDE A = fa; bg , Q = fq1; q2; q3g .

sPISOK q1a ! q1 , q1a ! q2 , q2b ! q2 , q2b ! q3 ZADAET FUNKCI@ PEREHODOW ' . |TU VE FUNKCI@ MOVNO ZADATX TABLI^NO (SM. TABL. 2).

oRIENTIROWANNYJ GRAF DLQ \TOGO AWTOMATA IZOBRAVEN NA RIS. 2. tABLICA 2

rIS. 2

w ZAWISIMOSTI OT WYBORA Qc MOVET IZMENITXSQ QZYK, WOSPRINIMAEMYJ AWTOMATOM K . w SLU^AE PRIMERA 1 IMEEM

1)ESLI Qc = fq3g , TO L(K) = fambn j m; n > 1g ;

2)ESLI Qc = fq1; q3g , TO L(K) = fambn j m; n > 1g[fak j k > 0g ;

3)ESLI Qc = fq2; q3g , TO L(K) = fambn j m > 1; n > 0g .

x6. kONE^NYE AWTOMATY I REGULQRNYE QZYKI

rOLX KONE^NYH AWTOMATOW W RASPOZNAWANII QZYKOW WYQSNQETSQ W SLEDU@]IH TEOREMAH.

tEOREMA 1. l@BOJ REGULQRNYJ QZYK RASPOZNAETSQ NEKOTORYM KONE^NYM AWTOMATOM.

63

pRI TAKOM SOOTWETSTWII KAVDOE SLOWO 2 L(K) MOVET BYTX WYWEDENO W POSTROENNOJ GRAMMATIKE G , I PRO^ITANNAQ ^ASTX SLOWAKONE^NYM AWTOMATOM K W KAVDYJ MOMENT WREMENI OPQTX SOWPADAET S POSTROENNOJ ^ASTX@ SLOWA W GRAMMATIKE G . pOSKOLXKU POSTROENNAQ GRAMMATIKA G QWLQETSQ REGULQRNOJ, TO I QZYK L(K) , RAWNYJ L(G) , TOVE BUDET REGULQRNYM. tEOREMA DOKAZANA.

pRIMER 2. kONE^NYJ AWTOMAT, IZOBRAVENNYJ NA RIS. 4, IMEET

PRAWILA PEREHODA q1a ! q2 , q1a ! q3 , q2b ! q3 , q2b ! q4 , q3b ! q1 , q3b ! q2 . sIGNALXNYM SOSTOQNIEM QWLQETSQ q4 . zAMETIM, ^TO

\TOT AWTOMAT RASPOZNAET QZYK L(K) = (ab+)+ . gRAMMATIKA G ,

tEOREMA 3. qZYK L = fambm j m > 0g NE QWLQETSQ REGULQRNYM. dOKAZATELXSTWO. eSLI L QWLQETSQ REGULQRNYM, TO SU]ESTWUET KONE^NYJ AWTOMAT K , KOTORYJ EGO RASPOZNAET. pUSTX KOLI^ESTWO EGO SOSTOQNIJ RAWNO n . wYBEREM SLOWO ambm , GDE m > n . pOSKOLXKU n < m, TO PRI ^TENII m BUKW a KAKOE-TO SOSTOQNIE qi AWTOMATA K POQWITSQ POWTORNO, NAPRIMER, ^EREZ k [AGOW, GDE k < m . oT- S@DA SLEDUET, ^TO AWTOMAT K NE RAZLI^AET SLOWA ambm I am;kbm . sLEDOWATELXNO QZYK L = fambm j m > 0g NE MOVET BYTX RASPOZNAN

NIKAKIM KONE^NYM AWTOMATOM I ZNA^IT NE QWLQETSQ REGULQRNYM. tEOREMA DOKAZANA.

x7. pREOBRAZOWANIQ KONE^NYH AWTOMATOW

dWA KONE^NYH AWTOMATA NAZYWA@TSQ \KWIWALENTNYMI, ESLI ONI WOSPRINIMA@T ODIN I TOT VE QZYK.

pO L@BOMU NEDETERMINIROWANNOMU KONE^NOMU AWTOMATU

= (A; Q; 'nd) MOVNO POSTROITX \KWIWALENTNYJ EMU KONE^NYJ AWTOMAT Kd PO SLEDU@]EMU ALGORITMU.

65

1.mNOVESTWO SOSTOQNIJ AWTOMATA Kd RAWNO MNOVESTWU WSEH PODMNOVESTW Q ; ONO OBOZNA^AETSQ ^EREZ P (Q) .

2.aWTOMAT Kd IMEET PRAWILO PEREHODA Q1a ! Q2 W TOM SLU- ^AE, KOGDA Q1 Q , a 2 A , A PODMNOVESTWO Q2 = '(Q1; a) . eSLI OKAVETSQ, ^TO Q2 = ? , TO PRAWILO Q1a ! Q2 MOVNO OPUSTITX. sIGNALXNYMI BUDUT TE PODMNOVESTWA Qi , W KOTORYH IMEETSQ HOTQ BY ODNO SIGNALXNOE SOSTOQNIE AWTOMATA Knd .

pRI NAHOVDENII PRAWIL PEREHODA KONE^NOGO AWTOMATA

NO ISPOLXZOWATX TABLICU ZNA^ENIJ 'nd I DOPOLNQTX EE DO TABLICY ZNA^ENIJ 'd .

pRIMER 1. w PREDYDU]EM PARAGRAFE (SM. PRIMER 2 NA S. 65) MY RASSMATRIWALI NEDETERMINIROWANNYJ AWTOMAT Knd , KOTORYJ IMEET FUNKCI@ PEREHODOW 'nd , PRIWEDENNU@ W TABL. 3. dOPOLNIW EE STRO^KAMI IZ TABL. 4, POLU^IM ISKOMU@ TABLICU ZNA^ENIJ FUNKCII PEREHODOW DLQ SOOTWETSTWU@]EGO DETERMINIROWANNOGO AWTOMATA Kd .

DOSTIVIMY IZ NA^ALXNOJ WER[INY q1 , PO\TOMU IH MOVNO UDALITX, I MY POLU^AEM UPRO]ENNYJ DETERMINIROWANNYJ AWTOMAT, IZOBRAVENNYJ NA RIS. 6.

w ZAKL@^ENIE ZAMETIM, ^TO WSE \TI AWTOMATY RASPOZNA@T ODIN I TOT VE QZYK L = (ab+)+ . dRUGIE PRIMERY PREOBRAZOWANIJ KONE^NYH AWTOMATOW W BOLX[OM KOLI^ESTWE PREDSTAWLENY W U^EBNOM POSOBII [12] .

x8. mETOD CIKLI^ESKIH KOMPLEKSOW

w \TOM PARAGRAFE MY PRIWEDEM ALGORITM NAHOVDENIQ REGULQRNOGO QZYKA L , RASPOZNAWAEMOGO DANNYM KONE^NYM AWTOMATOM K .

pRIMER 1. bUDEM DEMONSTRIROWATX RABOTU ALGORITMA NA PRIMERE AWTOMATA, GRAF KOTOROGO IZOBRAVEN NA RIS. 7.

1. nAHODIM WSE ORIENTIROWANNYE \LEMENTARNYE CEPI, WEDU]IE

sTRELKA S BUKWOJ POKAZYWAET NAPRAWLENIE SOOTWETSTWU@]EJ DUGI GRAFA I EE OTMETKU.

tOGDA L = L1 [L2 , A QZYKI L1 I L2

L1 = K1 [?] a K2 [1] b K5 [1; 2] I

L2 = K1 [?] b K3 [1] a K4 [1; 3] a K2 [1; 3; 4] b K5 [1; 2;3; 4] .

|TI FORMULY POLU^ENY IZ CEPEJ l1 I l2 ZAMENOJ WER[IN NA SOOTWETSTWU@]IE CIKLI^ESKIE KOMPLEKSY, PRI^EM W KAVDOM SLEDU@- ]EM KOMPLEKSE ISKL@^A@TSQ WSE PREDYDU]IE WER[INY; DLQ KRATKOSTI MY NAPISALI W KOMPLEKSAH NE SAMI WER[INY, A IH NOMERA.

2. dALEE WY^ISLQEM KAK TE KOMPLEKSY, KOTORYE UVE POLU^ILISX, TAK I TE, KOTORYE POQWQTSQ DALX[E, DO TEH POR, POKA NE PRIDEM K PUSTYM KOMPLEKSAM.

K1[?] = ? , T.K. NET CIKLA, SOEDINQ@]EGO q1 S q1 ;

68

x9. kONTEKSTNO SWOBODNYE QZYKI I GRAMMATIKI

nAPOMINAEM, ^TO ks-GRAMMATIKA G = (T; NT; P ) MOVET IMETX PRAWILA WIDA A ! , GDE 2 (T [ NT) . dOPUSKAETSQ EDINSTWENNOE PRAWILO I ! " S PUSTYM SLOWOM .

pRIWEDEM NEKOTORYE PRIMERY KONTEKSTNO SWOBODNYH QZYKOW.

1) RAS[IRITX ALFAWIT NT DOBAWLENIEM NOWYH NETERMINALXNYH SIMWOLOW A1; A2; : : : ; An , SOOTWETSTWU@]IH TERMINALXNYM SIMWOLAM

2) WO WSEH PRAWILAH A ! , GDE j j > 2 , ZAMENITX WSE TERMINALXNYE ai NA Ai ;

3) DOBAWITX NOWYE PRAWILA Ai ! ai , i = 1; 2; : : : ; n .

pRIMER 4. pRIMENIW \TO PREOBRAZOWANIE K GRAMMATIKE G3 , RASSMOTRENNOJ W PRIMERE 3, MY POLU^IM ks-GRAMMATIKU G03 S PRAWI-

I ! A1B ! aB ! aA1BB ! aaBB ! aabB ! aabA1BB ! aabaBB ! aababB ! aababb .

uDOBSTWO RABOTY W GRAMMATIKE G03 SOSTOIT W TOM, ^TO NA KAVDOM [AGE PRIMENQETSQ NEKOTOROE PRAWILO GRAMMATIKI K SAMOMU LEWOMU NETERMINALU.

mOVNO POJTI E]E DALX[E I ISKL@^ITX IZ GRAMMATIKI WSE PRA-

69

WILA WIDA A ! B1B2 : : : Bk , GDE k > 2 , ZAMENIW KAVDOE IZ NIH NA

CEPO^KU PRAWIL A ! B1C1 , C1 ! B2C2; : : : ; Cn;3 ! Bn;2Cn;2 ,

Cn;2 ! Bn;1Bn S POMO]X@ NOWYH NETERMINALOW C1; C2; : : : ; Cn;2 . w REZULXTATE POLU^AETSQ ks-GRAMMATIKA W NORMALXNOJ FORME hOMSKOGO (ILI BINARNOJ FORME). w \TOJ GRAMMATIKE SOHRANQETSQ OPISANNOE WY[E UDOBNOE SWOJSTWO WYWODA SLOW.

pRIMER 5. pREOBRAZOWAW K NORMALXNOJ FORME hOMSKOGO GRAMMATIKU G2 (SM. PRIMER 2), MY POLU^IM ks-GRAMMATIKU G02 S PRAWI-

LAMI I ! A1C1 j B1C2 j c , C1 ! IA1 , C2 ! IB1 , A1 ! a , B1 ! b .

wYWOD SLOWA abbcbba W GRAMMATIKE G02 BUDET WYGLQDETX TAK:

I ! A1 C1 ! aC1 ! aIA1 ! abC2A1 ! abIB1A1 ! abB1C2 B1A1 ! abbC2B1A1 ! abbIB1B1A1 ! abbcB1B1A1 ! abbcbB1 A1 ! abbcbbA1 ! abbcbba .

x10. sTEKOWYE AWTOMATY

oPREDELENIE 1. sTEKOWYM ILI MAGAZINNYM AWTOMATOM M NAZYWAETSQ ^ETWERKA (A; As; Q; P ) , GDE A = fa1; a2; : : : ; amg | WHODNOJ ALFAWIT; As = fZ0 ; Z1 ; : : : ; Zkg | STEKOWYJ ALFAWIT; Z0 | NA^ALXNYJ SIMWOL STEKA; Q = fq1; q2; : : : ; qng | MNOVESTWO WNUTRENNIH SOSTOQNIJ; q1 | NA^ALXNOE SOSTOQNIE; P | MNOVESTWO PRAWIL PEREPISYWANIQ WIDA qiajZk ! ql , PO KOTOROMU AWTOMAT M BUDU^I W SOSTOQNII qi , IMEQ W WER[INE STEKA SIMWOL Zk , ^ITAET SIMWOL aj I PEREHODIT W SOSTOQNIE ql , ZAMENQQ Zk NA STEKOWOE SLOWO 2 As , PRI \TOM MOVET BYTX I PUSTYM SLOWOM, OBOZNA^A- EMYM "0 .

CTEKOWYJ AWTOMAT NA^INAET RABOTU W NA^ALXNOM SOSTOQNII q1 , IMEET W STEKE SIMWOL Z0 I POSLEDOWATELXNO ^ITAET SIMWOLY WHODNOGO SLOWA 2 A , IZMENQQ PRI \TOM SWOE WNUTRENNEE SOSTOQNIE I SODERVIMOE STEKA, T.E. IZMENQET KONFIGURACI@ C = qi! , GDE qi | TEKU]EE WNUTRENNEE SOSTOQNIE, ! | NEPRO^ITANNAQ ^ASTX SLOWAWKL@^AQ ^ITAEMYJ SIMWOL, | TEKU]EE SODERVIMOE STEKA.

eSLI IZ NA^ALXNOJ KONFIGURACII C0 = q1 Z0 STEKOWYJ AWTOMAT PRIHODIT W ZAKL@^ITELXNU@ KONFIGURACI@ C1 = qi""0 , TO PI- [UT q1 Z0 ` qi""0 I GOWORQT, ^TO AWTOMAT WOSPRINIMAET SLOWO .

70