Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Лекція 2.Скінченні автомати.

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

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

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

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

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

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

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


Читайте також:

  1. Вид заняття: лекція
  2. Вид заняття: лекція
  3. Вид заняття: лекція
  4. Вид заняття: лекція
  5. Вид заняття: лекція
  6. Вступна лекція
  7. Вступна лекція 1. Методологічні аспекти технічного регулювання у
  8. Клітинна селекція рослин.
  9. Колекція фонограм з голосами осіб, які анонімно повідомляли про загрозу вибуху
  10. ЛЕКЦІЯ (4): Мануфактурний період світової економіки
  11. Лекція - Геополітика держави на міжнародній арені
  12. Лекція 02.04.2013




Переглядів: 1120

<== попередня сторінка | наступна сторінка ==>
ЕВОЛЮЦІЯ МІКРООРГАНІЗМІВ. | Недетерміновані скінченні автомати

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.007 сек.