Лекция 8 Тақырыбы: Тьюринг машинасы

Лекция 8

Тақырыбы: Тьюринг машинасы

Тьюринг машинасы мен шекті автоматтың негізгі айырмашылығы мынада:

1. 
   Тьюринг машинасының лентасы шексіз.
   
2. 
   Тьюринг машинасы лентаның бойымен кез келген бағытта жылжи алады. (немесе лентаны жылжыта алады).
   

Анықтама: [A, S, υ, , σ] бестігі Тьюринг машинасы деп аталады. Мұндағы А – ұяшыққа жазылуы мүмкін болған символдық шекті алфавиті, бір мезгілде енуші әрі шығушы болып табылады: А={a₀ a_1…… a_n}

S- ішкі жағдайлардың шекті жиыны S={s₀ s_{1 …..}s_n } υ –S ішіндегі S β А –дан алынған функция; ξ - А ішіндегі S β А–дан алынған функция, σ- ішіндегі S β A дан алынған функция. Тьюринг машинасы былай жұмыс істейді. S₀ бастапқы жағдайда тұрып, өз жұмысын бастайды. Бірінші симолды оқыған соң

– υ функциясымен анықталатын жаңа ішкі жағдайға өтеді,

– ξ функциясының мәні боп табылатын символды лента ұяшығына жазады,

– σ функциясының мәніне сәйкес лентаны оңға (П), солға (Л), не өз орнында қалып жұмысты тоқтады (ОСТАНОВ).

Осылайша, машина жұмысы келесі циклді қайталаудан тұрады: ұяшықтан симолды оқу, жаңа симолды шығару, печаттау, лентаны солға не оңға жылжыту, не тоқтау. Лента 2 бағыт бойынша шексіз, бірақ басында белгілі бір ұящықтардың шекті саны толтырылған болады.

Мысал: Төмендегі берілген Тьюринг машинасы, енуші 0 және 1 – дің тізбегін оқып, бірліктер саны жұп болса Ж – ны, егер тақ болса Т – ны шығарады. 0 және 1 тер қатарының алдында да, артында да бос ұяшықтар бар. Бос ұяшықты # белгісімен белгілейміз. Ж және Т символдары енуші қатардан кейінгі бірінші бос ұяшыққа печатталады.

Сонымен алфавит мынадай көрініске ие:

A = {#, 0, 1, Ж, Т}.

ішкі жағдай: S={S₀ S₁ S₂}; S₀ – бастапқы жағдай, ОСТАНОВ сигналы берілсе машина тоқтайды.

 : (s₀, 0) a s₁

ξ: (s₀, 0) a 0

σ : (s₀, 0) a Л

(s₀, 1) a s₂ (s₀, 1) a 1 (s₀, 1) a Л

(s₁, 0) a s₁ (s₁, 0) a 0 (s₁, 0) a Л

(s₁, 1) a s₂ (s₁, 1) a 1 (s₁, 1) a Л

(s₂, 0) a s₂ (s₂, 0) a 0 (s₂, 0) a Л

(s₂, 1) a s₁ (s₂, 1) a 1 (s₂, 1) a Л

(s₀,#) a s₀ (s₀, #) a # (s₀, #) a Л

(s₁,#) a s₁ (s₁, #) a Ж (s₁, #) a ОСТАНОВ

(s₂,#) a s₂ (s₂, #) a Т (s₂, #) a ОСТАНОВ

Лекция 9

Тақырыбы: Шекті автоматтардың формальді анықтамасы

1. 
   Шекті автоматтардың формальді аныќтамасы
   
2. 
   Детерминирлі шекті автомат
   

1. ¤ткен сабаќтарда айтылып µткендей грамматика – б±л тудыратын ж‰йе. Автомат – б±л формальді ќабылдаушы ж‰йе. Автомат берілген грамматика эквивалентті деп атлады, егер тек осы грамматика тудыратын тілді ѓана толыќ ќабылдайтын болса. Шекті автомат – тілдер мен ж±мыс істеуде ќолданылатын ењ ќарапайым механизм. Б±л танушыныњ т±раќты жады ±яшыќтарыныњ жиыны бар. Ал басќару ќ±рылѓысы енуші лента бойымен оњѓа ѓана жылжи алады жєне жады жаѓдайын µзгерте алады. Шекті автоматтыњ негізгі бµлігі – б±л µту функциясы. ¤ту функциясы кез келген аѓымдаѓы жаѓдай ‰шін жєне кез келген енуші символ ‰шін м‰мкін болѓан µтулерді аныќтайды. Бірден бірнеше єр т‰рлі автомат жаѓдайларына µту м‰мкіндігі де бар, яѓни танушыныњ басќару ќ±рылѓысы детерминирлі емес болуы да м‰мкін.

Детерминирлі емес дегенді былай ±ѓу керек: егер берілген жаѓдайда єр т‰рлі жаѓдайѓа µту м‰мкіндігі бар болса, онда єр бір жања жағдай ‰шін автоматтыњ бірнеше кµшірмесі ќ±рылады ( дайындалады). Тізбек тілге тиісті деп есептелінеді, егер ќадамдар ќатарларыныњ ењ ќ±рыѓанда бір (бір ќадамдар ќатары) соњѓы, аяќтаушы жағдаймен аяќталса.

Енді шекті автоматты формальді аныќтамасын келтіреміз:

ША = ( Q, Σ, б, q _0, F) бестігімен аныќталады.

М±нда:

• 
  Q – Жағдайлардыњ шекті жиыны.
  
• 
  Σ – м‰мкін болѓан енуші символдардыњ шекті жиыны ( енуші алфавит ).
  
• 
   - басќару ќ±рылѓысын ќимылын (поведение) аныќтайтын P(Q) жиындаѓы Q x Σ жиыныныњ бейнесі. (Б±л функцияны µту функциясы деп атайды.) Б±л бейнелеудіњ элементтері ереже деп аталады.
  
• 
  q ₀ € Q – Басќару ќ±рылѓысыныњ бастапќы жаѓдайы.
  
• 
  F  Q – cоњѓы (терминал ) жаѓдайлар жиыны.
  

е
нуші лента : енуші а:€ Σ тізбегі

2. Детерминирлі шекті автоматтар

Детерминирлі шекті автоматты жалпы (детерминирлі емес) шекті автоматтың дербес жағдай ретінде анықтаймыз. Бұған қосымша кейбір анықтамаларды келтіріп өтеміз.

Анықтама: Автомат детерминирлі деп аталады егер (q,а) жиынында кез келген q, а үшін жағдайлар саны 1-ден артпаса. Егер (q,а) єрдайым дєл 1 жаѓдайдан т±рса (яѓни аныќталмаѓан ауысулары жоќ), орнда автоматты толыќ аныќталѓан деп атайды.



Аныќтама: алфавитінен ќ±рылѓан W = а₁... а_к сµзін М=(Q,) шекті автоматты µткізеді, егер мынадай q₁,q₂,…,q_n жаѓдайлар ќатары бар болса; q₁= q_o, q_n F жєне кез – келген i,j ‰шін

1 I(q_i a_j) = q_{i + 1}