Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

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

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

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

Не по теме:

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

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

Не по теме:

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

так всё это дело надо преобразовать и потом написать на с++
Kuzia domovenok
1887 / 1742 / 117
Регистрация: 25.03.2012
Сообщений: 5,916
Записей в блоге: 1
21.12.2012, 23:58     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА #6
Цитата Сообщение от VanUliK Посмотреть сообщение
так всё это дело надо преобразовать и потом написать на с++
я о том, что тут довольно много народу может помочь с программой, тем более на С++, но это не значит, что все мы разбираемся в автоматике. Мне вот все эти твои термины ни о чём не говорят. Я уверен, что ты мог бы сначала разобраться со всей теорией автоматики, а только потом ставить задачу для программистов.
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
22.12.2012, 00:35  [ТС]     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА #7
с приведением я разобрался, как опишу в электронном виде, выложу здесь, но как описать то, что мне надо описать на си
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}

Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
Вот теперь надо описать этот автомат на с++, т.е.: консольное приложение, на вход подается какая-то цепочка (её вводит пользователь) символов, и должна проходить проверка прохода от начального состояния к конечному (как-то так, не знаю как это словами объяснить).
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
22.12.2012, 11:33  [ТС]     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА #9
Нашел ошибку в графе, вот исправленный:
Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
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 как-то не правильно обрабатывается.
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2012, 14:48     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА #11
Цитата Сообщение от VanUliK Посмотреть сообщение
Детерминированный конечный автомат
А почему вы решили, что это минимальный автомат? Моя программа минимизирует его до четырех состояний.
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
23.12.2012, 16:26  [ТС]     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА #12
мне хотя бы это сделать без минимизации
Mr.X
Эксперт С++
3039 / 1684 / 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;
    }
}
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
24.12.2012, 04:14  [ТС]     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА #14
не совсем понял
Mr.X
Эксперт С++
3039 / 1684 / 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;
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.12.2012, 03:58     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
Еще ссылки по теме:

Преобразуйте эту строчку так, чтобы сначала в ней шли цифры, а потом - все буквы исходной строчки... C++
почему не получается правильно вывести полученный массив на экран C++
Преобразуйте массив так, чтобы все положительные элементы массива стали отрицательными и наоборот C++
Преобразуйте одномерный массив C++
Преобразуйте конечную сумму в бесконечный ряд, используя оператор цикла while C++

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

Или воспользуйтесь поиском по форуму:
VanUliK
13 / 13 / 3
Регистрация: 13.02.2012
Сообщений: 219
Записей в блоге: 1
25.12.2012, 03:58  [ТС]     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА #16
вот что мне надо было
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
#include "stdafx.h"
#include "iostream"
#include "conio.h"
#include <string>
 
using namespace std;
 
enum State //перечисления
{
 S, SR, R, SRZ, Z
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    State state = S;
    char in;
    int k=0;
    in = getchar();
    string result = "";
    while(k == 0 && (in == 'a' || in == 'b' || in == 10))
    {
        switch (state)
        {
        case S:
            if(in == 'a') state = SR;
            else if (in != 'a') k = 1, result = "Ne mozhet nachinatsya s 'b'";
            break;
        case SR:
            if(in == 'a') state = SRZ;
            else if(in == 'b') state = R;
            break;
        case R:
              if (in == 'a') state = Z;
            break;
        case SRZ: 
            if (in == 'b') state = R;
            break;
        case Z:
            if(in == 10)
            result = "OK";
            k=1;
             break;
        }
     in = getchar();
    }
 if(result == "") result = "ERROR";
 cout<<result<<endl;
 _getch();
}
только требует небольшой доработки, но в целом работает...
- не работает когда строка короче 3 символов; нашел решение (теоретическое): необходимо добавить ещё одно состояние ER и в каждый кейс дописать
C++
1
else (in==10); state = ER;
- когда цепочка подходит, надо нажать второй раз enter для вывода сообщения - "OK"
Yandex
Объявления
25.12.2012, 03:58     Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
Ответ Создать тему
Опции темы

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