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

Question

[thearthurio]

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

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

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

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

Answer 1

[Rsa97]

0. Установить начальное состояние, установить указатель на первый символ.
1. Получить следующий символ.
2. По таблице переходов найти переход для пары (состояние, символ).
3. Если такой переход есть, то установить новое состояние, сдвинуть указатель на следующий символ, перейти на пункт 1.
4. По таблице допустимости проверить допустимость завершения в текущем состоянии.
5. Если завершение недопустимо, то выдать ошибку, завершить работу.
6. Выдать корректное завершение, завершить работу.

Answer 2

[Денис Загаевский]

У вас в грамматике левая рекурсия. <идентификатор> ::= <иден-р><б>|<иден-р><ц>
Такое нельзя ДКА реализовать. надо избавиться от неё. Гуглить "устранение левой рекурсии".

Answer 3

[tsarevfs]

Конечные автоматы эквивалентны регулярным выражениям. Но ваше задание написано в терминах Формы Бэкуса — Наура, которая задает контекстно свободную грамматику. В общем случае грамматики нельзя решить с помощью ДКА. Но в вашем случае очень легко написать регулярку: [A-Z]([1-9]|[A-Z])*. Теорема Клини дает способ построения автомата разрешающего любое регулярное выражение.

Answer 4

[abcd0x00]

Надо тебе получить эквивалентную грамматику сначала (порождающую тот же самый язык), пригодную для построения конечного автомата. Обычно для этого вводят дополнительный нетерминал.

Вот к этому мужику зайдёшь, посмотришь
проблема
https://www.youtube.com/watch?v=XbihuriQ8p8&t=1h5m30s
решение
https://www.youtube.com/watch?v=wH4l8WvGPFE&t=1m20s