0 / 0 / 0
Регистрация: 16.04.2015
Сообщений: 2
1

Задачи на конечные автоматы

16.04.2015, 11:33. Показов 14031. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Я не знаю как делать на с++ конечные автоматы,
Задание 1. Построить автомат, распознающий регулярные выражения вида: (101)*(110)*
Задание 2. Построить конечный автомат, распознающий регулярные выражения вида:
(+ | - | )digit*.digit digit*(Е|е(+|-|)digit+),
где digit={0,1,2,3,4,5,6,7,8,9}, E или e –символы английского алфавита.
Задание 3. Построить конечный автомат, распознающий идентификатор языка высокого уровня, где
• !,#,$,%,^,&, #32,(,),{,},[,]-символы, которые не могут встречаться в имени идентификатора (#32 – символ пробела);
• идентификатор состоит из символов английского алфавита.

Я начинаю только работать в с++ в институте и по ТЯП задали вот такое
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.04.2015, 11:33
Ответы с готовыми решениями:

Конечные автоматы
Помогите пожалуйста постоить графически НКА и ДКА по регулярному выражению 34(43343/44334)* и если...

Конечные автоматы!?!?!?!?
Ребят тупая задача сложнность 11 % а условие тупое не понятное кто может объяснить и условие и...

Конечные автоматы с реализацией
Есть такая работа,делал не я. http://f1.s.qip.ru/G1CCNne7.png http://f2.s.qip.ru/G1CCNne8.png ...

Конечные автоматы (с++). Помогите, пожалуйста!
Помогите, пожалуйста, сделать лабораторную работу! Разработать и реализовать представление...

4
7789 / 6556 / 2984
Регистрация: 14.04.2014
Сообщений: 28,657
16.04.2015, 17:14 2
Как-то так для 2. Возможно граф не совсем верный, у тебя не понятно описано.
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
#include <iostream>
#include <cstdlib>
#include <string>
#include <locale>
#include <map>
#include <utility>
 
 
int main()
{
    std::locale::global(std::locale(""));
 
    std::map<std::pair<int, char>, int> D; // таблица переходов
 
    D[std::make_pair(0, '+')] = 1;
    D[std::make_pair(0, '-')] = 1;
    D[std::make_pair(0, '.')] = 2;
    D[std::make_pair(1, '.')] = 2;
    D[std::make_pair(3, 'e')] = 4;
    D[std::make_pair(3, 'E')] = 4;
    D[std::make_pair(4, '+')] = 5;
    D[std::make_pair(4, '-')] = 5;
 
    for (char ch = '0'; ch <= '9'; ++ch)
    {
        D[std::make_pair(0, ch)] = 1;
        D[std::make_pair(1, ch)] = 1;
        D[std::make_pair(2, ch)] = 3;
        D[std::make_pair(3, ch)] = 3;
        D[std::make_pair(4, ch)] = 6;
        D[std::make_pair(5, ch)] = 6;
        D[std::make_pair(6, ch)] = 6;
    }
 
    std::string s;
    std::cin >> s;
 
    int state = 0; // состояние
    std::string::iterator it;
 
    for (it = s.begin(); it != s.end(); ++it) // входные символы
    {
        std::map<std::pair<int, char>, int>::iterator ns_it = D.find(std::make_pair(state, *it));
        if (ns_it == D.end()) break; // нет перехода
        state = ns_it->second; // следующее состояние
    }
 
    // 3 и 6 - допускающие состояния
    if ((state == 3 || state == 6) && it == s.end()) std::cout << "Yes.\n";
    else std::cout << "No.\n";
 
    system("pause");
    return 0;
}
Миниатюры
Задачи на конечные автоматы  
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
17.04.2015, 08:24 3
Задание 1.
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
/////////////////////////////////////////////////////////////////////////////////////////
//Построить автомат, распознающий регулярные выражения вида: (101)*(110)*
/////////////////////////////////////////////////////////////////////////////////////////
#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_101_110   :   public  T_FSM_base
{
    //-----------------------------------------------------------------------------------
    enum    T_state_val
    {
        start,
        _1,
        _10,
        _11
    };
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_FSM_101_110()
        :
        T_FSM_base( start )
    {
        add_rule(   start,  '1',    _1      );
        add_rule(   _1,     '0',    _10     );
        add_rule(   _1,     '1',    _11     );
        add_rule(   _10,    '1',    start   );
        add_rule(   _11,    '0',    start   );
 
        add_final_state( start );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  "Проверка регулярного выражения (101)*(110)*"
                    <<  std::endl;
 
        std::cout   <<  "Введите строку символов:"
                    <<  std::endl;
 
        T_str   s;
        getline( std::cin, s );
 
        T_FSM_101_110   fsm;
 
        std::cout   <<  std::endl
                    <<  (
                            fsm.string_is_accepted(s)
                                ?   "Строка допускается"
                                :   "Строка НЕ допускается"
                        )
 
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }
}
2
0 / 0 / 0
Регистрация: 16.04.2015
Сообщений: 2
17.04.2015, 10:29  [ТС] 4
Мужики огромное спасибо!!! Но я так накасячил в условии, что прям мне оправдания нету, в каждой из программы должен быть файл типа txt в нём записано выражение регулярно и его вроде как считавывать нужно и проверять верно оно или нет((( огромное спасибо за программы!!!!!
0
1 / 1 / 0
Регистрация: 19.06.2017
Сообщений: 32
19.06.2017, 13:27 5
Кликните здесь для просмотра всего текста
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
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
        char line[500];
       
       while (1){
       
         printf("Введите число:");
        fgets(line,sizeof(line), stdin);
                
                switch(line[0])
                {
                        case '1':
                                printf("Выбран пункт %d\n",1);
                                break;
                        case '2':
                                printf("Выбран пункт %d\n",2);
                                break;
                        case '3':
                                 printf("Выбран пункт %d\n",3);
                                break;
                        case '4':
                                 printf(" Выбран пункт %d\n",4);
                                break;
                        case '5':
                                 printf(" Выбран пункт %d\n",5);
                                break;
                        case '6':
                                 printf("Выбран пункт %d\n",6);
                                break;
                        case '7':
                                 printf("Выбран пункт %d\n",7);
                                break;
                        case '8':
                                 printf(" Выбран пункт %d\n",8);
                                break;
                                default:
                                printf("Ошибка!\n");
                                break;
                        case 'q':
                                 printf("Выход...\n",8);
                                exit(0);
                }
        }
}
//так проще...
0
19.06.2017, 13:27
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.06.2017, 13:27
Помогаю со студенческими работами здесь

Конечные автоматы и грамматики - разобрать код
Доброе утро!Добрые люди сделали программу построения конечных автоматов по регулярным...

Что такое полис и конечные автоматы и для чего используются в с++?
ОЧЕНЬ ХОЧУ ЗНАТЬ. ПОМОГИТЕ!!!!!!!!!

Конечные автоматы
в Pascal строки ограничены апострофами, а комментарии - символами {}, при этом скобка {,...

Конечные автоматы
Вопрос, есть ли какие либо библиотеки на эту тему? Я сам ничего не нашёл. А пытался накидать,...


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

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

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