Лекция 3. Тақырыбы: Грамматика класстары және оларды танушылар. Регуляр грамматика

Лекция 3.

Тақырыбы: Грамматика класстары және оларды танушылар. Регуляр грамматика

1. 
   Грамматикаларды классификациялау. Хомскийдің формальдық тілдер иерархиясы
   
2. 
   Грамматика класстарын танушылар
   
3. 
   Регуляр грамматика
   

1. Өткен сабақтардан грамматиканы G=(V_T,V_N,P,S) төрттігі түрінде анықталғаны белгілі. Мұндағы Р ережелердің ерекшеліктеріне қарай грамматикаларды 4 түрлі классқа бөледі. Грамматикаларды бұлайша классификациялау Хомський сирархиясы деп аталады. (Авторлық атымен аталған.)

-Егер Р-ғы ереже Ах В не А х түрінде болса, онда оң жаққа қарай реттелген немесе регуляр грамматика деп. аталады. Мунда А,В- терминал емес, ал Х-терминал.(Бос болуыда мүмкін)

-Егер Р-ғы ереже Аα (мұнда А-терминал емес, α-терминал не терминал емес болуыда мүмкін) түрінде берілсе, онда грамматиканы контексті бос деп. аталады.

-Егер Р-ғы барлық ережелер α→β болса, онда грамматиканы контексті тәуелді деп. аталады. Мунда │ά│≤│β│.(α,β –терминал емес не терминал.)

-Егер грамматика жоғарыда келтірілген 3шектеудің ешқайсысын да қанағаттандырмайтын болса, онда жалпы түрдей деп аталады.

Шартты түрде Хомський сирархиясын былайша бейнелеп көрсетуге болады:

Сонымен, грамматика класстары бірін-бірі өз іштеріне алады, яғни барлық контексті бос грамматикалар контексті тәуелді грамматикаларға жатады. Ал барлық контексті -тәуелді грамматикалар жалпы түрдегі грамматикалар болып есептеледі. Бұдан бөлек і типі не тиісті бірақ і+1 типіне тиісті болмайтын тілдерде бар.

Мысалы, G₃ тілі контексті –тәуелді болып табылғанмен, контексті-бос емес, яғни бұл тілі тудыратын контексті –бос граматика жоқ.

-О типті грамматика –ең күрделісі, ережелер түріне ешқандай шектеу қойылмайды.

-1 типті грамматика –мұнда символ тізбегін ауыстыру мүмкіндігі оның контексі арқылы анықталады.

-2 типтегі граматика -ереженің сол жағындағы бейтерминалдар кез-келгеніне ауыстырылуы мүмкін.

-3 типтегі грамматика -ең шектелген, ең қарапайым грамматика.
2. Әр түрлі грамматика класстарын танушылар.

Әрбір классқа өз танушысы сәйкес қойылады:

-Шектеусіз грамматикамен берілген берілген тіл, Тьюринг машинасымен танылады.

-Контексті тәуелді грамматикамен берілген тіл, сызықты шектелген автоматтармен (контекстке сезімтал) танылады.

-Оң жақ сызықты (регуляр) тілдер шекті автоматтар арқылы танылады.

Танушы деп қайсыбір жиынды (біздің жағдайда- тіл) анықтауға мүмкіндік беретін жалпыланған алгоритм деп ұғамыз. Ол өзінің жұмысы барысында келесі компоненттерді пайдаланады: енуші лента, шектелген жадысы бар басқару құрылғысы және қосымша жады. Әдетте, басқару құрылғысы енуші лентада жазылған мәліметті оқып және енуші лента бойымен алға жылжиды. Кейде артқа да жылжуы мүмкін. Оқу кезекті символды көрсететін енуші тиек (головка) көмегімен жүзеге асады. Танушы жады жағдайында өзгерте алады. Жады стек түрінде (магазин деп те аталады.) не сызықты орналасқан ұяшықтарды шектелген тізімі (жиыны) түрінде ұйымдастырылуы мүмкін.

Егер енуші лентаға берілген тізбек танушы бірқатар қадамдарды орындауға мүмкіндік берсе, және танушы соңғы жағдайына келіп тоқтаса, онда тізбек берілген тілге тиісті деп есептеледі. Тіл осылай танылады.

3. Регуляр грамматикалар.

Грамматикалардың ең қарапайым әрі ең шектеген типі –регуляр грамматиканы қарастырамыз.

