Формалды грамматика 6 страница

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒

Автомат – бұл қандай да бір жиынды анықтайтын алгоритм, мүмкін болған жағдайда ол жиынды басқа жиынға түрлендіруі мүмкін. Автоматтардың формальсыз сипатталынуы келесі түрде болады: автомат кіру лентасынан, күйдің нөмірін сақтайтын ақырлы жадысы бар басқару құрылғысынан тұрады, сонымен қатар көмекші және шығыстық лентасы болуы мүмкін. Автоматтардың екі типі бар:

1) танығыштар – шығыссыз автоматтар, олар кіру тізбегі берілген L жиынына тиісті ме соны таниды;

2) түрлендіргіштер – шығысы бар автоматтар, олар x ∈ L шарты орындалғанда кіру тізбегі х –ті у тізбегіне түрлендіреді.

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

Автоматтың лентасы шексіз, бірақ әрбір уақыт моментінде ұяшықтардың тек ақырлы саны ғана бос емес болады. Бос емес аймақтың шекаралы оң және сол жақтағы ұяшықтары арнайы соңғы маркерлерді алуы мүмкін. Маркер лентаның тек бір жақ соңында ғана тұруы немесе мүлдем болмауы мүмкін.

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

Жұмыс лентасы - ақпаратты сақтаудың көмекші қоймасы. Ондағы берілгендер автоматтың көмегімен оқылады және оған жазылуы да мүмкін.

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

1) кіру бастиегі оңға жылжиды немесе бір орында тұрады;

2) жұмыс лентасына қандай да бір ақпарат жазылады;

3) басқару құрылғысының жағдайы өзгереді;

4) шығу лентасына (егер ол бар болса) символ жазылады.

Автоматтың жұмыс істеу тәртібін автоматтың конфигурациясы терминімен сипаттаған ыңғайлы, ол келесіден тұрады:

а) басқару құрылғысының жағдайы;

б) кіру лентасындағы берілгендер кіру бастиегінің жағдайымен бірге;

в) жұмыс лентасындағы берлігендер кіру бастиегінің жағдайымен бірге;

г) шығу лентасындағы берілгендер, егер ол бар болса.

Басқару құрылғысы детерминделмеген болуы мүмкін. Мұндай жағдайда әрбір конфигурация үшін тактілердің ақырлы жиыны бар болуы мүмкін, оның әрқайсысын автомат осы конфигурациядан шыға отыра жасайды. Басқару құрылғысы детерминделген болады, егер әрбір конфигурация үшін тек бір ғана келесі такт мүмкін болса.

Бақылау сұрақтары:

1. Тілдер және автоматтар теориясы нені зерттейді?

2. Автоматтардың қандай тптері бар?

Ұсынылған әдебиеттер:

1. Берн.Э.С. Вопросы теории поисковых систем. М. 1966 г

2. Брауэр В. Введение в теорию конечных автоматов. М. 1987 г

Дәріс 7. Соңғы, магазиндік жадылы, екі жақты автоматтар

Мақсаты: Автоматтың типтері мен түрлерін таныстыру.

Жоспары:

· Автомат түрлері

· Инициалданған автомат

Автоматтардың келесі типтері болады: 1) Тьюринг машинасы (ТМ); 2) сызықты – шектелген автомат (США); 3) магазиндік жадысы бар автомат (МЖ- автомат); 4) ақырлы автомат (АА).

Ақырлы автоматтың күрделігін автоматтың күрделілігі анықтайды. Мысалы:

1) Тьюринг машинасы екі жаққа да шексіз ленталардан тұрады;

2) сызықты – шектелген автоматтарда жұмыс лентасының ұзындығы кіру тізбекшесінің ұзындығының сызықтық функциясын береді;

3) МЖ-автоматта жұмыс лентасы LIFO магазинінің принципімен жұмыс істейді;

4) ақырлы автоматтарда жұмыс лентасы болмайды.

Инициалданбаған автомат – бұл А = (К, X, Y, δ, γ) түрдегі бестік, мұндағы К – күйлердің жиыны (күйлердің алфавиті); Х – кіру алфавиті; Y – шығу алфавиті; δ – К: Х→К бейнелеуді беретін өту функциясы; γ – К: Х→У бейнелеуді беретін шығу функциясы.

Автоматтың функцияларын келесі түрдегі командалардың жиыны ретінде беруге болады: qx → py, мұндағы q және p ∈ K, x ∈ X, y ∈ Y.

t_i қайсыбір тактісінде басқару құрылғысы q жағдайда болсын, ал кіру лентасынан x символы оқылсын делік. Егер командалардың жиынында qx → py командасы бар болса, онда t_i тактісінде шығу летасына у символы жазылады, ал келесі t_i +1 тактісінде басқару құрылғысы р жағдайына өтеді, яғни:

y(t) = γ(q(t), x(t)), q(t-1) =δ(q(t), x(t)).

Егер qx → py командасы болмаса, онда автомат бұғатталады және t_i моментінде қабылданған символға ешқандай әсер білдірмейді, сонымен қатар уақыттың келесі моментіндегі символдарды да қабылдамайды.

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

Егер қандай да бір алғашқы жағдай алдын – ала бекітілген болса, онда мұндай автоматты инициалданған автомат деп атайды, яғни q(0) = q₀.

Инициалданған автомат – бұл А = (К, X, Y, δ, γ, q₀) түріндегі алтылық, мұндағы К – жағдайлардың жиыны (жағдайлардың алфавиті); Х – кіру алфавиті; Y – шығу алфавиті; δ - өту функциясы (К: Х → К бейнелеуі); γ – шығу функциясы (К: Х → У бейнелеуі); q₀ – алғашқы жағдай.

Бақылау сұрақтары:

1. Автоматтың қандай типтері бар?

2. Инициалданбаған және инициалданған автоматтар деп нені айтамыз?

Ұсынылған әдебиеттер:

1. Вирт Н. Систематическое программирование. М. Мир. 1977 г

2. Гросс М. Теория формаьныз граматик. М.Мир. 1971 г.

Дәріс № 8. ТЬЮРИНГ МАШИНАСЫ

Мақсаты: Тьюринг машинасы және фон Нейман автоматтарымен таныстыру.

Жоспары:

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒

Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных