Конечный автомат (распознавание идентификаторов)

[thearthurio]

Здравствуйте. Не могу решить задачу уже который день:

Данные:
<б> ::=A|B|C|...|Z (буква)
<ц> ::=0|1|....|9 (цифра)
<идентификатор> ::= <б>
<идентификатор> ::= <иден-р><б>|<иден-р><ц>

У нас есть начальное состояние, из него есть два пути: при вводе буквы - мы попадаем в первое состояние, а при вводе цифры или чего-то другого (например символа) мы попадаем в состояние "Конечное ошибочное". В первом состоянии у нас пути: при вводе буквы или цифры мы возвращаемся в первое состояние, а при вводе чего-то другого (else) - переходим в состояние "Конечное успешное".

Грубо говоря имеем матрицу состояний и нарисованную схему этих переходов, а задание заключается в составлении алгоритма этого конечного автомата, с циклами, переменными и еще чем-то, о чем мне подсказали. Алгоритм должен подходить под любой конечный автомат, то есть как я понимаю - подгонять под описания в задании нельзя, потому что этот алгоритм должен быть универсален под любое количество строк и столбцов в матрице, к примеру, появление чисел с запятыми и любыми другими дополнениями.

[p51x]

Вы не нашли ниодной реализации конечного автомата на своем языке программирования? Шутите? Вроде не первое апреля....
В лоб:
1. делаете набор состоянии, например enum
2. делает цикл пока не конец (например, до конца строки)
3. берете символ по текущему индексу
4. switch или куча ифов по текущему состоянию
5. в зависимости от состояния и символа меняете состояние/добавляете вывод и т.д.
6. увеличиваете индекс

[Pavia]

Есть два вида автоматов.
Детерминированный и недетерминированный.
Недетерменированный на каждой развилке порождает несколько указателей на состояния.

Допустим они работают параллельно тогда их можно объединить в супер состояния. Получиться детерминированный автомат.

Язык программирования у вас какой? И учебник какой?

[thearthurio]

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

[Pavia]

Сообщение от thearthurio

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

Алгоритм есть чёткая последовательность действий записанная на каком либо языке.
Раз на любом так почему бы не взять язык программирования? Там есть средства для контроля они проверят что-бы ваша последовательность была чёткой.

Советую уточнить у вашего преподавателя. Скорее всего вы ошибаетесь и он ждёт от вас именно программу. Иначе нет никакого смысла, по словосочетаниям "конечный автомат" нагуглить данные и написать реферат дело 5 минут, точно было на intuit.ru.

Если хотите разобраться для себя то переведите вот эту статью
https://swtch.com/~rsc/regexp/regexp1.html
Исходники автоматов лежат тут:
https://swtch.com/~rsc/regexp/

Описание на русском есть в книгах по компиляторам:
Альфред Ахо,Рави Сети,Джеффри Ульман. Компиляторы. 2-е издание, Вильемс 2003

[thearthurio]

Вот я ему переслал такое решение, но я тут чисто подгонял под ответ. Он и сказал, что решение должно подходить под любое количество состояний и входных данных, часть ему понравилась в алгоритме, а остальное нет, потому что при изменении любого значения из матрицы - все будет неправильно работать. Он точно не ждет программу на языке программирования. Я изучаю алгоритмы на работе, для последующего описания бизнес-процессов, только и всего

[Pavia]

В любом случае результат вашей работы должен оканчиваться документом: реферат, отчёт, программа и её описание.

Вот ещё описание ДКА:
http://citforum.ru/programming/theor...ryakov/3.shtml