Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

126

4. Порівняти результати виконання завдань 2 і 3, визначив-ши загальну кількість порівнянь символів підрядка х із сим­волами рядка s.

5. Виконати завдання 1 для випадку, коли довжина рядка s перевищує 255 символів.

6. Виконати завдання 5 для підрядка х довжиною понад 255 символів у рядку s довжиною в 10 000 символів, протестував-ши його для випадку, коли підрядок х входить у рядок s:

• на початку рядка s;

• посередині рядка s;

• у кінці рядка s;

• декілька разів у рядок s.

7. Порівняти результати виконання завдань 3 і 6, визначив- ши загальну кількість порівнянь символів підрядка х із сим­ волами рядка s.

Скінченні автомати Основні поняття

Теорія автоматів - це один із розділів інформатики. Якщо бути точнішими, то теорія автоматів належить до теоретично! інформатики і вивчає методи, за допомогою яких можна на ос-нові моделей логічного типу вивчати процеси, що протікають у різних пристроях під час обчислень.

Почнемо з уведення загальних понять теорії автоматів.

У широкому тлумаченні автоматами називають пристрої, які виконують процеси приймання, перетворення та передачі енергії, матеріалів або інформації відповідно із закладеними у них програмами.

В інформатиці під автоматом розуміють перетворювач ін-формації, для якого задаються множини вхідних сигналів А, внутрішніх станів Q, вихідних сигналів V, а також дві функції: функція переходів станів 6 та функція виходів X.

Схематично роботу автомата можна зобразити так (мал. 42):

Мал. 42

I ще нам треба ввести такі два поняття: скінченний вхідний алфавіт, який насправді є множиною елементів, над якими може виконуватися перетворення даним автоматом, напри-клад множина натуральних чисел або латинські літери, та сло­во - підмножина алфавіту, над якою безпосередньо і відбу-вається перетворення, тобто яку обробляє автомат у даному

127

конкретному випадку, налриклад задане натуральне число N або деякий текст латинськими літерами. Іншими словами, «слово» - це вхідна інформація.

Якщо введет нові поняття здаються вам складними, то на-справді це зовсім не так. Розберемося з ними детальніше, і все стане напрочуд зрозумілим. Згодом навіть виявиться, що ми вже користувалися алгоритмами, які реалізують скінченні автомати. Термін «скінченний» пояснимо, коли детальніше на прикладах ознайомимося з поняттям автомата.

Для кращого розуміння, почнемо з формулювання задачі, розв'язування якої ми розглянемо в термінах автомата. Нехай задана послідовність натуральних чисел а[і], і - 1, 2, ..., п, у якій треба всі числа, що перевищують 7, замінити на 7.

Завданням автомата є обробка за певною програмою інфор-мації, яка подається йому у вигляді «слова». У нашому випад­ку таким «словом» є задана послідовність дійсних чисел. «Сло­во» складається з окремих елементів а - заданих натуральних чисел, що входять до множини вхідних сигналів А, тобто до множини натуральних чисел. Функція переходів визначає, в який стан q' із множини можливих станів Q перейде перетво-рювач, якщо він перебувае у стані q i на вхід надійшов сигнал а: б(<у, а) = q'. У термінах нашої задачі це означає, що коли на деякому кроці в послідовності значень а[і] буде оброблятися число, значения якого перевищує 7, то воно буде замінено на 7. Тобто при обробці числа а[і] > 7 спрацює функція переходу 6: а[і] :- 7 і перетворить число, яке більше за 7 (вхідний сигнал), на число 7. Зауважимо, що q' також входить до множини Q.

Функція виходів у результат! виконання функції перетво-рення показує, який при цьому виробляється вихідний сигнал v, що належить множит вихідних сигналів V: k(q, а) = v. У нашому прикладі вихідних сигналів буде два: один - про-довження введения дійсних чисел у випадку, коли і < п, і завер­шения введения, коли і > п. Перший позначимо, наприклад, О, другий - I.

Стандартним описом скінченного автомата є таблиця, яку називають таблицею перетворень.

Отже, представимо описаний скінченний автомат, що реа-лізує поставлену задачу у вигляді такої таблиці переходів (табл. 11): у рядках розмістимо можливі стани виконання ал­горитму - перехід до наступного елемента заданої послідов-ності та заміну поточного елемента на 7; у стовпчиках — усі можливі значения елементів послідовності. На перетині відпо-відних рядків і стовпчиків розміщене посилання на функцію переходу, яку описує даний елемент таблиці. Наприклад, якщо поточний елемент послідовності дорівнює 2, то переходимо до розгляду наступного елемента, якщо ж 8, то спочатку робимо

128

заміну його значения на 7, а потім знову переходимо до розгля-ду наступного елемента. Алгоритм завершиться, коли припи­ши-ься введения елементів послідовності.

