Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Социальные группы Поиск Сообщения за день Заказать работу  
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 1
1

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

13.12.2012, 23:15. Показов 1739. Ответов 15
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Помогите с решением задачки:
Задан КА: M({S,R,Z}, {a,b}, δ, S, {Z}), δ(S,a) = {S.R}, δ(R,b) = {R}. δ(R,a) = {Z}.
Преобразуйте его к детерминированному виду и минимизируйте полученный КА.

Добавлено через 20 часов 17 минут
КА - Конечный автомат
0
Лучшие ответы (1)
Сообщение: #3905604
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 13.12.2012, 23:15
Ответы с готовыми решениями:

Минимизируйте функцию
Минимизируйте функцию f(x)=((1-e^x sinx))^2

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

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

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

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

___
P.S. всё приходится делать самому...
0
Kuzia domovenok
21.12.2012, 13:39
  #4

Не по теме:

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

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

Не по теме:

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

так всё это дело надо преобразовать и потом написать на с++
0
4063 / 3317 / 924
Регистрация: 25.03.2012
Сообщений: 12,483
Записей в блоге: 1
21.12.2012, 23:58 6
Цитата Сообщение от VanUliK Посмотреть сообщение
так всё это дело надо преобразовать и потом написать на с++
я о том, что тут довольно много народу может помочь с программой, тем более на С++, но это не значит, что все мы разбираемся в автоматике. Мне вот все эти твои термины ни о чём не говорят. Я уверен, что ты мог бы сначала разобраться со всей теорией автоматики, а только потом ставить задачу для программистов.
0
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 1
22.12.2012, 00:35  [ТС] 7
с приведением я разобрался, как опишу в электронном виде, выложу здесь, но как описать то, что мне надо описать на си
0
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 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
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 1
22.12.2012, 11:33  [ТС] 9
Нашел ошибку в графе, вот исправленный:
Преобразуйте КА к детерминированному виду и минимизируйте полученный КА
0
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 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
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
23.12.2012, 14:48 11
Цитата Сообщение от VanUliK Посмотреть сообщение
Детерминированный конечный автомат
А почему вы решили, что это минимальный автомат? Моя программа минимизирует его до четырех состояний.
0
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 1
23.12.2012, 16:26  [ТС] 12
мне хотя бы это сделать без минимизации
0
Эксперт С++
3224 / 1751 / 436
Регистрация: 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
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 1
24.12.2012, 04:14  [ТС] 14
не совсем понял
0
Эксперт С++
3224 / 1751 / 436
Регистрация: 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
14 / 14 / 3
Регистрация: 13.02.2012
Сообщений: 233
Записей в блоге: 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"
0
25.12.2012, 03:58
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 25.12.2012, 03:58
Помогаю со студенческими работами здесь

Преобразуйте последовательность по правилу
Пусть даны вещественные числа а1, а2, ..., а20. Преобразуйте последовательность по правилу: большее...

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

Преобразуйте последовательность по правилу
пусть даны вещественные числа a1,a2,...a20. Преобразуйте последовательность по правилу: большее из...

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru