Z A 79 Теория пулеметтер: 230101 мамандығы бойынша тәжірибелік сабақтарға әдістемелік нұсқаулар / Т.З. Аралбаев,<...>Әдістемелік нұсқаулар келесі мәселелерді қарастырады: көрсету әдістері логикалықфункциялары ( LF); алгебралық түрлендіру LF; минимизациялау әдістері Квинжәне МакКласский карталарды пайдалана отырып Карно; пішіндер тапсырмалар финал пулеметтер; синтез комбинациялық схемаларнегізінде « ЖӘНЕ ЕМЕС” (“НЕМЕСЕ ЖОҚ") қосулы логикалық элементтері K155 және K561 сериялары.<...>Әдістемелік нұсқаулар курс бойынша тәжірибелік сабақтарды ұйымдастыруға арналған. Теория пулеметтер» 230101 «Компьютерлер, кешендер, жүйелер және желілер» мамандығының 2 курс студенттеріне арналған.<...>Карталардағы логикалық функцияларды азайту Карно ……………………….. <...>41 3 Кіріспе Бұл әдістемелік нұсқаулар «Теория» пәнінің негізгі бөлімдерінің бірінде практикалық сабақтарды өткізуге арналған материалды қамтиды. пулеметтер” – “Логикалық негіздері сандық пулеметтер”. <...>1.1 LF көрсетудің кестелік түрі Логикалық функция ең айқын түрде берілген кестелер шындық(TI) және карталар Карно. <...> Кесте шындық- Бұл кесте, онда xi (i = 1, n) аргумент мәндерінің әрбір екілік жиыны Y = f (x1, x2,..., xi,..., xn) функциясының мәнімен байланысты бұл жиынтық. <...>Карно картасы - n 2 ұяшықтан тұратын тікбұрышты кесте, әрбір ұяшық i -ші жол мен j -ші бағанның қиылысында орналасқан, ai және aj - құрамдас элементтер екілік жұмысқа қабылдау n – жергілікті LF.<...>1) тігінен немесе көлденеңінен іргелес жатқан ұяшықтардың кез келген жұбы, сондай-ақ картада тігінен немесе көлденеңінен симметриялы орналасқан ұяшықтардың кез келген жұбы сәйкес келеді. екілік жинақтар, тек бір айнымалының мәнімен ерекшеленетін (яғни бір цифрмен ерекшеленеді);<...>2) жылы жасушалар карталарКарно сәйкес жиынтықтағы функцияның мәндерін көрсетеді;<...>3) жолдарды белгілейтін аргументтердің екілік жиындары, сондай-ақ бағандарды белгілейтін аргументтердің екілік жиындары<...>

Theory_automata.pdf

ӘОЖ 004.3(076.5) ББК 32.97я73 А 79 Рецензент: т.ғ.д., профессор А.М. Пишухин Аралбаев, Т.З.А 79 Автоматтар теориясы: 230101 мамандығына практикалық сабақтарға арналған әдістемелік нұсқаулар / Т.З. Аралбаев, И.В. Жукалина. - Орынбор: ОМУ мемлекеттік оқу орны, 2009. – 41 б. Әдістемелік нұсқаулар келесі мәселелерді қарастырады: логикалық функцияларды бейнелеу әдістері (ЛФ); LF алгебралық түрлендіру; Карно карталарын пайдалана отырып, Квин және МакКласскийдің минимизациялау әдістері; ақырлы күй машиналарын көрсетуге арналған формалар; K155 және K561 серияларының логикалық элементтері бойынша «ЖӘНЕ-ЕМЕС» («НЕМЕСЕ-ЕМЕС») негізіндегі комбинациялық схемаларды синтездеу. Әдістемелік нұсқаулар 230101 «Компьютерлер, кешендер, жүйелер және желілер» мамандығының 2 курс студенттеріне «Автоматтар теориясы» курсы бойынша практикалық сабақтарды ұйымдастыруға арналған. ҚБҚ 32.97я73 © Аралбаев Т.З., 2009 © Жукалина И.В., 2009 © ОМУ ММ, 2009 2

2-бет

Мазмұны Кіріспе................................................. ... ................................................. ......... ...................4 1 Практикалық сабақ No1. Логикалық функцияларды бейнелеу әдістері……………………………….….… 5 1.1 ЖЖ ұсынудың кестелік түрі…………………………………………………………………………….5 1.2 ЖҚ ұсынудың аналитикалық формасы ……… ……………………………….8 2 №2 тәжірибелік сабақ. Логикалық функциялардың формулаларын алгебралық түрлендіру………….…..12 2.1 Буль алгебрасының заңдары…………………………………………………………………………………………12 2.2 Буль алгебрасының аксиомалары мен теоремалары ………… …………………………...12 3 №3 тәжірибелік сабақ. Квин және МакКласскийдің минимизациялау әдісі……….………………………….15 3.1 Барлық жай импликанттарды табу……………………………………..15 3.2 Квиннің қамту кестесін құру матрицалар……………………………16 3.3 Функцияның минималды жабуын табу……………………………………………………………………….16 3.4 LF минималды түрін алу……… …… …………16 4 №4 тәжірибелік сабақ. Karnaugh карталарын қолдану арқылы логикалық функцияларды минимизациялау………………………..20 4.1 Ең аз DNF құру…………………………………………21 4.2 Ең аз CNF құру… ……………………………………………………………………………22 4.3 Толық анықталмаған ЖЖ-ны минимизациялау………………………………..23 5 Практикалық сабақ № 5 Ақырлы мәндерді көрсету формалары күй машиналары…………………………………….……..25 6 Тәжірибелік сабақ №6 «ЖӘНЕ-ЕМЕС» («НЕМЕСЕ-ЕМЕС») негізінде комбинациялық тізбектердің синтезі………. ………30 7 Практикалық сабақ № 7. K155 және K561 серияларының логикалық элементтеріне негізделген комбинациялық схемалардың синтезі……………………………………………………………………………………………… …35 Пайдаланылған көздер тізімі.. ................................................. ................ ...............40 Қосымша………………………………………… ……………………………………41 3

3-бет

Кіріспе Бұл әдістемелік нұсқаулар «Автоматтардың теориясы» пәнінің негізгі бөлімдерінің бірі – «Цифрлық автоматтардың логикалық негіздері» бойынша практикалық сабақтарды өткізуге арналған материалды қамтиды. Сабақтардың мақсаты логикалық функцияларды түрлендіру әдістері мен көрсету формалары, сондай-ақ комбинациялық схемаларды синтездеу әдістемесі туралы білімді практикалық түрде бекіту болып табылады. Әрбір практикалық сабақта сабақтың мақсатын баяндау, тақырып бойынша қысқаша теориялық материал, типтік мысалдар, тест сұрақтары және өздік жұмысқа жаттығулар кіреді. Сабақты өткізу алдында студент оның мақсатын түсініп, бақылау сұрақтарына жауап беруі керек. Сабаққа өз бетінше дайындалу үшін студенттерге пайдаланылған әдебиеттер тізімінде ұсынылған әдебиеттерді оқу ұсынылады. Сабақ барысында мысалдар талданып, нұсқалар бойынша жаттығулар орындалады. Білімді бақылау тест сұрақтарына жауап беру және жаттығуларды орындау нәтижелері бойынша жүзеге асырылады. 4

4-бет

1 Тәжірибелік сабақ No1. Логикалық функцияларды бейнелеу формалары Комбинациялық схемаларды жобалаудың әртүрлі кезеңдерінде қолданылатын логикалық функцияларды (ЛФ) бейнелеудің бірнеше формалары бар, атап айтқанда: ауызша, кестелік, аналитикалық, геометриялық, кубтық. Тәжірибелік сабақтың мақсаты – ЖЖ көрсетудің кестелік және аналитикалық формаларын және ЖҚ кестелік сипаттамасынан аналитикалық сипаттауға көшу алгоритмдерін оқу. 1.1 LF көрсетудің кестелік түрі Логикалық функция ақиқат кестесі (ТИ) және Карнау картасы арқылы барынша анық көрсетілген. Ақиқат кестесі дегеніміз xi (i = 1, n) аргумент мәндерінің әрбір екілік жиыны Y = f (x1, x2,..., xi,...,) функциясының мәнімен байланыстырылатын кесте. xn) осы жинақта. 1.1-кесте мысал ретінде үш аргумент үшін TI функциясын көрсетеді. Y функциясы әрбір жиында 1 немесе 0 мәнін қабылдайды. Егер функцияның мәні анықталмаса, онда TI сәйкес орнына сызықша қойылады. 1.1 кесте – логикалық функцияның ақиқат кестесі N Х1 Х2 Х3 Y 0 0 0 0 1 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 1 7 1 1 1 1 Кейде бірліктер мен нөлдер жиындарының тізімін беретін TI көрсетудің тізімдік формасы пайдаланылады. Сонымен, мысалда қарастырылған функцияны тізім түрінде көрсетуге болады: Y = F Х Х Х) = ∨ (0, 1, 3, 6, 7) Y = ∧ (2, 4, 5) (0 1, 2 , 3 1 5

Реферат Mealy және Moore автоматтары туралы бастапқы ақпарат берілген. Берілген мүмкін жолдарыавтоматтардың бейнелері: жиынтық-теориялық, графиктік, кестелік және матрицалық, автоматтың реакциясы туралы түсініктер және эквивалентті автоматтар. Автоматтардың өзара эквивалентті түрлендіру әдістері ұсынылған. Берілген негізгі ақпаратмикробағдарламалық басқару туралы, микронұсқаулар, микрооперациялар, микробағдарламалар ұғымдары, микропрограммаларды алгоритмдердің графиктік диаграммалары (GDA) түрінде көрсету әдістері, аударма формулалары, алгоритмдердің матрицалық және логикалық диаграммалары. GSA таңбалау әдістері және олардың көмегімен Mealy және Moore автоматтарын құру ережелері келтірілген. Біріктірілген автомат туралы түсінік және оны бейнелеу жолдары берілген. Құрылымдық автоматтардың канондық синтезінің әдістері қарастырылған. RS-, T- және D-флип-флоптар негізіндегі құрылымдық автоматтың жады синтезінің мысалдары келтірілген.

Негізгі ұғымдар мен анықтамалар.
Ең қарапайым ақпарат түрлендіргіші (1.1, а-сурет) кіріске келетін X ақпараттық элементтердің белгілі бір жиынын Y шығысында белгілі бір жиынға көрсетеді. Егер X және Y жиындары шекті және дискретті болса, яғни түрлендіру жүзеге асырылады. уақыт бойынша дискретті моменттерде шығады, онда мұндай түрлендіргіштер туралы ақпарат соңғы трансформаторлар деп аталады. Бұл жағдайда X және Y жиындарының элементтері екілік кодтармен алдын ала кодталады және бір жиынның екіншісіне түрлендіруі құрастырылады.

F: X → Y түрлендіру нәтижесі көбінесе қандай ақпаратқа байланысты емес осы сәткірісінде пайда болды, сонымен қатар бұрын болған оқиғадан, яғни трансформацияның тарихқа дейінгі кезеңінен. Мысалы, дәл сол енгізу – көршіңіздің адам көп автобуста аяғыңызды басқаннан кейін кешірім сұрауы – бірінші рет бір реакцияға, бесінші рет мүлдем басқа реакцияға себеп болады.

Мазмұны
Мұқаба бетін басып шығару
Дәріс 1. Абстрактілі автоматтар теориясының негізгі түсініктері
Дәріс 2. Эквивалентті автоматтар
Дәріс 3. Дискретті құрылғылардың жұмысын сипаттау әдістері
Дәріс 4. Микропрограммалық графикалық диаграмма арқылы абстрактілі автоматтарды құру
Дәріс 5. Құрылымдық автоматтың синтезі
Дәріс 6. Құрылымдық автоматтың жадысы
Дәріс 7. Флип-флоптар көмегімен құрылымдық автомат синтезінің мысалы.
Дәріс 8. Графикалық әдістриггерлердегі құрылымдық автоматтың синтезі.

Тегін жүктеу электрондық кітапыңғайлы форматта қараңыз және оқыңыз:
«Автоматтар теориясына кіріспе» кітабын жүктеп алыңыз, Князков В.С., Волченская Т.В., 2016 - fileskachat.com, жылдам және тегін жүктеп алыңыз.

pdf жүктеп алыңыз
Сіз бұл кітапты төменде сатып ала аласыз ең жақсы бағаРесей бойынша жеткізумен жеңілдікпен.

Pdf файлындағы «автоматтар теориясы» пәні бойынша тамаша қысқаша дәріс жазбалары.

Екілік арифметикалық алгоритмдерді жүзеге асыру үшін цифрлық автоматтардың синтезі

• Сандық машиналар туралы жалпы мәліметтер. Глушковтың үлгісі. Жұмыс істейтін машиналар синтезі
• Таңбасыз сандарды жанама көбейтуді орындау үшін операциялық автоматты синтездеу мысалы
• Басқару машиналарының түрлері. Mealy және Moore автоматтарының құрылымдары.
• Тікелей кодта таңбасыз сандарды көбейту алгоритмі үшін қатаң логикасы бар басқару автоматының (CALA) синтезінің мысалы.

• Дискретті Глушков түрлендіргішінің моделін сипаттаңыз.
• Операциялық автоматтың (ОА) мақсаты қандай?
• Канондық құрылымның процедуралық типіндегі ОА синтезінің кезеңдерін көрсетіңіз.
• Көбейтуді орындау үшін OA синтезін жүргізіңіз (жеңілдетілген
• таңбасыз сандарды жанама көбейту алгоритмі).
• Жанама көбейту алгоритмі арқылы сандарды көбейтуге мысал келтіріңіз.
• Жанама көбейтудің негізгі нұсқаларын (схемаларын) сипаттаңыз.
• Көбейту үшін ОА уақыт диаграммасын тұрғызыңыз. Түсіндіріңіз.
• Варианттар бойынша арифметикалық амалды орындау алгоритмін синтездеңіз.
• Алгоритміңізге сәйкес OA схемасын синтездеңіз.
• Басқару автоматының (CA) мақсаты қандай?
• Ақпараттық және басқару сигналдарының рөлі.
• УА түрлері.
• Қатты логикамен UA синтезінің кезеңдерін атап көрсетіңіз.
• Негізгі флип-флоптарды қарапайым күй машиналары ретінде сипаттаңыз.
• УАЗЛ синтезінің ерекшеліктері қандай әртүрлі түрлерітриггерлер?
• Mealy және Moore автоматтарының құрылымдық диаграммаларын көрсетіңіз. Олардың айырмашылықтары қандай?
• Абстрактілі Mealy және Moore автоматтарының модельдерін сипаттаңыз.
• Абстрактілі ақырлы күй машиналарын сипаттаудың қандай формаларын білесіз?
• Схема бойынша ауысу/шығару кестелері мен автоматтар графиктерін құру
• алгоритм.
• Көбейту алгоритмін орындау үшін UA синтездеңіз (пайдаланыңыз
• таңбасыз сандарды жанама көбейтудің жеңілдетілген алгоритмі) сияқты
• Мили/Мур автоматты.
• Көбейту үшін ОА уақыт диаграммасын құрыңыз. Түсіндіріңіз.
• Опцияларға сәйкес алгоритміңіз үшін UASL схемасын синтездеңіз.

Тұрақты өрнектерді пайдалану (RE). Автоматтарды бағдарламалық қамтамасыз етуді енгізу

• Тұрақты өрнектер және автоматтарды танғыштар туралы түсінік
• Тұрақты өрнектерге жылдам кіріспе (RE). RV диалектілері.
• Бағдарламалауда RT қолдану
• Тұрақты сөз тіркесін құруға мысал
• -мен жұмыс істеу мысалы тұрақты өрнекпайдаланушы енгізген IP мекенжайларын басқару үшін.
• Тұрақты өрнекпен көрсетілген тілді тану үшін детерминирленген автоматтың синтезі және оны бағдарламалық қамтамасыз ету.
• ε – ауысулары бар НКА-ға РФ түрлендіру
• ε-өтулері бар НКА-ны ε-өтусіз НКА-ға түрлендіру
• НКА-дан ε-өтусіз DKA алу
• DFA минимизациясы
• Ғарыш кемесінен РЖ қабылдау
• DFA танушысын бағдарламалық қамтамасыз етуді енгізу

Бірінші бөлімдегі өзін-өзі бақылауға арналған сұрақтар:

• Тұрақты өрнек дегеніміз не?
• RV қайда қолданылады?
• RV тағайындаудың қандай әдістерін білесіз?
• RT көрсетілген тілдерді тану үшін қандай автоматтар қолданылады?
• НКА дегеніміз не? DKA?
• RV көмегімен ғарыш аппаратын тану құралын қалай құруға болады?
• RV көмегімен DKA тану құралын қалай құруға болады?
• Ғарыш аппараттарындағы электронды ауысуды қалай жоюға болады?
• Ғарыш аппаратын танушыны қалай азайтуға болады?
• VS ортасында RT қалай қолданылады?
• .NET Framework жүйесінде RT-ге қалай қолдау көрсетіледі?
• RT арқылы берілген тізбектерді сипаттаңыз.
• Бұл РЖ қандай тізбектерді анықтайды (мысалдар, сипаттамалар).
• Бағдарламалық жүйелерде RT қолдауын енгізу стратегиялары.
• Мәтінді өңдеу бағдарламаларын жазу кезінде RT қолдауын пайдалану жолдары.
• RT көмегімен мәтінді өңдеудің қандай мәселелерін шешуге болады?
• Өздеріңіз білетіндердің тізімін жазыңыз бағдарламалық жүйелер, қолдау көрсететін RV.

білім министрлігі Ресей Федерациясыатындағы Нижний Новгород мемлекеттік университеті. Н.И. Лобачевский

Есептеу математикасы және кибернетика факультеті

«Алгоритмдер теориясы және математикалық логика» курсы бойынша студенттердің өздік жұмыстарына арналған оқу-әдістемелік әзірлемелер

тақырыбын оқу барысында «Ақырлы күй машинасы және тұрақты тіл ұғымдары. Тұрақты тілдердегі операциялар»

Нижний Новгород 2000 ж

Әдістемелік әзірлеме «Қолданбалы информатика» мамандығы студенттерінің «Ақырлы күй машиналары және тұрақты тілдер туралы түсініктер» тақырыбының материалы бойынша өздік жұмыстарына арналған. Тұрақты тілдердегі амалдар», «Алгоритмдер теориясы және математикалық логика» оқу курсының бөлігі болып табылады. Формальды тіл түсінігі және формальды тілдердегі операциялар, оның ішінде негізгі жиынтық-теориялық операциялар енгізіледі. Ақырлы автомат туралы түсінік берілген (детерминирленген және детерминирленген емес нұсқаларда); тұрақты тілдер – соңғы күй машиналарымен танылатын тілдер класы. Амалдардың, бірігулердің, қиылысулардың, толықтырулардың, жалғаулардың және итерациялардың тұрақты тілдер класынан шықпайтыны көрсетілген. Ақырлы күй машиналарының синтезінің сәйкес алгоритмдері берілген.

Құрастырушы:

ҰНН есептеу математикасы және математика факультетінің информатика және ғылыми зерттеулерді автоматтандыру кафедрасының оқытушылары доцент, т.ғ.д. Коган Д.И. және ассистент Бабкина Т.С.

1. Тіл туралы түсінік, тілге мысалдар, тілдерге амалдар.

Алфавит — символдардың еркін бос емес соңғы жиыны; ерікті алфавиттің таңбалары әріптер деп аталады. Мысал ретінде біз орыс алфавитін (тыныс белгілерінсіз немесе онсыз), латын әліпбиін, осы алфавиттердің тіркесімін және ондық немесе екілік санау жүйелерінің көптеген цифрларын көрсетеміз. Жалпы, біз әліпбиді A = жиыны ретінде анықтаймыз (a 1, a 2, ..., a n); А әліпбиінің әріптерінің арасында арнайы бос әріп болуы мүмкін (бос әріп әдетте e деп белгіленеді (ағылшынша «бос» аббревиатурасы - бос);

А әліпбиіндегі сөз оның әріптерінің ерікті соңғы тізбегі; бір әріп осы реттілікте бірнеше рет пайда болуы мүмкін. α сөзінің ұзындығы (белгіленуі l(α)) бұл сөздегі әріптер саны. Арнайы λ символы ұзындығы нөлге тең жалғыз сөзді (бос сөз) білдіреді; бос сөз бен бір бос әріптен тұратын е сөзін ажырату керек; e (кеңістік) сөзінің ұзындығы біреуге тең. A = (a 1, a 2, ..., a n) әліпбиінде ұзындығы l әр түрлі n l сөздерді жазуға болады, мұндағы l = 0, 1, 2, .... А әліпбиінің барлық сөздерінің жиыны А * белгісімен белгіленеді. А * жинағында бос сөз де бар екенін ерекше атап өтейік. А әліпбиінің барлық сөздері жиынының кардиналдығы санаулы.

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

αλ= λα= α, αλβ= αβ.

A әліпбиіндегі тіл - A *-дан L сөздерінің ерікті жиыны. Тілді L ақырлы деп атаймыз, егер оның құрамында сөздердің шекті жиыны болса; L тілі шексіз болады, егер оның құрамында шексіз сөздер болса. Орыс тіліндегі барлық сөздердің және ағылшын тіліндегі барлық сөздердің жиынтығы шектеулі тілдердің мысалдары болып табылады. Барлығының жазбалары көп жай сандарондық немесе екілік санау жүйесінде шексіз тіл болып табылады. А әліпбиінің барлық тілдерінің жиынтығы континуумдық кардиналдыққа ие.

А алфавитіндегі L тілі әмбебап деп аталады, егер L=A *. Тіл Л

L жиыны бос болса (L =) оны бос деп атаймыз.

L 1 және L 2 A әліпбиіндегі тілдер болсын. L 1 L 2 және L 1 ∩ L 2 арқылы біз боламыз

сәйкесінше осы тілдердің бірігуін және қиылысуын білдіреді. α сөзі екі тілдің бірлестігіне жатады, егер ол олардың кем дегенде біреуіне тиесілі болса; α сөзі бір тілге де, екінші тілге де тиесілі болса, екі тілдің қиылысына жатады. А алфавитінде L тілі болсын; Бұл тілдің толықтауышын L c деп белгілейік. L c тілі L тіліне кірмейтін А әліпбиіндегі сөздер арқылы жасалады: L c = A *\L. Бірлесу, қиылысу және қосу амалдары негізгі жиынтық-теориялық амалдар болып табылады.

L 1 және L 2 A әліпбиіндегі тілдер болсын. L 1 \L 2 деп белгілейміз

L 1 және L 2 тілдерінің айырмашылығы. A * сөзінен α сөзі L 1 \L 2 тіліне тиесілі болып есептеледі, егер ол L 1 тіліне жатады, бірақ L 2 тіліне жатпайды. Айырмашылық операцияны негізгі теория арқылы көрсетуге болатыны анық

бірнеше амалдар: L 1 \L 2 =L 1 ∩ (L 2 )с.

Сонымен қатар, біз тілдерге бірнеше арнайы операциялар енгіземіз. L 1 және L 2 A әліпбиіндегі тілдер болсын. L 1 ( L 2 тілді білдірсін

келесідей анықталады: α сөзі L 1 ( L 2) тіліне жатады, егер бұл сөзді екі қатарынан бөлікке бөлуге болатын болса ғана

(яғни, α = α 1 α 2 түрінде берілген) бірінші бөлігі L 1 тілінің сөзі, ал екінші бөлігі L 2 тілінің сөзі болатындай етіп берілген. Операциясы ( тілдерді біріктіру (байланыстыру) деп аталады. Таңбасы жиі түсіріліп қалады, содан кейін L 1 және L 2 тілдерінің жалғауы L 1 L 2 жазылады. L 1 L 2 тілі сөздерді қосу арқылы алынады. L 2 тілінің сөздеріне жалғау ретінде ескеріңіз, егер бос сөз ерікті γ сөзіне қосылса, онда L 1 және L 2 тілдері ақырлы болса, онда нәтиже γ сөзі болады. ал бірінші тілде m сөз, ал екінші тілде n сөз болса, онда тіл L 1 L 2. көп дегенде миллион сөзден тұрады L 1, L 2 тілдерінің біреуі бос болса, L 1 L 2 де бос тіл.

Тілді күшке көтеру операциясын енгізейік. Біз сенеміз:

L 0 =(λ);

L1 = L;

L2 = LL; Ln +1 = Ln L, n=2, 3, ...;

осылайша L тілінің L i дәрежесі ұғымы кез келген i =0, 1, 2, 3,

L* =U Li.

i= 0

Енгізілген операция итерация деп аталады. Бос сөз кез келген тілдің итерациясына жататынын ескеріңіз. Бос емес α сөзі L тілінің итерациясына жатады, егер бұл сөзді әрбір бөлік L тіліне жататын етіп бірнеше ретті бөліктерге (ішкі сөздерге) бөлуге болатын болса ғана. Егер L тілі А алфавитінің барлық бір әріпті сөздерінен тұратын болса, онда бұл тілдің итерациясы әмбебап тіл А* болып табылады. Кез келген L тілі үшін бізде (L *)*=L * болатынын ескеріңіз.

Көптеген тілдерде келесі унарлық оператор ()+ кейде қарастырылады:

(L )+ =U L i .

i= 1

L * және L + тілдері бір-бірінен бос сөзде ғана ерекшеленеді. λ сөзі әрқашан L * тіліне жатады. Ол L + тіліне жатады, егер ол L тіліне жататын болса ғана.

2. Ақырлы күй машинасы және тұрақты тіл туралы түсініктер.

Кибернетикада автоматтар – келіп түсетін ақпаратты өңдеуге арналған техникалық немесе бағдарламалық қамтамасыз етілген модульдер. Мемлекеттік машинамүмкін күйлердің шектеулі саны бар және дискретті уақытта жұмыс істейтін модуль. Бұл оқулықта соңғы күй машиналары тіркелген кіріс алфавитінің сөздерін өңдеуге арналған абстрактілі алгоритмдік құрылғылар ретінде зерттеледі. Автомат арнайы таңдалған бастапқы күйден А кіріс алфавитіндегі ерікті α сөзін өңдеуді бастайды деп есептейміз. Дискретті уақыттың әрбір тактілік циклінде оның әсерінен машинаның кірісіне өңделген сөздің келесі әрпі келеді, машина өз күйін өзгертеді; Машина өтетін күй оның алдыңғы күйімен және кіріс сөзінің оқылған әрпімен анықталады. Құрылғы ұзындығы l циклдеріндегі сөзде жұмыс істейді. Машинаның жұмысының нәтижесі оның аяқталғаннан кейін қандай күйде болатынымен анықталады.

Формальды түрде біз К соңғы автоматын жиын ретінде анықтаймыз

K=(Q, A, q0, g, F),

мұндағы Q =(q 0, q 1, q 2, ..., q m) – автомат күйлерінің жиыны; A = (a 1, a 2, ..., a n) – енгізу алфавиті; q 0 – бастапқы күй деп аталатын машинаның арнайы таңдалған күйі; g – соңғы машинаның ауысу функциясы,

ол Q xA → Q типті бейнелеу болып табылады (егер g (q i,a j)=q k болса, онда a j әрпінің әсерінен q i күйіндегі автомат q k күйіне өтуі керек); F - автомат күйлерінің арнайы таңдалған ішкі жиыны, біз оны шартты түрде «жақсы», F Q деп атаймыз.

К автоматы осы сөздегі жұмыстың t циклінен кейін қай күйде болады (мұнда t = 0, 1, 2, ..., p):

qα (0) =q0 ;

q α (1) = g (q α (0), a i 1 )

q α (2) = g (q α (1), a i 2 )

q α (p) = g (q α (p - 1), a i p)

α сөзін q α (р) F болса, K автоматы қабылдайтынын айтамыз.

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

Ақырлы күй машинасын оның ауысу диаграммасы арқылы анықтау ыңғайлы. Диаграмма – төбелері автоматтың күйлерімен бірдей бағытталған бағытталған график; q i төбесінен q k төбесіне дейін оның үстінде a j әрпі жазылған доға g (q i,a j)=q k болғанда ғана сызылады. Егер q i-ден q k-ға өту белгілі бір S, S A ішкі жиынының кез келген әріптерінің әсерінен жүзеге асырылған жағдайда, осы ішкі жиынның барлық әріптері тиісті доғаның үстіне қойылады (барлық әріптер тізімінің орнына, қысқартылған «x S» немесе жай «S» жазуына рұқсат етіледі). Егер q i ерікті күйі F-ға қосылса, онда бұл факт диаграммада q i төбесін ерекшелейтін қалың шеңбермен белгіленеді.

Кез келген ақырлы күй машинасы оның өту диаграммасымен толық анықталғаны анық. Төменде белгілі бір қасиеттері бар ақырлы автоматты құру тапсырмасы оның ауысуларының диаграммасын құру міндеті ретінде түсінілетін болады.

Суретте. 2.1-суретте A =(a,b,c) алфавитіндегі сөздермен жұмыс істейтін К 1 автоматының диаграммасы көрсетілген. Автоматтың екі күйі бар, q 0 және q 1, тек q 1 күйі «жақсы». q 0 күйінде жұмыс істей бастаған машина a, b әріптерінің әсерінен бұл күйден шықпайды; c әрпінің әсерінен q 1 күйіне көшу жүзеге асырылады; кез келген келесі хат машинаны сол күйінде қалдырады. Осылайша, K 1 автоматы құрамында с әрпі бар сөздерден тұратын L 1 тілін таниды. Бұл тілтұрақты болып табылады.

q0 q1

Бір алфавиттегі тұрақты тілдерге тағы бірнеше мысал келтірейік: L 2 - а әрпі жұп рет кездесетін сөздер жиынтығы; L 3 - бір әріптен басталатын және аяқталатын сөздер жиынтығы; L 4

Құрамында α =abbc ішкі сөзі бар сөздер жиынтығы; L 5 - солдан оңға қарай оқу кезінде кездесетін a және b әріптерінің саны арасындағы айырмашылық ешқашан 2-ден аспайтын сөздер жиынтығы. L 2 - L 5 тілдерін танитын ақырлы күй машиналарының K 2 - K 5 диаграммалары , тиісінше 2.2 - 2.5 суреттерде көрсетілген. Машина оның күйі бойынша кіріс сөздің өңделген бөлігі туралы ақпаратты «есте сақтайды». Мәселен, мысалы, K 5 автоматы кіріс сөздің кейбір бөлігін өңдеп, q х күйінде болады, егер ол оқыған кіріс сөз бөлігінде кездесетін а әріптерінің саны кездесетін b әріптерінің санынан асып кетсе. x; мұнда x (-2, -1, 0, 1, 2); Автомат жұмысының белгілі бір нүктесінде өңделген a әріптерінің саны мен өңделген b әріптерінің саны арасындағы айырмашылықтың абсолютті мәні 2-ден асса, автомат q нашар күйде болады.

		q жаман

Кез келген кіріс әріп автоматты осы күйден шығармаса, соңғы автоматтың жұту күйін атаймыз. Жұтатын күй деп атаймыз оң сіңіреді, егер ол F-ға тиесілі болса, және теріс сіңіредіәйтпесе. K 1 және K 4 автоматтарында q 1 және q 4 күйлері сәйкесінше, K 5 автоматында, q нашар күйі теріс жұтылады;

Әрбір автоматта біреуден артық емес оң жұту және бірден теріс жұту күйі (егер бірнеше оң немесе теріс жұту күйлері болса, онда оларды біреумен оңай ауыстыруға болады) деп болжауға болады. Әдетте, теріс жұту күйі өтпелі диаграммада бейнеленбейді; егер белгілі бір күйден белгілі бір әріппен өту көрсетілмесе, онда ол теріс жұтатын күйге әкеледі деп есептеледі. 2.6-суретте көрсетілген шекті машина А әліпбиінде с әрпі тура бір рет кездесетін сөздерден тұратын тілді таниды. Бұл автоматтың 3 күйі бар, теріс жұту q күйі нашар (автомат оған в әрпіне сәйкес q 1 күйінен кіреді) диаграммада көрсетілмеген.

q0 q1

B әліпбиін енгізейік =(0, 1, 2, …, 9), бұл алфавиттегі әрбір сөз теріс емес бүтін сан ретінде қарастырылады. L (p) натурал тұрақты p санына еселік болатын барлық теріс емес бүтін сандардың ондық санау жүйесіндегі жазбалар – сөздер жиынын белгілейік; L (p) тілі деп есептейміз.

қосымша λ бос сөзі де жатады. L (p) тұрақты тіл екенін көрсетейік. L(p)-ті танитын ақырлы K(p) автоматын келесідей құруға болады. Автоматтың күйлерін q 0, q 1, q 2, q p –1 деп қарастырамыз; ерікті күйден q i цифры x, x (0, 1, 2, ... ,9), машина келесіге өтеді

Оқулықта автоматтар теориясы бойынша кең материал бар. Ол автомат ұғымымен таныстырады, дерексіз және құрылымдық автоматтар теорияларын береді, құрылымдық автоматтар мен біртекті құрылымдар теориясының мәселелерін ашады. Кітапта автоматтар теориясының пайда болуы мен дамуы кезінде отандық және шетелдік авторлар алған соңғы автоматтар теориясы бойынша негізгі нәтижелер жеткілікті толық қамтылған.

1-қадам. Каталогтан кітаптарды таңдап, «Сатып алу» түймесін басыңыз;

2-қадам. «Арба» бөліміне өтіңіз;

Қадам 3. Қажетті мөлшерді көрсетіңіз, «Алушы» және «Жеткізу» блоктарындағы деректерді толтырыңыз;

4-қадам. «Төлемге өту» түймесін басыңыз.

Қазіргі уақытта ELS сайтында 100% алдын ала төлеммен ғана баспа кітаптарын, электронды қолжетімділікті немесе кітапханаға сыйлық ретінде кітаптарды сатып алуға болады. Төлемді төлегеннен кейін сізге электронды кітапханада оқулықтың толық мәтінімен танысуға рұқсат беріледі немесе біз сізге баспаханада тапсырыс дайындауды бастаймыз.

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

Тапсырысыңыз үшін келесі әдістердің бірімен төлей аласыз:

1. Қолма-қол ақшасыз әдіс:
   • Банк картасы: Пішіннің барлық өрістерін толтыру керек. Кейбір банктер төлемді растауды сұрайды - бұл үшін телефон нөміріңізге SMS-код жіберіледі.
   • Онлайн-банкинг: төлем қызметімен ынтымақтасатын банктер толтыру үшін өз пішінін ұсынады. Барлық өрістерге деректерді дұрыс енгізіңіз.
     Мысалы, үшін " class="text-primary">Сбербанк Онлайнсаны қажет ұялы телефонжәне электрондық пошта. Үшін " class="text-primary">Альфа БанкСізге Alfa-Click қызметіне кіру және электрондық пошта қажет.
   • Онлайн әмиян: егер сізде Яндекс әмиян немесе Qiwi әмиян болса, олар арқылы тапсырысыңызды төлей аласыз. Ол үшін сәйкес төлем әдісін таңдап, берілген өрістерді толтырыңыз, содан кейін жүйе сізді шот-фактураны растау үшін бетке бағыттайды.