Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
Nerewar
0 / 0 / 0
Регистрация: 25.10.2014
Сообщений: 48
1

Конечный автомат

29.12.2015, 00:04. Просмотров 1042. Ответов 2
Метки нет (Все метки)

Доброго времени суток! Помогите, пожалуйста, разобрать задачу.
Дано условие: C*C(aa)b(a)*(aa|ab)
Для этого нужно написать задачу на конечный автомат.
Схему сделал, но с кодом какая-то неразбериха.
По схеме выходит, что конечными точками являются 3 и 4.
+ Ко всему с самого начала строки, преподаватель сказал, что значение c должно вводиться сколько угодно раз (сколько он сам введёт) и это не должно прерывать всю цепочку к точкам 3 или 4.
Таковыми цепочками являются: c......caa , c.........cab. (кратчайшие цепочки)
P.S.: До того, как я закомментировал те строки, что в коде, значение s всегда возвращалось 1. Когда закомментировал выдавало уже значения 1, 2, 3 или 1, 2, 4. Но эта ситуация не соответствовала условию что c может быть сколько угодно...
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <string>
using namespace std;
int state(int s, char c)
{
    if(c!='a' && c!='b' && c!='c') s=-1;
    switch(s)
    {
        case 0: {
         /*   if(c='a') s=-1;
            if(c='b') s=-1;*/
            if(c='c') s=1;
            break;
        }
        case 1: {
            if(c='a') s=2;
          /*  if(c='b') s=5;
            if(c='c') s=1;*/
            break;
        }
        case 2: {
            if(c='a') s=3;
          /*  if(c='b') s=4;*/
            /*if(c='c') s=-1;*/
            break;
        }
        case 3: {
            if(c='a') s=2;
            if(c='b') s=5;
            if(c='c') s=-1;
            break;
        }
        case 4: {
            if(c='a') s=-1;
            if(c='b') s=-1;
            if(c='c') s=-1;
            break;
        }
        case 5: {
            if(c='a') s=-1;
            if(c='b') s=-1;
            if(c='c') s=6;
            break;
        }
        case 6: {
            if(c='a') s=1;
            if(c='b') s=-1;
            if(c='c') s=-1;
            break;
        }
        default: s=-1;
    }
    return s;
}
int main()
{
    int i,s=0;
    char c;
    string l;
    cin >> l;
    for (i=0; i<l.size(); i++)
    {
        c=l[i];
        s=state(s,c);
        cout << "s = " << s << endl;
    }
    if(s==3 || s==4) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

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

Конечный автомат
Задание типа нахождения кратчайшей последовательности вставок и удалений одного...

Конечный автомат
Всем доброго времени суток! Я в программировании кое-что понимаю, но именно что...

Конечный автомат
Здравствуйте! Возникли проблемы с задачей: дан набор правил q0 -&gt; aq1, q1 -&gt;...

Конечный автомат
Нужно написать программу работы данного автомата.

Детерминированный конечный автомат
Всем привет,у меня такая проблема: Написал в билдере код,но не получается...

2
Nerewar
0 / 0 / 0
Регистрация: 25.10.2014
Сообщений: 48
29.12.2015, 00:21  [ТС] 2
Вот схема, составленная для этого автомата...
0
Миниатюры
Конечный автомат  
Mr.X
Эксперт С++
3182 / 1709 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
29.12.2015, 03:33 3
Цитата Сообщение от Nerewar Посмотреть сообщение
Дано условие: C*C(aa)b(a)*(aa|ab)
Не очень понял ваше условие и схему. Если после (aa) подразумевается звездочка, т.е. если регулярное выражение имеет вид c*c(aa)*ba*(aa|ab), то программа ниже.
Написать ее совершенно несложно, если правильно составить правила перехода и почитывать прикрепленные темы.
Итак идем в тему шаблонов задач в это сообщение. В приведенной там программе в классе-наследнике записываем список состояний, правила перехода и список допускающих состояний.
Кстати, тот автомат, который я составил для вашей задачи, оказался минимальным. Это я проверил на вот этой моей программе.
Итак, решение вашей задачи:
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
/////////////////////////////////////////////////////////////////////////////////////////
//Построить автомат, распознающий регулярные выражения вида: c*c(aa)*b(a)*(aa|ab)
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
/////////////////////////////////////////////////////////////////////////////////////////
class   T_FSM_base  //Базовый класс для любого конечного автомата. В классе-наследнике
                    //достаточно определить значения состояний, заполнить таблицу переходов
                    //и множество допускающих состояний.
{
    //-----------------------------------------------------------------------------------
    typedef int                                                 T_state;
    typedef std::pair   < T_state,              char        >   T_state_and_symb;
    typedef std::map    < T_state_and_symb,     T_state     >   T_state_transition_table;
    typedef std::set    < T_state                           >   T_states;
    //-----------------------------------------------------------------------------------
    T_state                     cur_state_;
    T_state_transition_table    state_transition_table_;
    T_states                    final_states_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_FSM_base( T_state     start_state )
        :
        cur_state_( start_state )
    {}
    //-----------------------------------------------------------------------------------
    bool    string_is_accepted( T_str   &   s )
    {
        for( auto  c_it = s.begin(); c_it != s.end(); ++c_it )
        {
            if  (
                    !successfully_set_cur_state_for_symb( *c_it )
                )
            {
                return  false;
            }
        }//for
 
        return  cur_state_is_final();
    }
    //-----------------------------------------------------------------------------------
    void    add_rule
        (
            T_state     cur_state,
            char        symb,
            T_state     new_state
        )
    {
        state_transition_table_
            [    
                T_state_and_symb
                    (
                        cur_state,
                        symb
                    )
            ]
        
            =   new_state;
    }
    //-----------------------------------------------------------------------------------
    void    add_final_state( T_state    state )
    {
        final_states_.insert( state );
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    bool    successfully_set_cur_state_for_symb( char   symb )
    {
        auto    tr_it   =   state_transition_table_.find
                                (
                                    T_state_and_symb
                                        (
                                            cur_state_,
                                            symb
                                        )
                                );
 
        bool    bool_res    =   tr_it   !=  state_transition_table_.end();
 
        if( bool_res )
        {
            cur_state_  =   tr_it->second;
        }
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    bool    cur_state_is_final()
    {
        return  final_states_.count( cur_state_ )   !=  0;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
class   T_FSM_cab   :   public  T_FSM_base
{
    //-----------------------------------------------------------------------------------
    enum    T_state_val
    {
        start,
        _2,
        _3,
        _4,
        _5,
        _6,
        _7,
        _8,
        _9,
        _10
    };
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_FSM_cab()
        :
        T_FSM_base( start )
    {
        add_rule(   start,  'c',    _2      );
        add_rule(   _2,     'a',    _3      );
        add_rule(   _2,     'b',    _4      );
 
        add_rule(   _2,     'c',    _2      );
        add_rule(   _3,     'a',    _2      );
        add_rule(   _4,     'a',    _5      );
 
        add_rule(   _5,     'a',    _6      );
        add_rule(   _5,     'b',    _7      );
        add_rule(   _6,     'a',    _6      );
 
        add_rule(   _6,     'b',    _7      );
 
        add_final_state( _6 );
        add_final_state( _7 );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  "Проверка регулярного выражения c*c(aa)*b(a)*(aa|ab)"
                    <<  std::endl;
 
        std::cout   <<  "Введите строку символов:"
                    <<  std::endl;
 
        T_str   s;
        getline( std::cin, s );
 
        T_FSM_cab   fsm;
 
        std::cout   <<  std::endl
                    <<  (
                            fsm.string_is_accepted(s)
                                ?   "Строка допускается"
                                :   "Строка НЕ допускается"
                        )
 
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2015, 03:33

Конечный автомат для строк
Конечный автомат для строк используя switch. Помогите пожалуйста...

Конечный автомат. Построить транслитератор
Построить транслитеротор: кириллица-&gt;латиница, а также конечный автомат,...

Конечный автомат. Лабиринт (поиск в глубину)
Пусть лабиринт задан двумерным массивом bool, индексы ячеек соответствуют их...


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

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

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