Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
#1

Преобразуйте КА к детерминированному виду и минимизируйте полученный КА - C++

13.12.2012, 23:15. Просмотров 887. Ответов 15
Метки нет (Все метки)

Помогите с решением задачки:
Задан КА: M({S,R,Z}, {a,b}, δ, S, {Z}), δ(S,a) = {S.R}, δ(R,b) = {R}. δ(R,a) = {Z}.
Преобразуйте его к детерминированному виду и минимизируйте полученный КА.

Добавлено через 20 часов 17 минут
КА - Конечный автомат
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2012, 23:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Преобразуйте КА к детерминированному виду и минимизируйте полученный КА (C++):

С виду простое однородное уравнение. Нужно привести к виду F(x,y)=C - Дифференциальные уравнения
Из 250 задач ВУЗа решил все, за исключением единственной! (Хотя по части задач были недопонимания - спасибо форуму!) Ветку читал...

Преобразуйте конструктор - C++
Дан класс MyString: class MyString { char *ps; int size,len; public: MyString(); MyString(int...

Преобразуйте IP-адрес - Информатика
Преобразуйте IP-адрес, шестнадцатеричное представление которого равно C22F 1582, в десятичный формат, разделенный точками.

Преобразуйте одномерный массив - C++
Преобразуйте одномерный массив таким образом, чтобы сумма элементов в его первой половине была бы как можно ближе к сумме элементов его...

Преобразуйте последовательность по правилу - Pascal
Пусть даны вещественные числа а1, а2, ..., а20. Преобразуйте последовательность по правилу: большее из аi и аi+10 (i = 1,...,10) примите в...

Преобразуйте последовательность по правилу - C#
Напишите программу для решения задачи: Пусть даны вещественные числа а1, ..., а20. Преобразуйте эту последовательность по правилу:...

15
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
16.12.2012, 19:49  [ТС] #2
намекните хотя бы как это делать...
0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
21.12.2012, 13:32  [ТС] #3
НКА выглядит так:
Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
___
P.S. всё приходится делать самому...
0
Kuzia domovenok
21.12.2012, 13:39
  #4

Не по теме:

по-моему, ты ошибся разделом

0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
21.12.2012, 23:33  [ТС] #5
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение

Не по теме:

по-моему, ты ошибся разделом

так всё это дело надо преобразовать и потом написать на с++
0
Kuzia domovenok
1951 / 1804 / 140
Регистрация: 25.03.2012
Сообщений: 6,245
Записей в блоге: 1
21.12.2012, 23:58 #6
Цитата Сообщение от VanUliK Посмотреть сообщение
так всё это дело надо преобразовать и потом написать на с++
я о том, что тут довольно много народу может помочь с программой, тем более на С++, но это не значит, что все мы разбираемся в автоматике. Мне вот все эти твои термины ни о чём не говорят. Я уверен, что ты мог бы сначала разобраться со всей теорией автоматики, а только потом ставить задачу для программистов.
0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
22.12.2012, 00:35  [ТС] #7
с приведением я разобрался, как опишу в электронном виде, выложу здесь, но как описать то, что мне надо описать на си
0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
22.12.2012, 04:04  [ТС] #8
Итого:
Детерминированный конечный автомат

M` ({S, SR, R, SRZ, Z}, {a, b}, δ`, S, {Z}),

δ` (S , a) = {SR}
δ` (R , a) = {Z}
δ` (R , b) = {R}
δ` (SR , a) = {SRZ}
δ` (SR , b) = {R}
δ` (SRZ , a) = {SRZ}
δ` (SRZ , b) = {R}

Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
Вот теперь надо описать этот автомат на с++, т.е.: консольное приложение, на вход подается какая-то цепочка (её вводит пользователь) символов, и должна проходить проверка прохода от начального состояния к конечному (как-то так, не знаю как это словами объяснить).
0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
22.12.2012, 11:33  [ТС] #9
Нашел ошибку в графе, вот исправленный:
Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
23.12.2012, 12:01  [ТС] #10
Вот с этим надеюсь понятней будет, помогите допилить
C++
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
31
32
33
34
35
36
37
38
#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    int state=1;
    char in;
    int k=0;
    in = getchar();
    while(k == 0 || in == 'a' || in == 'b')
    {
        switch (state)
        {
        case 1:
            if(in == 'a') state = 2; //если a, то из S в SR
            else if (cout<< "Error"<<endl) //если не подходит - вывести "ОШИБКА"
                break;
        case 2: // находимся в состоянии SR
            if(in == 'b') state = 4; //если b, то из SR в R
            else if(in == 'a') state = 3; //если a, то из SR в SRZ
                else if(in == 'a') state = 3; //если a, то из SRZ в SRZ
                else if(in == 'b') state = 4; //если b, то из SRZ в R
            break;
        case 3: // находимся в состоянии R
            if(in == 'b') state = 4; //если b, то из R в R
            else if (in == 'a') state = 5;  //если a, то из R в Z
            break;
        case 4: // проверка на нажатие enter, конечный автомат отработал.
            if(in == 10)
            {cout<<"OK"<<endl;}
            k=1;
            break;
        }
        in = getchar();
    }
}
Добавлено через 12 часов 20 минут
в case 2 как-то не правильно обрабатывается.
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2012, 14:48 #11
Цитата Сообщение от VanUliK Посмотреть сообщение
Детерминированный конечный автомат
А почему вы решили, что это минимальный автомат? Моя программа минимизирует его до четырех состояний.
0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
23.12.2012, 16:26  [ТС] #12
мне хотя бы это сделать без минимизации
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2012, 19:07 #13
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от VanUliK Посмотреть сообщение
мне хотя бы это сделать без минимизации
На самом деле и из рисунка видно, что состояния SR и SRZ можно склеить.
C++
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
/////////////////////////////////////////////////////////////////////////////////////////
class T_FSM_aabba
{
    enum T_state
    {
        START_STATE,
        aa_STATE,
        aabb_STATE,
        aabba_FINISH_STATE
    };
    //-----------------------------------------------------------------------------------
    typedef std::set    < T_state   >                           T_states;
    typedef char                                                T_symbol;
    typedef std::set    < T_symbol  >                           T_symbols;
    typedef std::pair   < T_state,              T_symbol    >   T_state_and_symbol;
    typedef std::map    < T_state_and_symbol,   T_state     >   T_state_for_state_and_symbol;
    //-----------------------------------------------------------------------------------
    T_symbols                       alphabet_;
    T_state_for_state_and_symbol    state_for_state_and_symbol_;
    T_states                        accept_states_;
    T_state                         cur_state_;
    //--------------------------------------------------------------------------------
public:
    T_FSM_aabba()
        :
        cur_state_( START_STATE )
    {
        fill_alphabet                       ();
        fill_state_for_state_and_symbol     ();
        fill_accept_states                  ();
    }
    //--------------------------------------------------------------------------------
    bool  string_is_good(const T_str&  s)
    {
        for (
                T_str::const_iterator
                symb_it     =   s.begin     ();
                symb_it     !=  s.end       ();
                ++symb_it
            )
        {
            if  (
                    alphabet_.count( *symb_it ) == 0
                )
            {
                std::cout   <<  "Недопустимый символ во входной строке!"
                            <<  std::endl;
 
                return  false;
            }//if
 
            cur_state_   =   state_for_state_and_symbol_
                                [
                                    T_state_and_symbol
                                        (
                                            cur_state_,
                                            *symb_it
                                        )
                                ];
        }//for
 
        return  accept_states_.count( cur_state_ )  !=  0;
    }
    //--------------------------------------------------------------------------------
private:
    //--------------------------------------------------------------------------------
    void  fill_alphabet()
    {
        alphabet_.insert('a');
        alphabet_.insert('b');
    }
    //--------------------------------------------------------------------------------
    void  fill_state_for_state_and_symbol()
    {
        state_for_state_and_symbol_[ T_state_and_symbol( START_STATE,   'a'     )     ]   =   aa_STATE;
 
        state_for_state_and_symbol_[ T_state_and_symbol( aa_STATE,      'a'     )     ]   =   aa_STATE;
        state_for_state_and_symbol_[ T_state_and_symbol( aa_STATE,      'b'     )     ]   =   aabb_STATE;
 
        state_for_state_and_symbol_[ T_state_and_symbol( aabb_STATE,    'a'     )     ]   =   aabba_FINISH_STATE;
        state_for_state_and_symbol_[ T_state_and_symbol( aabb_STATE,    'b'     )     ]   =   aabb_STATE;
    }
    //--------------------------------------------------------------------------------
    void  fill_accept_states()
    {
        accept_states_.insert( aabba_FINISH_STATE );
    }
    //--------------------------------------------------------------------------------
};
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        std::cout   <<  "Введите строку для проверки:"
                    <<  std::endl;
 
        T_str   s;
        std::cin    >>  s;
 
        T_FSM_aabba     FSM_aabba;
        std::cout   <<  "Строка "
                    <<  (
                            FSM_aabba.string_is_good(s) 
                                ?   ""
                                :   "НЕ "
                        )
 
                    <<  "допускается."
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }
}
0
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
24.12.2012, 04:14  [ТС] #14
не совсем понял
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.12.2012, 09:25 #15
Цитата Сообщение от VanUliK Посмотреть сообщение
не совсем понял
Сделал заполнение переходов более читаемым:
C++
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
/////////////////////////////////////////////////////////////////////////////////////////
class T_FSM_aabba
{
    enum T_state
    {
        START_STATE,
        aa_STATE,
        aabb_STATE,
        aabba_FINISH_STATE
    };
    //-----------------------------------------------------------------------------------
    typedef std::set    < T_state   >                           T_states;
    typedef char                                                T_symbol;
    typedef std::set    < T_symbol  >                           T_symbols;
    typedef std::pair   < T_state,              T_symbol    >   T_state_and_symbol;
    typedef std::map    < T_state_and_symbol,   T_state     >   T_state_for_state_and_symbol;
    //-----------------------------------------------------------------------------------
    T_symbols                       alphabet_;
    T_state_for_state_and_symbol    state_for_state_and_symbol_;
    T_states                        accept_states_;
    T_state                         cur_state_;
    //--------------------------------------------------------------------------------
public:
    T_FSM_aabba()
        :
        cur_state_( START_STATE )
    {
        fill_alphabet                       ();
        fill_state_for_state_and_symbol     ();
        fill_accept_states                  ();
    }
    //--------------------------------------------------------------------------------
    bool  string_is_good(const T_str&  s)
    {
        for (
                T_str::const_iterator
                symb_it     =   s.begin     ();
                symb_it     !=  s.end       ();
                ++symb_it
            )
        {
            if  (
                    alphabet_.count( *symb_it ) == 0
                )
            {
                std::cout   <<  "Недопустимый символ во входной строке!"
                            <<  std::endl;
 
                return  false;
            }//if
 
            cur_state_   =   state_for_state_and_symbol_
                                [
                                    T_state_and_symbol
                                        (
                                            cur_state_,
                                            *symb_it
                                        )
                                ];
        }//for
 
        return  accept_states_.count( cur_state_ )  !=  0;
    }
    //--------------------------------------------------------------------------------
private:
    //--------------------------------------------------------------------------------
    void  fill_alphabet()
    {
        alphabet_.insert('a');
        alphabet_.insert('b');
    }
    //--------------------------------------------------------------------------------
    void  fill_state_for_state_and_symbol()
    {
        set_transition( START_STATE,    'a',    aa_STATE            );
 
        set_transition( aa_STATE,       'a',    aa_STATE            );
        set_transition( aa_STATE,       'b',    aabb_STATE          );
 
        set_transition( aabb_STATE,     'a',    aabba_FINISH_STATE  );
        set_transition( aabb_STATE,     'b',    aabb_STATE          );
    }
    //--------------------------------------------------------------------------------
    void  set_transition
        ( 
            T_state     state_from,
            T_symbol    symbol,
            T_state     state_to
        )
    {
        state_for_state_and_symbol_
            [ 
                T_state_and_symbol
                    (
                        state_from,
                        symbol
                    )
            ]
            =   state_to;
    }
    //--------------------------------------------------------------------------------
    void  fill_accept_states()
    {
        accept_states_.insert( aabba_FINISH_STATE );
    }
    //--------------------------------------------------------------------------------
};
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        std::cout   <<  "Введите строку для проверки:"
                    <<  std::endl;
 
        T_str   s;
        std::cin    >>  s;
 
        T_FSM_aabba     FSM_aabba;
        std::cout   <<  "Строка "
                    <<  (
                            FSM_aabba.string_is_good(s) 
                                ?   ""
                                :   "НЕ "
                        )
 
                    <<  "допускается."
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }
}
0
24.12.2012, 09:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2012, 09:25
Привет! Вот еще темы с ответами:

Преобразуйте программу на язык С++ - C++
Кто может сделать перевод на С Pascala на С++ эту программу program MaxElem; uses Crt; type Mas = array of Real; var A: Mas; ...

преобразуйте числовую переменную в символьную - QBasic
преобразуйте числовую переменную в символьную

Заданные векторы преобразуйте по правилу - C#
Заданные векторы X(N) и Y(N) преобразуйте по правилу: большее из xi и yi примите в качестве нового значения xi , а меньшее — в качестве...

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


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

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

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