Лекция Тақырыбы: Алфавиттер, тізбектер және тілдер



жүктеу 0.83 Mb.
бет1/13
Дата24.04.2016
өлшемі0.83 Mb.
түріЛекция
  1   2   3   4   5   6   7   8   9   ...   13
: CDO -> 2013-2014 -> Avtom -> Data
Data -> Лекция: 30 сағат лбс: 15 сағат С¤Ж: 45 сағат обс¤Ж: 45 сағат Барлық сағат саны: 135 сағ
2013-2014 -> Лабораториялық сабақтардың әдістемелік нұсқауы Пән: Омыртқалылар зоологиясы
2013-2014 -> Лекция: 30 сағат Практикалық: Лаборатория: 15 сағат обсөЖ: 45 СӨЖ: 45 Барлық сағат саны: 135 сағат
2013-2014 -> Курс жұмысын орындауға арналған әдістемелік нұСҚАУ
2013-2014 -> Лабораториялық сабақтардың Әдістемелік нұСҚауы пән Компьютерлік желілер Мамандық
2013-2014 -> Бағдарламасы Жетісай 20 ж мемлекеттік емтихан бағдарламасы құрастырған: Р. А. Кошкаров Кафедра мєжілісінде қаралған
2013-2014 -> Лекция:: 30 Лабораториялық: 15 Обсөж 45 СӨЖ
2013-2014 -> Лекция:: 15 Семинар: 13 СӨЖ: 62 Барлық сағат саны: 90 Аралыќ баќылау (АБ)- 60балл
2013-2014 -> Лекция: 30 сағат Лаборатория: 30 сағат обсөЖ: 60 сағат Барлық сағат саны: 180 сағат

Лекция 1.

Тақырыбы: Алфавиттер, тізбектер және тілдер

1. Алфавит. Тізбектер

2. Тілдер

3. Тілдерді өрнектеу


1. Алфавит. Тізбектер

Алдымен алфавит ұғымын енгізйік . Алфавит деп символдардың кез-келген жиынын атаймыз. Алфавит шекті болуы және санақты болуы міндетті емес, алайда практикада ол шекті болады. Алфавиттің екі мысалы: 26 үлкен және 26 кіші латын әріптері, екілік алфавит деп аталатын {0,1} жиыны.

Егер бірінен соң бірін орналастырып символдар қатарын жазып шықсақ онда бұл символдар тізбегі болады. Мысалы, 01011 – екілік {0,1}алфавиттегі тізбек. Сөз және қатар терминдері (кейде сөйлем) тізбек терминінінің синонимі ретінде жиі қолданылады.

Бос тізбек деп аталатын тізбек жиі кездеседі, сондықтан да оны арнайы е әрпімен белгілейді. Бос тізбекте ешқандай символ болмайды.
Анықтама. Е алфавитіндегі тізбек формальді түрде былай анықталады.:


  1. е – Е алфавитіндегі тізбек,

  2. егер х - Е алфавитіндегі тізбек болса және а символы Е-ге тиісті болса , онда ха – Е алфавитіндегі тізбек,

  3. у – Е алфавитіндегі тізбек бола алады, егер оған қатысты 1. немесе 2. пункттері дұрыс болса.

Кейінірек қажет болатыны үшін тізбекке қолданылатын амалдарды анықтайық. Егер х және у тізбектер болса, онда ху – х пен у –ң конкатенациясы деп аталады. Мысалы, х=аb, у=сd, онда xy=abcd. Кез-келген х тізбегі үшін хе = ех=х.

х Тізбектің айналуы деп (хR деп белгілейміз) реті кері қарай жазылған х тізбегін атаймыз, яғни, егер х =а1...аn, болса, мұндағы аі-ң барлығы символдар, онда хR = аn...а1. Бұдан бөлек, еR =е.

Айталық х, у, z – қайсыбір Е алфавитіндегі кез-келген тізбектер. ху тізбегінің префиксі (не басы) деп х-ті айтамыз, ал суффиксі (не аяғы) деп у-ті айтамыз. у-ті хуz тізбегінің ішкітізбегі деп атаймыз. Тізбектің префиксі және суффиксі оның ішкітізбектері боп табылады. Бос тізбек кез-келген тізбектің префиксі, суффиксі және ішкі тізбегі боп табылатындығын айта кетеміз.

Егер х≠у және х – у-ң префиксі (суффиксі) болса, онда у тізбегінің өз (өзінің) префиксі (суффиксі) деп аталады.

Тізбек ұзындығы – бұл ондағы символдар саны, яғни, егер х = а1...аn, мұндағы аі –лер символдар, онда х тізбегінің ұзындығы n-ге тең.

