Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
lezh1k
36 / 36 / 5
Регистрация: 03.06.2010
Сообщений: 120
1

Регулярное выраженив в ДКА

23.06.2015, 12:44. Просмотров 218. Ответов 1
Метки нет (Все метки)

Добрый день.
В данный момент у меня реализован уже перевод регулярного выражения в ДКА. Но есть одна ошибка, с которой не получилось справиться сразу .

Допустим, есть у меня регулярное выражение "cacadfe" .

Я получил вот такую таблицу переходов :

__| a | b | c | d | e |
0 | 0 | 0 | 1 | 0 | 0 |
1 | 2 | 0 | 1 | 0 | 0 |
2 | 0 | 0 | 3 | 0 | 0 |
3 | 4 | 0 | 1 | 0 | 0 |
4 | 0 | 5 | 1 | 0 | 0 |
5 | 0 | 0 | 1 | 6 | 0 |
6 | 0 | 0 | 1 | 0 | 7 |
7f | 0 | 0 | 1 | 0 | 0 |

Естественно там, где жирная единичка, должна быть 3. Вопрос собственно в том, как мне определить, что там должна быть 3?

Для примера если взять последовательность "cacacadfe", то такой автомат её не найдет как раз из-за неправильного перехода в 4м состоянии.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2015, 12:44
Ответы с готовыми решениями:

Регулярное выражение в НКА и ДКА
Доброго времени суток! У меня проблема с построением НКА, и преобразованием его в ДКА из...

ДКА
Построить дка распознающий числа в двоичной системе которые делятся на 3

Минимизация ДКА
Привет всем. Впервые минимизирую ДКА и прошу меня проверить, верно ли я все сделал. Дан...

Построить ДКА
помогите, плизззз)) Построить конечный автомат (детерминированного типа), позволяющий...

Построить ДКА
Построить ДКА, допустимым для которого является язык над алфавитом {0,1}, состоящий из множества...

1
lezh1k
36 / 36 / 5
Регистрация: 03.06.2010
Сообщений: 120
26.06.2015, 06:50  [ТС] 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
void CF_NFA::CDfaTable::patch_for_loopbacks()
{
  for (size_t i = 0; i < m_cols; ++i) {
    if (m_table[0][i].cell_val.state == 0) continue;
 
    for (size_t j = 1; j < m_rows_real; ++j) {
      if (m_table[j][i].cell_val.state == 0) continue;
 
      //patch!!!!!
      std::vector<word_t> st;
 
      int prev_state = find_way_to_state(j, i, st);
      int curr_state = j;
 
      bool br = false;
      for (std::vector<word_t>::reverse_iterator ri = st.rbegin(); ri != st.rend(); ++ri) {
        if (m_table[curr_state][*ri].cell_val.state == 0) {
          m_table[curr_state][*ri].cell_val.state = m_table[prev_state][*ri].cell_val.state;
          br = true;
          break;
        }
        curr_state = m_table[curr_state][*ri].cell_val.state;
        prev_state = m_table[prev_state][*ri].cell_val.state;
      }
 
      if (!br)
        m_table[curr_state][i].cell_val.state = m_table[j][i].cell_val.state;
    }
  }
 
  for (size_t i = 0; i < m_cols; ++i) {
    if (m_table[0][i].cell_val.state == 0) continue;
 
    for (size_t j = 0; j < m_rows_real; ++j) {
      if (m_table[j][i].cell_val.state != 0) continue;
      m_table[j][i].cell_val.state = m_table[0][i].cell_val.state;
    }
  }
}
Тему можно закрыть.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2015, 06:50

Моделирование ДКА
Задание: Построить конечный автомат, распознающий последовательности из нулей и единиц, содержащие...

Представление ДКА в коде
Здравствуйте! Подскажите пожалуйста, как можно представить детерминированный конечный автомат в...

Регулярные языки, ДКА
Верно ли, что для всякого регулярного языка существует принимающий его ДКА с единственным финальным...


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

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

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