Форум программистов, компьютерный форум, киберфорум
Наши страницы
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/12: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Darija
0 / 0 / 0
Регистрация: 25.10.2015
Сообщений: 5
1

Нужна реализация любого конечного автомата.

19.09.2011, 22:44. Просмотров 2307. Ответов 1
Метки нет (Все метки)

Народ, подкиньте реализацию любого конечного автомата, или подскажите, где взять. Заранее спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.09.2011, 22:44
Ответы с готовыми решениями:

Построение конечного автомата...
Задали лабу, но ничего не обьяснили. Что тут нужно вообще делать, пожалуйста,...

Детерминизация конечного автомата
здравствуйте, надеюсь, пишу в тот раздел. более подходящего не нашел. перехожу...

Модель детерминированного конечного автомата
Подскажите пожалуйста, как будет выглядеть таблица переходов автомата без...

Построение модели конечного автомата
Построить модель кодового замка с пятью кнопками (А, Б, В, Г, Д),...

Построение модели конечного автомата
Монета многократно подбрасывается и делается отметка при четных выпадениях...

1
challengerr
43 / 36 / 6
Регистрация: 30.07.2008
Сообщений: 136
26.09.2011, 17:04 2
Задан конечный автомат следующем функцией переходов :

состояниесимвол 0символ 1
01
124
253
324
http://www.cyberforum.ru/cgi-bin/latex.cgi?\rightarrow(выход)
435
555
Реализация
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'матрица переходов
Dim Delta(5,2) As Integer
'state - номер текущего состояния
Dim state,j,l,n As Integer
'InputString - входная цепочка
'Symbol - текущий входной символ
Dim InputString, Symbol As String
Delta(1,1) = 2 : Delta(1,2) = 4
Delta(2,1) = 5 : Delta(2,2) = 3
Delta(3,1) = 2 : Delta(3,2) = 4
Delta(4,1) = 3 : Delta(4,2) = 5
Delta(5,1) = 5 : Delta(5,2) = 5
n = len(inputstring)
state = 1
For i=1 To n
Symbol = Mid(inputstring,i,1)
If Symbol="0" Then
j=1
Else If Symbol="1" Then
j=2
Else
state =5 : Exit For
End If
state = Delta(state,j)
Next
If state =3 Then
'цепочка допускается
Else
'цепочка не допускается
End If
самостоятельно:
1. проверить является ли число двоичным
2. проверить принадлежит ли грамматике (нетерминалами которой является 0 и 1): четное число 1 и нечетное число 0 цепочка
(нетерминалы: 0,1)

Добавлено через 5 часов 56 минут
Как решить задачу построения конечного автомата
Цепочку необходимо пройти только один раз при считывании, особенность конечных автоматов в том, что у них нет памяти - нельзя посмотреть ни предыдущий, ни следующий символ.
Берем какую-нибудь цепочку для примера. 00111010001
Автомат, который нужно построить: четное число 1, нечетное число 0. Это грамматика.
У нас есть входное состояние конечного автомата. Занумеруем его цифрой I.
Составляем таблицу из 3 столбцов. Первый столбец это номера состояним конечного автомата, второй столбец это изменение состоянии автомата при получении символа 0. Второй столбец - это изменение состояния автомата при получении символа 1.
Первым символом може быть либо 0, либо 1. Если получаем на входе другой символ, то получаем особое состояние пустой цепочки. Обозначим его как N - из N автомат переходит только в N вне зависимости от того, какие символы дальше. Если автомат перешел в состояние N, это означаем, что цепочка не принадлежит заданной грамматике. Если это 0, то переходим в состояние II, если это 1, то переходим в состояние III. Записываем в таблицу значения:
№ 0 1
I II III
II
III
N N N
Автомат находится в состоянии II. Вторым символом в цепочке может быть либо 0, либо 1. Если это 0, то мы получили четное число 0. Обозначим состояние четности числа 0 через IV. В состоянии II у нас нечетное количество 0. Получим следующую таблицу:
№ 0 1
I II III
II
III
IV
N N N
Если в IV состоянии получен еще один ноль, то мы получили нечетное количество 0, значит авмомат может вернуться в сотояние II из IV. Пометим это в таблице:
№ 0 1
I II III
II IV
III
IV II
N N N
Если в IV состоянии получена 1, то мы получили четную цепочку 1, значит цепочка не допускается - переходим в состояние N. Пометим в таблице:
№ 0 1
I II III
II IV
III
IV II N
N N N

Если во II состоянии получили 1, то мы получили состоянии нечетности 0 и перешли в сосотяние нечетности 1, а это состояние номер III.
Пометим в таблице:
№ 0 1
I II III
II IV III
III
IV II N
N N N

Автомат находится в состоянии III. Символом в цепочке может быть либо 0, либо 1. Если 0, то количество 1 нечетно, значт цепочка не принадлежит грамматике. Пометим в таблице переход в состояние N:
№ 0 1
I II III
II IV III
III N
IV II N
N N N
Автомат находится в состоянии III. Если получили 1 то количество единиц стало четным. Обозначим состояние четности 1 как V и зафиксируем переход из состояния III в V.
№ 0 1
I II III
II IV III
III N V
IV II N
V
N N N
Рассмотрим состояние V. Если в этом состоянии получили 0, то перешли в состояние нечетного количества 0, а это II. Если получили 1, то перешли в состояние нечетности 1, это III.
№ 0 1
I II III
II IV III
III N V
IV II N
V II III
N N N
Какие состояния являются состояниями выхода:
I четность и 0 и 1
II нечетность 0
III нечетность 1
IV четность 0
V четность 1
Не являются состояниями выхода III и IV.
Являются состояниями выхода II и V.
Полученный автомат - детерминированный. и его нельзя улучшить, составляя классы эквивалентности.
Подробнее написано в прекрасной книге Ахо и Ульмана.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2011, 17:04

Нарисовать диаграмму состояний конечного автомата
Добрый день. Помогите нарисовать диаграмму состояний конечного автомата....

Построить графическую модель конечного автомата
Добрый день, помогите пожалуйста реализовать задачу. Необходимо построить...

Задана диаграмма переходов конечного автомата
Если задана диаграмма переходов конечного автомата, то как построить схему его...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru