Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Конечный детерминированный автомат
СообщениеДобавлено: 04 апр 2013, 13:06 
Не в сети
Начинающий
Зарегистрирован:
04 апр 2013, 12:48
Сообщений: 2
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Может кто помочь решить,пожалуйста?
Построить автомат (конечный детерминированный), который принимает слова на основе алфавита {0,1} и определяет как «правильные» только те, которые заканчиваются на 10 или содержат по крайней мере одну группу 0011.
Указать, на каком этапе «чтения» слова автомат принимает решение засчитать ее «правильной».
Возможно ли в автомате состояние «ловушки»? Объяснить свой ответ.
Построить грамматику, соответствующую автомату.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Конечный детерминированный автомат
СообщениеДобавлено: 04 апр 2013, 16:36 
Не в сети
Последняя инстанция
Аватара пользователя
Зарегистрирован:
03 апр 2012, 03:09
Сообщений: 4112
Cпасибо сказано: 116
Спасибо получено:
1823 раз в 1515 сообщениях
Очков репутации: 379

Добавить очки репутацииУменьшить очки репутации
▼ Построение автомата
Регулярное выражение: [math](0|1)^*(10|0011(0|1)^*)[/math]

Недетерминированный автомат:
Изображение

Построение детерминированного автомата:
01
11,41,2
1,41,4,51,2
1,4,51,4,51,2,6
1,21,3,41,2
1,3,41,4,51,2
1,2,61,3,41,2,7
1,2,71,3,4,71,2,7
1,3,4,71,4,5,71,2,7
1,4,5,71,4,5,71,2,6,7
1,2,6,71,3,4,71,2,7

01
1 (start)23
243
445
363
6 (end)43
567
7 (end)87
8 (end)97
9 (end)910
10 (end)87


После минимизации числа состояний:
01
1 (start)23
243
363
445
567
6 (end)43
7 (end)77


Рисунок:
Изображение

▼ Праволинейная грамматика
[math]G=(\{S,A,B,C,D,E,F\},\{0,1\},P,S)[/math]
[math]S\to0A[/math]
[math]S\to1B[/math]
[math]A\to0C[/math]
[math]A\to1B[/math]
[math]B\to0E[/math]
[math]B\to1B[/math]
[math]C\to0C[/math]
[math]C\to1D[/math]
[math]D\to0E[/math]
[math]D\to1F[/math]
[math]E\to0C[/math]
[math]E\to1B[/math]
[math]F\to0F[/math]
[math]F\to1F[/math]
[math]B\to0[/math]
[math]D\to0[/math]
[math]D\to1[/math]
[math]F\to0[/math]
[math]F\to1[/math]

Oi-Man писал(а):
Указать, на каком этапе «чтения» слова автомат принимает решение засчитать ее «правильной».

Неясен вопрос.
Oi-Man писал(а):
Возможно ли в автомате состояние «ловушки»? Объяснить свой ответ.

Что такое состояние "ловушки"?

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Human "Спасибо" сказали:
Alexdemath, mad_math, Oi-Man
 Заголовок сообщения: Re: Конечный детерминированный автомат
СообщениеДобавлено: 14 апр 2013, 13:24 
Не в сети
Начинающий
Зарегистрирован:
04 апр 2013, 12:48
Сообщений: 2
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Human писал(а):
Что такое состояние "ловушки"?

Это бесконечный цикл.



Огромное спасибо, merci & thank you за то, что Вы проделали выше!!!

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 3 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
построить детерминированный конечный автомат

в форуме Дискретная математика, Теория множеств и Логика

Boongo

1

184

06 янв 2022, 12:51

Построить конечный детерминированный автомат

в форуме Дискретная математика, Теория множеств и Логика

Xterylis

0

112

12 янв 2021, 19:47

Задан детерминированный конечный автомат

в форуме Дискретная математика, Теория множеств и Логика

Venus11

1

317

15 июл 2016, 17:21

Построить детерминированный конечный автомат

в форуме Дискретная математика, Теория множеств и Логика

Kenguru

0

243

15 дек 2019, 17:33

Построить детерминированный конечный автомат

в форуме Дискретная математика, Теория множеств и Логика

Alinmora

1

1044

20 май 2016, 19:03

Построить детерминированный конечный автомат по описанию

в форуме Дискретная математика, Теория множеств и Логика

rakichkin

1

172

13 дек 2021, 00:41

Построить Конечный детерминированный автомат, распознающий н

в форуме Дискретная математика, Теория множеств и Логика

Alexander132

2

166

08 сен 2019, 08:38

Построить детерминированный автомат

в форуме Дискретная математика, Теория множеств и Логика

nextr0ll

0

146

14 окт 2019, 20:48

Недетерминированный конечный автомат

в форуме Дискретная математика, Теория множеств и Логика

Elhanan

3

430

21 дек 2016, 17:34

Построить законченный детерминированный автомат

в форуме Дискретная математика, Теория множеств и Логика

Olena88

1

149

12 дек 2021, 17:26


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved