Головна

Кінцеві автомати та формальні граматики

  1.  Ein bisschen Grammatik (трошки граматики)
  2.  Грецькі початкові і кінцеві терміноелементи
  3.  ДИСФУНКЦІЇ БЮРОКРАТІЇ - втручання людського фактора - емоцій, симпатій, уподобань, неформальних норм і цінностей в формальні правила).
  4.  ДИСФУНКЦІЇ БЮРОКРАТІЇ. (Дисфункції -вмешательство людського фактора - емоцій, симпатій, уподобань, неформальних норм і цінностей в формальні правила).
  5.  Європейські граматики XV - початку XVII ст. в їх зв'язку з гуманізмом і Реформацією
  6.  ІНФОРМАЦІЙНІ ПОСЕРЕДНИКИ ТА КІНЦЕВІ КОРИСТУВАЧІ
  7.  До первинних відносять тільки малі групи, до вторинних - формальні малі і великі.

Технічне втілення логічних операцій отримало назву комбінаційних або переключательних схем. Як зазначалося вище логічні стану «1» і «0» задаються в комп'ютерах і системах зв'язку у вигляді наявності або відсутності струму в електронних ланцюгах. Переключательная схему можна отримати шляхом послідовного з'єднання елементарних електричних ланцюгів з контактами (електричними вимикачами), які можуть замикати або розмикати електричний ланцюг. Можливо таке уявлення елементарних логічних операцій за допомогою ланцюгів і контактів (Рис 2.1).

Рис 2.1. Подання елементарних логічних операцій за допомогою електричних ланцюгів з контактами

більш складні переключательние схеми, Що реалізують більш складні логічні вирази, Можна технічно отримувати шляхом послідовного приєднання виходів одних електричних ланцюгів елементарних логічних схем до входів інших електричних ланцюгів реалізують інші елементарні логічні схеми. Якщо комбінаційна схема має кінцеве безліч вхідних логічних станів x, y, z ... і одне єдине вихідна стан q, то описаний процес послідовного приєднання елементарних логічних схем відповідає процесу побудови логічної формули f (x, y, z ...) за допомогою операцій, що реалізуються використовуваними електричними ланцюгами (елементарними логічними схемами). За допомогою таких комбінаційних логічних схем і відповідним їм електричних кіл технічно реалізуються пристрої зберігання, переміщення і здійснення не тільки логічних операцій над символами, а й арифметичних операцій над цифрами. Вони утворюють, так звані, тригери, регістри, суматори. Ці технічні конструкції утворюють ті самі спеціальні пристрої, з яких і складається комп'ютер. Так пристрої для зберігання даних складаються з регістрів і називаються пам'яттю. Пристрої для здійснення логічних і арифметичних операцій над даними, що складаються з регістрів і суматори називаються арифметично-логічними пристроями (АЛУ). Особливий різновид цих пристроїв називається пристроями управління (УУ), Бо логічні операції, здійснювані ними, спрямовані на управління потоками даних комп'ютері.

Важливою особливістю подібних пристроїв є те, що їх внутрішні логічні стану (Логічні змінні) змінюються з часом під впливом вхідних впливів (Теж логічних станів), фізично подаються у вигляді наявності або відсутності струму в ланцюзі. Ці вхідні впливу іноді називають вхідними сигналами (X, y, z ... ..). Нагадаємо, що ці пристрої мають і вихідна логічне стан, Яке називається вихідним сигналом (Q).

Для математичного опису подібних пристроїв вводяться спеціальні позначення. Безліч вхідних сигналів позначається як U , через Q - безліч вихідних сигналів, А через X - безліч внутрішніх станів. Для опису змін в часі зручно ввести поняття дискретного часу. На осі часу відзначаються моменти, в які вхідний сигнал може зазнавати зміни. Ці окремі моменти часу зручно представляти у вигляді послідовності невід'ємних цілих чисел n = 0,1,2 ... В інформатиці такі послідовності називають тактами. Рівняння, що описує роботу комбінаційної схеми в часі можна записати у вигляді Q (n) = f (X (n)). Математичний опис комбінаційних схем з урахуванням їх внутрішніх станів і еволюції цих станів у часі під впливом вхідних сигналів називається кінцевим автоматом і задається сукупністю п'яти величин A = (U, Q, X, f, ?). Тут f: X • U > X -функція переходів, ?: X • U > Q - функція виходів. Функції переходів і виходів зазвичай задаються відповідними таблицями або з допомогою спеціальних графіків - спрямованих графів. Вершини графів зображувані у вигляді кружечків, визначають стану автомата, дуги вказують переходи автомата з одного стану в інший під впливом вхідного сигналу. У дужках вказується вихідний сигнал.

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

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

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

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

У висновку ще раз перерахуємо основні операції математичної логіки і двійковій арифметики:

· Це логічні операції: роз'єднання (Диз'юнкція, логічне «АБО»), логічне множення (Сполучення, логічне «І»), логічне заперечення (Інверсія, логічне «НЕ»), логічне проходження (Імплікація), логічна еквівалентність.

· Це арифметичні операції: двійкове додавання, двійкове множення.

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




 ВСТУП |  Поняття інформатики. Структура і класифікація |  Поняття інформації. характеристики інформації |  Економічна інформація і її особливості |  Інформаційні системи. Структура і класифікація інформаційних систем |  Інформаційні технології. Види інформаційних технологій |  Моделі рішення функціональних і обчислювальних завдань |  тестові завдання |  Вступ |  Технічна реалізація символів і операцій над ними |

© um.co.ua - учбові матеріали та реферати