Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Постановка задачи к лабораторной работе № 7
Разработать программное средство, автоматизирующее процесс разбора цепочек для грамматик простого предшествования. Программное средство должно выполнять следующие функции: 1) ввод произвольной грамматики; 2) построение множеств L (A) и R (A)для каждого нетерминального символа грамматики; 3) формирование матрицы простого предшествования для введенной грамматики; 4) проверка условия простого предшествования для данной грамматики; 5) моделирование функционирования распознавателя для грамматик простого предшествования. Составить набор контрольных примеров для случаев: а) введенная грамматика не является грамматикой простого предшествования; б) исходная грамматика является грамматикой простого предшествования, но анализируемая строка не принадлежит языку грамматики; в) заданная грамматика является грамматикой простого предшествования и входная строка принадлежит языку грамматики. Разбор цепочек представить в виде таблицы, строки вывода и дерева вывода. Вариантами индивидуального задания к лабораторной работе № 7 являются выходные данные лабораторной работы № 4.
Тема и цель лабораторной работы Лабораторная работа № 2. Тема: «Построение конечного автомата по регулярной грамматике»
Цель: -закрепить понятия «регулярная грамматика», «недетерминированный и детерминированный конечный автомат»; - сформировать умения и навыки построения конечного автомата по регулярной грамматике и преобразования недетерминированного конечного автомата к детерминированному конечному автомату.
Постановка задачи Дана регулярная грамматика G = ({ A, B, C, S }, { a, b }, P, S), где Р: 1) S ® aB | aA; 2) A ® aA | bC | b; 3) B ® bB | aC | a.
Разработать программное средство, реализующее следующие функции: 1) ввод произвольной формальной грамматики с клавиатуры и проверка ее на принадлежность к классу регулярных грамматик; 2) построение по заданной регулярной грамматике конечного автомата; 3) преобразование недетерминированного конечного автомата к детерминированному конечному автомату; 4) вывод графа результирующего конечного автомата на экран. 3 Формальная модель задачи Определение 1. Детерминированным конечным автоматом (ДКА) называется пятерка объектов:
, (2.1)
где - конечное множество состояний автомата; - конечное множество допустимых входных символов; - функция переходов, отображающая множество Q´T во множество Q; - конечное множество начальных состояний автомата; Z - множество заключительных состояний автомата, Z Í Q. Определение 2. Недетерминированным конечным автоматом (НКА) называется конечный автомат, в котором в качестве функции переходов используется отображение во множество всех подмножеств множества состояний автомата , т.е. функция переходов неоднозначна, так как текущей паре соответствует множество очередных состояний автомата .
|
|||||||
Последнее изменение этой страницы: 2019-04-30; просмотров: 253; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.15.197.123 (0.004 с.) |