Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.03.2017, 11:43   #1
dima.karpov
Пользователь
 
Регистрация: 20.11.2016
Сообщений: 51
По умолчанию Конечный автомат. Как добавить состояние?

Разбираюсь с автоматоми.
Рассматриваю пример отсюда http://www.devexp.ru/2011/02/konechnye-avtomaty-v-c/

Код:
enum States
{
	State_Start,
	State_Number,
	State_Word,
	State_Skip
};

States state = State_Start;

const size_t length = text.length();
for (size_t i = 0; i != length; ++i)
{
	const char current = text[i];
 
	switch (state)
	{
	case State_Start:
		if (std::isdigit(current))
		{
			state = State_Number;
		}
		else if (std::isalpha(current))
		{
			state = State_Word;
		}
		break;
	case State_Number:
		if (std::isspace(current))
		{			FoundNumber(); 
			state = State_Start; 
		} 
		else if (!std::isdigit(current)) 
		{ 
			state = State_Skip; 
		} 
		break; 
	case State_Word: 
		if (std::isspace(current)) 
		{ 
			FoundWord(); 
			state = State_Start; 
		} 
		else if (!std::isalpha(current)) 
		{ 
			state = State_Skip; 
		} 
		break; 
	case State_Skip: 
		if (std::isspace(current)) 
		{ 
			state = State_Start; 
		} 
		break; 
	} 
}
а если мне, например, нужно добавить состояние, то как тут быть?
т.е. не в коде добавить, а чтобы пользователю предлагалось и он сам мог добавлять. так возможно реализовать?
dima.karpov вне форума Ответить с цитированием
Старый 12.03.2017, 12:07   #2
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Ну в данном коде очевидно нет, а так да. Просто надо создать какую-то таблицу состояний и функций, и добавлять туда.

std::vector, std::map, ...
std::function, лямбды
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.
Alex11223 вне форума Ответить с цитированием
Старый 12.03.2017, 12:24   #3
dima.karpov
Пользователь
 
Регистрация: 20.11.2016
Сообщений: 51
По умолчанию

Цитата:
Сообщение от Alex11223 Посмотреть сообщение
Ну в данном коде очевидно нет, а так да. Просто надо создать какую-то таблицу состояний и функций, и добавлять туда.

std::vector, std::map, ...
std::function, лямбды
типа этого:
• Алфавит: {0, 1}
• Состояния: {ЧЕТ, НЕЧЕТ}
• Начальное состояние: ЧЕТ
• Функция перехода:
ф(ЧЕТ,0)=ЧЕТ
ф(ЧЕТ,1)=НЕЧЕТ
ф(НЕЧЕТ,0)=НЕЧЕТ
ф(НЕЧЕТ,1)=ЧЕТ
• Допускающие состояния: {НЕЧЕТ}

таблица:
dima.karpov вне форума Ответить с цитированием
Старый 12.03.2017, 12:43   #4
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Нет, таблица не такая как на картинке, тут же уже просто примеры результата с разными входными данными.

Для кода из первого сообщения хватит и просто списка вида Состояние —> Функция
Например std::vector<std::function> (если просто нумеровать состояния, от 0)
Или std::map<std::string, std::function> если строки вместо номеров.

Код:
currentState = mymap[currentState](currentInput);
Вообще по FSM полно библиотек для любого ЯП, можно посмотреть как в них сделано.
https://github.com/jakesgordon/javascript-state-machine
https://github.com/digint/tinyfsm
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.

Последний раз редактировалось Alex11223; 12.03.2017 в 12:51.
Alex11223 вне форума Ответить с цитированием
Старый 12.03.2017, 13:55   #5
dima.karpov
Пользователь
 
Регистрация: 20.11.2016
Сообщений: 51
По умолчанию

что-то типа этого:
Код:
static const Table_Entry    my_table[] =
{
    //  Current   Transition     Next
    //  State ID    Letter     State ID
    {    0,          'A',        1}, // From 0 goto 1 if letter is 'A'.
    {    0,          'B',        2}, // From 0 goto 2 if letter is 'B'.
    {    0,          'C',        3}, // From 0 goto 3 if letter is 'C'.
    {    1,          'A',        1}, // From 1 goto 1 if letter is 'A'.
    {    1,          'B',        3}, // From 1 goto 3 if letter is 'B'.
    {    1,          'C',        0}, // From 1 goto 0 if letter is 'C'.
};
источник http://stackoverflow.com/questions/1...-state-machine

Последний раз редактировалось Alex11223; 12.03.2017 в 14:04.
dima.karpov вне форума Ответить с цитированием
Старый 12.03.2017, 14:03   #6
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Да, только в transition criteria у вас же не просто буква, а более сложная функция.

Я ж показал простой пример для данного случая. Сделать массив или map, где каждому состоянию соответствует функция (ну, указатель на нее).
Функция принимает символ и возвращает новое состояние.
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.
Alex11223 вне форума Ответить с цитированием
Старый 12.03.2017, 15:12   #7
dima.karpov
Пользователь
 
Регистрация: 20.11.2016
Сообщений: 51
По умолчанию

Цитата:
Сообщение от Alex11223 Посмотреть сообщение
Да, только в transition criteria у вас же не просто буква, а более сложная функция.
если честно, я пока не догоняю насчет функции.
что мы будем передавать через нее и что получать, для чего она, если у нас в таблице уже есть начальное состояние, переход (условие) и результат перехода (следующее состояние).
dima.karpov вне форума Ответить с цитированием
Старый 12.03.2017, 15:25   #8
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Я ж сказал что. Передавать входные данные (символ в данном случае), возвращать новое состояние.
Функция это и есть условие перехода. Не будете ж вы все существующие символы пихать в таблицу? (ну в данном случае 256 символов еще можно, но если б был Юникод, то было б совсем уныло).

Наверно для начала надо осознать, что функции тоже можно использовать как данные (переменные, ...), хранить указатели на них.
А с лямбдами даже и создавать новые функции во время работы программы.
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.
Alex11223 вне форума Ответить с цитированием
Старый 15.03.2017, 22:17   #9
dima.karpov
Пользователь
 
Регистрация: 20.11.2016
Сообщений: 51
По умолчанию

Цитата:
Сообщение от Alex11223 Посмотреть сообщение
Я ж сказал что. Передавать входные данные (символ в данном случае), возвращать новое состояние.
Функция это и есть условие перехода. Не будете ж вы все существующие символы пихать в таблицу? (ну в данном случае 256 символов еще можно, но если б был Юникод, то было б совсем уныло).




Наверно для начала надо осознать, что функции тоже можно использовать как данные (переменные, ...), хранить указатели на них.
А с лямбдами даже и создавать новые функции во время работы программы.
еще вопрос: как реализовать эту функцию?
вызываю ф-ю, передаю символ, а эта ф-я возвращает мне результат, что это буква, цифра..
так?
dima.karpov вне форума Ответить с цитированием
Старый 15.03.2017, 22:19   #10
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Зависит от задачи.

Функция новое состояние автомата возвращает.
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.
Alex11223 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
конечный автомат fkty Помощь студентам 18 17.01.2015 18:49
Конечный автомат Rыся Помощь студентам 1 11.01.2013 10:56
недетерминированный конечный автомат CodeNOT Общие вопросы C/C++ 0 21.02.2012 15:48
Конечный автомат maxon56 Помощь студентам 0 19.12.2011 19:32
Конечный автомат на Delphi Arkuz Общие вопросы Delphi 4 02.10.2008 23:50