Таблицяіі

Тепер можна визначитися щодо назви «скінченні автома­та». Справа в тому, що у нашому випадку всі множини сигна-лів А та V і внутрішніх станів Q дискретні, тобто порційні, а їх елемента ізольовані один від одного: послідовність вхідних дійс-них чисел (а[ї\, і - 1, 2, ..., п), перетворення значень деяких із них за умовою задачі (якщо а[ї] > 7, тоді а[і]:- 7), завершения виконання задачі (і > п). Дискретною є і послідовність момен-тів, у які надходять вхідні сигнали, отримуються вихідні та змінюються внутрішні стани: перехід до введения наступного значения а[ї\ відбувається лише після завершения обробки попереднього.

Будемо говорити, що якщо множини сигналів і станів скін-ченні, то автомат, обо перетворювач, називається скінченним.

Наведемо означения скінченного автомата в термінах алго-ритмізапії, оскільки саме цей розділ інформатики знаходиться в полі нашого зору і саме методами побудови алгоритмів ми займаємося.

Скінченним автоматом будемо називати алгоритм, у якому передбачено обробку скінчешюї кількості всіх можливих ситуацій та переходу вхідної інформації за скінченну кіль-кість кроків із заданого початкового стану в кінцевий.

Тепер, коли поняття скінченного автомата стало досить про-зорим, можна навести чимало прикладів із тих задач, які ми раніше розв'язували, і тепер сформулювати їх у нових термі-нах. Наприклад, задача, яка передбачає введения недодатних значень для змінних, що можуть набувати лише натуральних чисел; контроль за перемиканням клавіатури на ту чи іншу абетку при введенні текстової інформації тощо.

Розглянемо ще кілька задач, алгоритми яких можна пред-ставити у вигляді скінченних автоматів.

■ ) Ыфораттщгя 9 l»¹1 і

129

Нехай треба визначити правильність розміщення круглих дужок у заданій математичній формулі. Для спрощення вва-жатимемо, що вхідна інформадія задається у вигляді тексту, який містить натуральні числа, знаки арифметичних операцій (+, -, •, /) і відкриті та закриті круглі дужки.

Алгоритм визначення коректності розставлених круглих дужок в арифметичному виразі полягає в покроковому збіль-шенні лічильника k у випадку «(» та його зменшення у випад­ку «)» . Якщо протягом виконання алгоритму виконається умо-ва k < О, то це означатиме, що порушено баланс відкритих та закритих дужок і далі виконання алгоритму не мае змісту. Якщо перегляд вхідної інформації завершено, то ознакою ко-ректності розміщення круглих дужок в арифметичному виразі є виконання умови k »= 0.

Які ситуації нам потрібно обробляти, тобто які внутрішні стани можуть бути? Перше - це перехід до наступного символу у випадку, коли він не є дужкою, та перевірка завершеності введения інформації. Друге - підрахунок відкритих круглих дужок, тобто збільшення лічильника ft на 1. Третє — підра-хунок закритих круглих дужок, тобто зменшення лічильника k на 1. Четверте — перевірка співвідношення k < 0, тобто кон-тролювання ситуації, коли закритих дужок стане більше, ніж відкритих. П'яте - завершения роботи автомата. Робота такого автомата представлена у вигляді таблиці 12.

Таблиц* 12

130

У комірках на перетині відповідних станів та елементів вхідної інформації будемо вказувати дві величины: значения функції переходу 6(9,, а.) та через кому значения функції вихо-ду X(q., cif) (табл. 12).

Значениям функції переходу 6 може бути одне з можливих значень, указаних у переліку станів q_r Значениям функції вы­ходу К може бути 0 (робота автомата продовжуеться) та 1 (робо­та автомата припиняється).

Для зручності значения функції виходу будемо вказувати так. Якщо результат цієї функції однозначний, то будемо вка­зувати одне це значения, якщо ж значень може бути два, за-лежно від виконання умови, яка аналізується, то будемо вказу­вати два значения: перше - для випадку виконання умови, друге - для випадку ЇЇ невиконання. Наприклад, q_v 0/1 озна­чав перехід до стану q_i зі значениям функції виходу 0 у разі виконання умови, що аналізується в цьому стані (це означав, що робота автомата продовжуеться), та 1 у разі невиконання умови (робота автомата припиняеться).

Отже, ми представили алгоритм, описаний вище, в іншій формі - у вигляді таблиці переходів скінченного автомата.

Змінимо попередню задачу і будемо контролювати корект-ність написания імен функцій, використання яких передбаче-но умовою задачі. Для спрощення запису таблиці переходів створимо скінченний автомат лише для функції синуса і буде­мо вважати, що символи «s», «i» та «n» використовуються ли­ше у выклику вказаної функції. Побудуємо таблицю переходів для цієї задачі (табл. 13).

Таблиця 13