х тізбегінің ұзындығын |x| -пен белгілейміз. Мысалы, |аав| =3 және |е| =0.
2. Тілдер
Анықтама. Е алфавитіндегі тіл деп Е-дегі тізбектер жиынын айтады. Кез-келген тіл ұғымы бұл анықтамаға дұрыс келеді, Фортран, Паскаль, тіпті ағылшын тілі де.
Мысал 10. Е алфавитіндегі қарапайым тілдерге мысал клтірейік. Бос жиын Ǿ - бұл да тіл. Бос тізбек қана тиісті болған жиыны да тіл боп саналады. Ǿ мен {е}-ң екі түрлі тілдер екенін ескертеміз.
Анықтама. Е* арқылы Е алфавитіндегі барлық тізбектерді, соның ішінде е-ден құралған жиынды белгілейміз. Мысалы, егер Е екілік алфавит {0,1}болса, онда

Е* ={е, 0,1, 00, 01, 10, 11, 000, 001, ...} болады.

Е алфавитіндегі әрбір тіл Е* жиының ішкі жиыны болып табылады. Е алфавитіндегі е-ден басқа барлық тізбектер жиына Е1 деп белгіленеді.
Мысал 11. L1 тілі айталық, нөл не одан көп а символынан құралған тізбектерден тұрсын. Оны былай белгілеуге болады: {ai | i≥0}. L1 ={а}* екендігі көрініп тұр.
Анықтама. Егер қайсыбір L тілдегі ешқандай тізбек осы тілдегі басқа ешқандай тізбектің өз префиксі (суффиксі) болып табылмаса, онда бұл L тілін префиксті қасиетке ие деп атайды.

Мысалы, {a}* префиксті қасиетке ие емес, ал, {aib | i≥0} бұл қасиетке ие.


3. Тілдерді өрнектеу
Бізге тілдерге түрлі амалдар қолдануға жиі тура келеді. Негізгі амалдарды қарастырамыз.

Тіл дегеніміз жиын болғандықтан жиынға қолданылатын біріктіру, қиылысу, айырмасын табу, толықтыру амалдары тілдерге де қолданылады. Конкатенация амалын тізбектерге қолданған сияқты тілдерге де қолдануға болады.



Анықтама. Айталық L1 – Е1 алфавитіндегі тіл, ал L2 – Е2 алфавитіндегі тіл болсын. Онда L1 және L2-ң конкатенациясы (не көбейтіндісі) деп аталатын L1L2 тілі – бұл {ху | xЄ L1 және xЄ L1 } тілі.
Кейбір жағдайларда тілдегі тізбектердің қалаған санымен конкатенация жасауға тура келеді. Бұл үшін тілдің итерациясы ұғымымен танысу қажет.
Анықтама. L тілінің итерациясын L* арқылы белгілейміз, ол былайша анықталады:

  1. L0={e},

  2. Ln=LLn-1 , n≥1 үшін

  3. L*=Ln .

L тілінің позитивті итерациясы L+ деп Ln тілін айтамыз. L+= LL*= L*L және L*= L+{e} болатынын ескерте кетеміз.



Лекция 2.

Тақырыбы: Формальді грамматика

1. Тілді анықтау мәселесі

2. Грамматиканы анықтау. Терминал және терминал емес белгілер. Шығару ережелері

3. Бэкустың нормаль формалары.


1. Тілді анықтау мәселесі

1. Табиѓи не жасанды басылым кез – келген тілде ќарым – ќатынас жасау сµйлем арќылы ( дєлірегі фраза) ж‰зеге асады. Сµйлем осы тіл сµздерініњ шекті тізбегінен т±рады. Сµйлемді ќ±ра білу керек. Егер сµйлемді ќ±ру механизімі жєне оныњ д±рыстыѓын тексеретін механизім ( аныќтау, ( тану) механизімі) бар болса, онда осы тілдіњ ќайсыбір теоремасы бар болѓаны.

АНЫЌТАМА :  тілі - А алфавитінен т‰зілген ±зындыѓы шекті тізбектер жиыны.

Компиляция жасау барысында бірінші туындайтын мєселелердіњ бірі б±л ќарастырылатын програмалау тілін аныќтау. Тілді ќалай беруге болады ?

Біріншіден ( берілген қандайда бір А алфавитінен түзілген) тізбектер саны шектеулі болатын тілдерді ќарастырѓан жаѓдайда барлыќ м‰мкін болѓан тізбектерді айќындап беруге болады.

