|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
08.02.2017, 14:17 | #1 |
Новичок
Джуниор
Регистрация: 08.02.2017
Сообщений: 3
|
Конечный автомат (распознавание идентификаторов)
Здравствуйте. Не могу решить задачу уже который день:
Данные: <б> ::=A|B|C|...|Z (буква) <ц> ::=0|1|....|9 (цифра) <идентификатор> ::= <б> <идентификатор> ::= <иден-р><б>|<иден-р><ц> У нас есть начальное состояние, из него есть два пути: при вводе буквы - мы попадаем в первое состояние, а при вводе цифры или чего-то другого (например символа) мы попадаем в состояние "Конечное ошибочное". В первом состоянии у нас пути: при вводе буквы или цифры мы возвращаемся в первое состояние, а при вводе чего-то другого (else) - переходим в состояние "Конечное успешное". Грубо говоря имеем матрицу состояний и нарисованную схему этих переходов, а задание заключается в составлении алгоритма этого конечного автомата, с циклами, переменными и еще чем-то, о чем мне подсказали. Алгоритм должен подходить под любой конечный автомат, то есть как я понимаю - подгонять под описания в задании нельзя, потому что этот алгоритм должен быть универсален под любое количество строк и столбцов в матрице, к примеру, появление чисел с запятыми и любыми другими дополнениями. |
08.02.2017, 14:57 | #2 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,709
|
Вы не нашли ниодной реализации конечного автомата на своем языке программирования? Шутите? Вроде не первое апреля....
В лоб: 1. делаете набор состоянии, например enum 2. делает цикл пока не конец (например, до конца строки) 3. берете символ по текущему индексу 4. switch или куча ифов по текущему состоянию 5. в зависимости от состояния и символа меняете состояние/добавляете вывод и т.д. 6. увеличиваете индекс |
08.02.2017, 15:21 | #3 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
Есть два вида автоматов.
Детерминированный и недетерминированный. Недетерменированный на каждой развилке порождает несколько указателей на состояния. Допустим они работают параллельно тогда их можно объединить в супер состояния. Получиться детерминированный автомат. Язык программирования у вас какой? И учебник какой?
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
08.02.2017, 15:25 | #4 |
Новичок
Джуниор
Регистрация: 08.02.2017
Сообщений: 3
|
Здесь без языка программирования, использовать надо только алгоритмизацию, чтобы работало даже при увеличении состояний и входных данных...
|
08.02.2017, 15:52 | #5 | |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
Цитата:
Раз на любом так почему бы не взять язык программирования? Там есть средства для контроля они проверят что-бы ваша последовательность была чёткой. Советую уточнить у вашего преподавателя. Скорее всего вы ошибаетесь и он ждёт от вас именно программу. Иначе нет никакого смысла, по словосочетаниям "конечный автомат" нагуглить данные и написать реферат дело 5 минут, точно было на intuit.ru. Если хотите разобраться для себя то переведите вот эту статью https://swtch.com/~rsc/regexp/regexp1.html Исходники автоматов лежат тут: https://swtch.com/~rsc/regexp/ Описание на русском есть в книгах по компиляторам: Альфред Ахо,Рави Сети,Джеффри Ульман. Компиляторы. 2-е издание, Вильемс 2003
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
|
08.02.2017, 15:59 | #6 |
Новичок
Джуниор
Регистрация: 08.02.2017
Сообщений: 3
|
Вот я ему переслал такое решение, но я тут чисто подгонял под ответ. Он и сказал, что решение должно подходить под любое количество состояний и входных данных, часть ему понравилась в алгоритме, а остальное нет, потому что при изменении любого значения из матрицы - все будет неправильно работать. Он точно не ждет программу на языке программирования. Я изучаю алгоритмы на работе, для последующего описания бизнес-процессов, только и всего
|
08.02.2017, 16:07 | #7 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
В любом случае результат вашей работы должен оканчиваться документом: реферат, отчёт, программа и её описание.
Вот ещё описание ДКА: http://citforum.ru/programming/theor...ryakov/3.shtml
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
конечный автомат | 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 |