МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
Лекція 2.Скінченні автомати.У даній лекції розглядаються два найбільш поширених способи визначення формальних мов: граматики та автомати. Розглядаються скінченні автомати, що відповідають у ієрархії Хомського праволінійним граматикам, визначаються поняття скінченного автомату, недетермінованого скінченного автомату і мови, що розпізнається скінченним автоматом. Наведено практичні приклади і вправи для закріплення матеріалу Два найбільш поширених способи задання формальної мови - це граматики й автомати. Автоматами в даному контексті називають математичні моделі деяких обчислювальних пристроїв. В цій лекції розглядаються скінченні автомати, що відповідають у ієрархії Хомського праволінійним граматикам. Термін "автоматна мова" закріплений за мовами, що розпізнається саме скінченними автоматами, а не якимись більш широкими родинами автоматів (наприклад, автоматами з магазинною пам'яттю або лінійно обмеженими автоматами). У розділі 2.1 визначаються поняття скінченного автомату (для ясності такий автомат можна називати недетермінованим скінченним автоматом) і мови, що розпізнається скінченним автоматом . У наступному розділі дається інше, але еквівалентне першому визначення мови, що розпізнається скінченним автоматом. Воно не є необхідним для подальшого викладу, але саме це визначення піддається узагальненню на випадки автоматів інших типів. У розділі 2.3 доводиться, що той же клас автоматних мов можна отримати, використовуючи лише скінченні автомати спеціального виду (вони читають на кожному такті рівно один символ і мають рівно один початковий стан). У багатьох підручниках скінченними автоматами називають саме такі автомати. Цілу серію класичних результатів теорії формальних мов становлять теореми про відповідність деяких класів граматик деяким класам автоматів. Перша теорема з цієї серії, яка стверджує, що праволінійні граматики є автоматними мовами, доводиться в розділі 2.4. Інша серія результатів пов'язана з можливістю звузити певний клас граматик, не змінивши при цьому клас породжуваних ними мов. Зазвичай у такому випадку граматики з меншого класу називаються граматиками в нормальній формі. У розділі 2.5 * формулюється результат такого типу для праволінійних граматик. Сама ця теорема не представляє великого інтересу, але аналогічні результати, які доводяться пізніше для контекстно-вільних граматик, використовуються в багатьох доведеннях та алгоритмах. Не всі скінченні автомати підходять для конструювання розпізнавальних пристроїв, придатних для практичної реалізації, тому що в загальному випадку скінченний автомат не дає точної вказівки, як поступати на черговому кроці , а дозволяє продовжувати обчислювальний процес декількома способами. Цього недоліку немає у детермінованих скінченних автоматів (часткового випадку недетермінованих скінченних автоматів), визначених у розділі 2.6. У розділі 2.7 доводиться, що кожна автоматна мова задається деяким детермінованим скінченним автоматом. Читайте також:
|
||||||||
|