Теория автоматов
1. Автомат. Подходы к определению и изучению автоматов. Концепция порождения и распознавания. Применение теории автоматов. 2. Знак. Символ. Алфавит. Множество универсум. Слово. Строка. Конкатенация. Формальный язык. Операции над формальными языками.
Определение LL(k)-грамматик. Для начала предположим, что G=(N,E,P,S) — однозначная грамматика и w=a1,a2…an — цепочка из L(G). Тогда существует единственная последовательность левовыводимых цепочек b0,b1..bm, для которой S=b0,bi,pi ? bi+1 при 0<=i<m и am=w. Последовательность p0p1..pm-1 -левый разбор цепочки w.
Учебное пособие для вузов Рекомендовано научно-методическим советом Приднестровского государственного университета в качестве учебного пособия для студентов высших технических учебных заведений
Занятие 1.1. Формальные языки Задача 1 Задан алфавит и строка над этим алфавитом. Перечислить префиксы, суф¬фиксы и подстроки строки . Оценить, сколькими способами для строки дли¬ной можно выбрать суффикс, префикс и подстроку.
Занятие 2.1. Машина Тьюринга (МТ) Задача 23 МТ задана таблицей.
Занятие 3.1. Минимизация автоматов Задача 39 КА задан в виде графа.
Занятие 4.1. Синтез комбинационных автоматов Задача 45 Заданы два КА и в виде автоматных таблиц. Построить КА , эквивалентный последовательному соединению автоматов и .
