Розуміння державних машин

Вступ до концепцій комп’ютерних наук

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

Це не завжди погано. Коли ми програмуємо, ми працюємо на набагато вищому рівні абстракції.

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

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

Те саме стосується програмування. Багато повсякденної роботи можна виконати, не розуміючи інформатики або зовсім не розуміючи її. Вам не потрібно розуміти обчислювальну теорію, щоб створити форму “Зв’яжіться з нами” у PHP.

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

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

Кінцеві державні машини

Кінцевий автомат - це математична абстракція, що використовується для проектування алгоритмів.

Простіше кажучи, автомат стану зчитує ряд входів. Коли він зчитує вхід, він переходить в інший стан. Кожен стан визначає, в який стан перемикатися, для даного вводу. Це звучить складно, але насправді досить просто.

Уявіть собі пристрій, який читає довгий аркуш паперу. На кожному дюймі паперу на ньому надруковано одну букву - або букву 'a', або букву 'b'.

Коли державна машина читає кожну літеру, вона змінює стан. Ось дуже простий автомат:

Кола - це " стану ", в яких може знаходитись машина. Стрілки - це переходи . Отже, якщо ви перебуваєте у стані s і читаєте букву 'a', ви перейдете до стану q . Якщо ви прочитаєте букву "b", ви залишитесь у штаті s .

Отже, якщо ми почнемо на s і прочитаємо паперову стрічку зверху зліва направо, ми прочитаємо "a" і перейдемо до стану q .

Потім ми прочитаємо "b" і повернемося до стану s .

Ще одне "b" буде тримати нас на s , а потім "a" - яке повертає нас до стану q . Досить просто, але який сенс?

Ну, виявляється, ви можете пропустити стрічку через автомат і розповісти щось про послідовність літер, дослідивши стан, в якому ви опинилися.

У нашому простому автоматі даних вище, якщо ми закінчуємося станами s , стрічка повинна закінчуватися літерою "b". Якщо ми закінчуємо в стані q , стрічка закінчується літерою 'a'.

Це може звучати безглуздо, але існує надзвичайно багато проблем, які можна вирішити за допомогою такого типу підходу. Дуже простим прикладом може бути визначення, чи містить сторінка HTML такі теги в такому порядку:

Машина стану може перейти до стану, який показує, що він прочитав тег html, цикл, поки не дійде до тегу head, цикл, поки не дійде до тегу close head, і так далі.

Якщо він успішно переходить у кінцевий стан, тоді ви маєте ці теги у правильному порядку.

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

Детерміновані скінченні машини

Стан-машини, які ми розглядали досі, - це всі детерміновані автомати стану. З будь-якого стану існує лише один перехід для будь-якого дозволеного введення. Іншими словами, не може бути двох шляхів, що ведуть із стану, коли ви читаєте букву "а". Спочатку це звучить безглуздо, щоб навіть зробити таку різницю.

Яка користь від набору рішень, якщо однакові дані можуть призвести до переходу до більш ніж одного стану? Ви не можете сказати комп’ютеру, if x == trueа потім виконати doSomethingBigчи виконати doSomethingSmall, чи не так?

Ну, ви як би можете з державною машиною.

Результатом роботи автомата стану є його кінцевий стан. Він проходить всю свою обробку, а потім зчитується кінцевий стан, після чого здійснюється дія. Державна машина нічого не робить , переходячи від стану до стану.

Він обробляє, і коли доходить до кінця, стан зчитується, і щось зовнішнє викликає бажану дію (наприклад, видача содової банки). Це важливе поняття, коли мова йде про недетерміновані кінцеві автомати.

Недетерміновані скінченні автомати

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

Наприклад, скажімо, ми хочемо створити кінцевий автомат, який може розпізнавати рядки літер, які:

  • Почніть з літери "а"
  • а потім супроводжуються нулем або більше випадків букви "b"
  • або, нуль або більше випадків букви "c"
  • закінчуються наступною літерою алфавіту.

Дійсні рядки будуть:

  • abbbbbbbbbc
  • abbbc
  • відповідно до
  • відповідно до
  • ac (нуль випадків b)
  • ad (нуль випадків c)

Таким чином, він розпізнає букву "а", за якою слідує нуль або більше тієї самої літери "b" або "c", за якою слідує наступна буква алфавіту.

Дуже простий спосіб представити це за допомогою автомата стану, який виглядає як наведений нижче, де кінцевий стан t означає, що рядок прийнятий і відповідає шаблону.

Ви бачите проблему? Від початкової точки S , ми не знаємо , який шлях взяти. Якщо ми читаємо букву "а", ми не знаємо, чи йти до стану q або r.

Є кілька способів вирішити цю проблему. Один - шляхом зворотного відстеження. Ви просто йдете всіма можливими шляхами, а ігноруєте або відступаєте від тих, де застрягли.

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

Інший варіант - перетворити недетерміновану машину в детерміновану машину.

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

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

Машина нижче є детермінованою версією недетермінованої машини вище. У машині нижче кінцевий стан t або v досягається будь-яким рядком, який приймає машина.

Недетермінована модель має чотири стани та шість переходів. Детермінована модель має шість станів, десять переходів та два можливі кінцеві стани.

Це не набагато більше, але складність зазвичай зростає в геометричній прогресії. Недетермінована машина середнього розміру може створити абсолютно величезну детерміновану машину.

Регулярні вирази

Якщо ви виконували будь-який тип програмування, ви, мабуть, стикалися з регулярними виразами. Регулярні вирази та автомати з кінцевим станом функціонально еквівалентні. Все, що ви можете прийняти або зрівняти з регулярним виразом, може бути прийняте або підібране за допомогою автомата стану.

Наприклад, описаний вище шаблон може відповідати регулярному виразу: a(b*c|c*d)

Регулярні вирази та автомати з кінцевим станом також мають однакові обмеження. Зокрема, вони обидва можуть збігатися або приймати шаблони, з якими можна обробляти обмежену пам’ять.

То який тип зразків вони не можуть збігатися? Скажімо, ви хочете збігатись лише з рядками 'a' та 'b', де є число 'a', за яким слідує рівна кількість 'b'. Або n 'a слідують за n ' b, де n - деяке число.

Прикладами можуть бути:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbb

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

Скажімо, ви створюєте кінцевий автомат, який може приймати до 20 'a, а потім 20' b. Це чудово працює, поки ви не отримаєте рядок з 21 'a, за яким слідують 21' b - в цей момент вам потрібно буде переписати свою машину, щоб обробляти довший рядок.

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

Це відоме як лемма про накачування, яка в основному говорить: "якщо у вашому шаблоні є розділ, який можна повторити (наприклад, вище), то шаблон не є регулярним".

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

Якщо ви уважно подивитесь, ви помітите, що цей тип шаблону, де кожне 'a' має відповідність 'b', виглядає дуже схожим на HTML. У межах будь-якої пари тегів ви можете мати будь-яку кількість інших відповідних пар тегів.

Отже, хоча ви можете скористатися регулярним виразом або кінцевим автоматом, щоб розпізнати, чи на сторінці HTML є ; та елементи у правильному порядку, ви не можете використовувати регулярний вираз, щоб визначити, чи ціла HTML-сторінка є дійсною чи ні - оскільки HTML не є регулярним зразком.ml>, ead>

Машини Тьюрінга

То як розпізнати нерегулярні закономірності ?

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

Пояснення машини Тьюрінга займе більше місця, ніж ми маємо тут, але є кілька важливих моментів, що стосуються нашого обговорення кінцевих автоматів та регулярних виразів.

Машини Тьюрінга обчислювально повні - це означає все, що можна обчислити, можна обчислити на машині Тьюрінга.

Оскільки машина Тьюрінга може писати, а також читати з паперової стрічки, це не обмежується обмеженою кількістю станів. За паперовою стрічкою можна вважати нескінченну довжину. Звичайно, справжні комп’ютери не мають нескінченної кількості пам’яті. Але, як правило, вони містять достатньо пам’яті, щоб ви не досягли межі для типу проблем, які вони обробляють.

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

Чому це важливо?

Отже, який сенс? Як це допоможе вам створити наступну форму PHP?

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

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

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

Фонд комп’ютерних наук дозволяє приймати проблему, яку ви не знаєте, як вирішити і міркувати: «Я не знаю, як вирішити X, але я знаю, як вирішити Y. І я знаю, як конвертувати рішення для Y у рішення для X. Тому я тепер знаю, як вирішити X. "

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

Спочатку опубліковано на blog.markshead.com 11 лютого 2018 року.