Екіншіден тізбектіњ ±зындыѓына ешќандай шектеу ќоймайтын тілдер де бар. М±ндай жаѓдайда тілдіњ ќандайда бір шекті бейнесін тілді бейнелейтін шекті ережелер жиынына беруге болады. Жалпы тілдерді беруге ыњѓайлы т‰рлі математикалыќ формализмдер бар. Солардыњ ішінде кењ таралғаны – грамматика деп аталатын механизм.

Басќаша айтќанда грамматика – тілді бейнелейтін математикалыќ ж‰йе.

Грамматика ќайсыбір ережелер кµмегімен тілге тиісті барлыќ тізбектерді бере алады. Грамматиканы тілді беруге ѓана емес, тілді тану ‰шін де пайдалануға болады. Оныњ артыќшылыѓы да осында. Яѓни енуші ( беріліп отырѓан ) тізбектіњ аныќталып отырѓан тілге сєйкестігін ( тиістілігін) грамматика кµмегімен аныќтауѓа болаы.


2. Грамматиканы анықтау. Терминал және терминал емес белгілер. Шығару ережелері

Грамматика келесі компоненттер арќылы аныќталады.



    • Терминал символдар. ( алфавит)

    • Терминал емес символдар. (кейде ±ѓымдар деп те аталады)

    • Шыѓару ережесі (тудыру)

    • Бастапќы символ.

Грамматиканы бейнелеуді (баяндау) тілдік алфавиттік аныќтаудан бастау керек. Ол    т‰рінде болады. Б±л ережелер кµмегімен тілдіњ барлыќ тізбектері ќ±ралады ( туындайды). Б±л ережелердіњ оњ жєне ол жаќтарында арнайы терминал емес символдар кездесуді м‰мкін ; шыѓару барысында терминал емес символдар сєйкес ережелер кµмегімен терминалсимволдарѓа ауыстырылады. Грамматикаѓа б±лардан бµлек бастапќы символ не аксиома да ену керек. Тілдіњ барлыќ сµйлемдерді бастпќы символда баталады.

Енді грматиканыњ аныќтамасын формальді т‰рде жазып шыѓу ‰шін тµмендегі белгілеулер ќажет болады.



    • Егер А алфавит болса, онда А* арќылы А алфавитіне енген символдардан т‰зілген  тізбектер ( ќатар ) жиынын белгілейміз. Б±л жиынѓа бос тізбекте ( оны е арќылы белгілейміз ) енеді.

Мысалы А=  а, в, с  Онда А* =  е, а,в,с,аа,ав, ас,вв,вс,сс,...авс,...

    • белгілейміз.

АНЫЌТАМА : G граматика мына тµрттік арќылы аныќтлады : G = ( Vт, VN , Р, S ) м±нда,

Vт – терминал символдардыњ шекті жиыны.

VN – терминал емес символдардыњ шекті жиыны

Vт U VN =  ( яѓни Vт мен V  ќиылыспайды, екеуініњ ортаќ символдары жоќ)

Р – ( , ) т‰ріндегі ережелердіњ шекті жиыны. М±нда,   V +,   V* ( V= Vт U VN )

S – бастапќы символ, S υ VN

Мысалы. 1)[ 0n 1 n / n ≥ 0 ] тілді тудыратын грамматика былай белгіленеді.

Ġ=({ 0,1}, { S}, Р, S), м±нда Р = { S→0S1, S→e}



3. Бэкустың нормаль формалары.

Қазіргі таңда информатикада формальді тілдерді тудыратын бірнеше граматиканы беру әдістері жасалынған. Қарапайым әдістердің бірі (әрі көп жерде қолданылатын) Бэкустің нормаль формалары деп аталатын әдіс.

Мысал арқылы қарастыралық. Айталық 2-лік цифр (0,1) және үтірден тұратын х алфавиті берілсін. Осы алфавит арқылы барлық рационал теріс емес екілік сандардан (бүтін, бөлшек) тұратын тіл құру керек. Мұндай тіл құру үшін Бэкус әдісінде мынандай екі (мета ұғым) ұғым беріледі.

“Сол жақ” Оң жақта келтірілген форма мәндерінің кез-келгенімен анықталады. n деген сөйлемді ынғайлылық үшін : : = белгісімен береміз.



<бүтін сан>: : =<0><1><0> <бүтін сан><1> <бүтін сан>

<екілік сан>: :=<бүтін сан> <,> <бүтін сан>

Мұнда  - немесе деген мағынаны білдіреді.

Жоғарыдағы анықтамаларға сәйкес дұрыс сөздер, яғни 2-лік сандар деп төмендегілерді айтуға болады: 01, 0010, 00.



  1   2   3   4   5   6   7   8   9   ...   13


©netref.ru 2017
әкімшілігінің қараңыз

    Басты бет