Этот заказ уже выполнен на сервисе Автор24
На нашем сайте вы можете заказать учебную работу напрямую у любого из 45000 авторов, не переплачивая агентствам и другим посредникам. Ниже приведен пример уже выполненной работы нашими авторами!
Узнать цену на свою работу

Построение детерминированного конечного автомата по НКА. Регулярные выражения.

Номер заказа
132016
Создан
23 августа 2014
Выполнен
24 августа 2014
Стоимость работы
150
Помоги! Срочно выполнить решение задач по информационным технологиям. Есть буквально 1 день. Тема работы «Построение детерминированного конечного автомата по НКА. Регулярные выражения.».
Всего было
18 предложений
Заказчик выбрал автора
Этот заказ уже выполнен на сервисе Автор24
На нашем сайте вы можете заказать учебную работу напрямую у любого из 45000 авторов, не переплачивая агентствам и другим посредникам. Ниже приведен пример уже выполненной работы нашими авторами!
Узнать цену на свою работу
Или вы можете купить эту работу...
Страниц: 5
Оригинальность: Неизвестно
150
Не подошла
данная работа?
Вы можете заказать учебную работу
на любую интересующую вас тему
Заказать новую работу

Задача1. Используя процедуру детерминизации недетерминированных автоматов постройте ДКА, эквивалентный заданному НКА M.
Задача 2. Постройте регулярное выражение, задающее язык язык L в алфавите .
• L= {w | w содержит нечетное число букв 0 и четное число букв 1}} ;
• L= {w | w содержит подслово 001 или подслово 110 } ;
• L= {w | w содержит по крайней мере мере два подряд идущих 0 } ;
• L= {w | w не содержит подслов 011 и 010}.
Задача1. Используя процедуру детерминизации недетерминированных автоматов постройте ДКА, эквивалентный заданному НКА M.
Задача 2. Постройте регулярное выражение, задающее язык язык L в алфавите .
• L= {w | w содержит нечетное число букв 0 и четное число букв 1}} ;
• L= {w | w содержит подслово 001 или подслово 110 } ;
• L= {w | w содержит по крайней мере мере два подряд идущих 0 } ;
• L= {w | w не содержит подслов 011 и 010}.
Задача1. Используя процедуру детерминизации недетерминированных автоматов постройте ДКА, эквивалентный заданному НКА M.
Задача 2. Постройте регулярное выражение, задающее язык язык L в алфавите .
• L= {w | w содержит нечетное число букв 0 и четное число букв 1}} ;
• L= {w | w содержит подслово 001 или подслово 110 } ;
• L= {w | w содержит по крайней мере мере два подряд идущих 0 } ;
• L= {w | w не содержит подслов 011 и 010}.
Задача1. Используя процедуру детерминизации недетерминированных автоматов постройте ДКА, эквивалентный заданному НКА M.
Задача 2. Постройте регулярное выражение, задающее язык язык L в алфавите .
• L= {w | w содержит нечетное число букв 0 и четное число букв 1}} ;
• L= {w | w содержит подслово 001 или подслово 110 } ;
• L= {w | w содержит по крайней мере мере два подряд идущих 0 } ;
• L= {w | w не содержит подслов 011 и 010}.

{1,2}
{}
{}
1
{}
{2}
{2}
2
{}
{0}
{}
Построим диаграмму данного НКА.
Устраним пустые переходы:
E*={(1,2)}
Определим НКА без пустых переходов:
Q={q0}{q | существуют такие q’  Q и a, что q’aq}
Q={0,1,2}
F={q | существует такое q’F, что (q,q’) E*}
F={2}
Построим диаграмму НКА без пустых переходов:
Данный конечный автомат не является детерминированным. Переходим к шагу 2.
Идея детерминации состоит в том, что состояния ДКА объявляются подмножествами состояний НКА. Тогда для каждого такого подмножества Т и входного символа а однозначно определено множество состояний Т’, в которые НКА может попасть из состояний Т при чтении а.
Построим булеан множества состояний (Q)
a
b
{Ø}
A
{Ø}
{Ø}
{0}
B
{1,2}*
F
{Ø}
{1}
C
{Ø}
{0,2}*
G
*{2}
Автор24 - это фриланс-биржа. Все работы, представленные на сайте, загружены нашими пользователями, которые согласились с правилами размещения работ на ресурсе и обладают всеми необходимыми авторскими правами на данные работы. Скачивая работу вы соглашаетесь с тем что она не будет выдана за свою, а будет использована использовать исключительно как пример или первоисточник с обязательной ссылкой на авторство работы. Если вы правообладатель и считаете что данная работа здесь размещена без вашего разрешения - пожалуйста, заполните форму и мы обязательно удалим ее с сайта. Заполнить форму
Оценим бесплатно
за 10 минут
Эта работа вам не подошла?
У наших авторов вы можете заказать любую учебную работу от 200 руб.
Оформите заказ и авторы начнут откликаться уже через 10 минут!
Заказать решение задач