Кейбір мысалдар:

Идентификатор (БНФ формасында беріледі).

<идент>: : =<әріп> <идент>: : = <идент> <әріп> → <идент> : : =

= <идент> <цфр> <әріп> : : = а |b|...|= <цфр> : : 0|1|...|9

G=(V_T,V_N, P,S) V_T={S, E, OP, i } V_N={, <идент>, +, -, *, /}

Р={ S→ iS→ i EE→ OPSop→+op→ -op→ *op→ /i→< сан>і→<идент> }

Осы жақшасыз өрнектер грамматикасын БНФ түрінде беруге болады.(бұл қатаң түрде болмаса да айтарлықтай көрнекті).

: : =< сан>|<идент >|: := : : = + | - | * | / <сан>: : =< цфр >
Z : : = UO |V1: : =Z1|1V : : =ZO|0

Бұл грамматика тудыратын тіл 01 не 10 жұптарынан түзілген қатарлардан тұрады, яғни

L(G)={B^h|h>0} мунда B={01¸10}

Жоғарыдағылардан сәл ғана күрделірек объектіде (мысалы, жақшасы бар арифметикалық өрнек) онда регуляр грамматикалардың өте шектелгендігі себепті →N ді қарастыра алмаймыз.

Мысал:

Арифметикалық өрнек (жақшасы бар)

G₀=( { Е, Т, Ғ},{a,+, *, (, ),#}Р, Е)

Р={Е→Е+Т |Т Т →Т*F |F F→(Е)|a}

Бұл енді регуляр емес. Бұл контексті - бос грамматика.

Шектелгендігіне қарамастан регуляр грамматикалар компиляторлар теориясында маңызды орын иелейді. Олар компилятордың бірінші бөлігі-сканерді жүзеге асыру үшін жеткілікті. Өйткені, сканер идентификатор және константа (тұрақты сияқты қарапайым объектермен жұмыс істейді.

Сонымен, регуляр тілдердің фразаларын (сөйлемдерін) тудыра аламыз. Алайда біздің мақсатымыз тудыру емес, сөйлемдерді тану. Сондықтан, келесі сабақта тиімді танушы механизмдердің бірі – шекті автоматтармен танысамыз.

ТАРАУ 2. Шекті автоматтар

Лекция 4,5

Таќырыбы: Шекті автоматтар

1. 
   Шекті автоматтардың формальді аныќтамасы
   
2. 
   Детерминирлі шекті автомат
   
3. 
   Шекті автоматты Мур диаграммалары арқылы бейнелеу
   
4. 
   Детерминирлі емес шекті автомат
   

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}

Аныќтама: L тілі шекті автоматпен танылады, егер Lтілініњ єрбір сµзі шекті автоматпен µткізілсе.
Аныќтама: Шекті автоматтарды ауысу диаграммалары кµмегімен бейнелеп кµрсету ќолайлы.
Мысалдар:

1. Айталыќ детерминирлі шекті автомат былай берілсін::

ША = (Q,, , q_a F)

Q = { S, A, B, q_f}, = {0.1}

= {SO q_f, SO A, A1B, BO  q_f , BO  A}

Ауысу диаграммасы былай бейнеленеді.

1
. БНФ формасында берілген жєне ДША т‰рінде берілген идентификатор ±ѓымын ќарастырайыќ

<идент>:: = <єріп> <идент> :: = <идент><єріп><идент> ::= <идент><цифр><єріп>:: = ab:.. = <цифр> ::= <єріп><цифр>
:

	1	2	3
<әріп>	2	2	-
<цфр>	4	2	-
<соңы>	4	3	-
<әйтпесе>	4	-	-

Матрица қатарлары енуші символдар, бағандары автомат жағдайы.

Бұл матрицаның кейбір элементері- артық. Дәлірек 3-баған тіпті керегі жоқ. Мұндай “артық” жағдайлар қателер тексеру (диагностикасы үшін) қызмет етуї мүмкін. Енуші алфавит-бұл автомат қабылдай алатын объект. Автомат оларды өзара ажыратуға айталық, әріппен цифрларды айыруы міндетті емес.

2. Арифметикалық өрнек (жақшасыз)

: : =/<идент>: :=: :=+\ -\ *\ / : <цфр>: :=<цфр>

жүктеу/скачать 1.44 Mb.

Достарыңызбен бөлісу: