|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Магазинні автоматиОзначення. Магазинний автомат де:
Поточний стан магазинного автомата - початкова конфігурація
- заключна конфігурація Такт роботи (позначається ╞═) магазинного автомата
Робота магазинного автомата Операції ╞═ та ╞═* можна трактувати як бінарні відношення на відповідних кортежах. Тоді робота магазинного автомата Означення. Мова, яку розпізнає магазинний автомат
Зафіксуємо наступні результати теорії магазинних автоматів: 1. Не існує алгоритму перетворення недетермінованого магазинного автомата у еквівалентний йому детермінований магазинний автомат. 2. Існує алгоритм, який вирішує проблему порожньої множини 3. Існує алгоритм, який за час, пропорційний 4. Клас мов, які розпізнаються магазинними автоматами, співпадає з класом мов, що породжуються КС-граматиками. На основі сформульованих вище результатів для лівосторонньої стратегії виводу Нехай - - - - функцію - якщо
- також поповнимо множину значень функції
Для ланцюжка - коли - коли Очевидно, якщо ланцюжок
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |