DFA + счетчик с умножением, сложением, скобками

Question

Я смотрю на экзаменационный вопрос, на котором написано

'Объясните, как правильно сформированное арифметическое выражение для переменных a, b, c, которое содержит сложения, умножение и скобки, может распознаваться DFA со счетчиком. (Такой DFA может увеличивать и уменьшать счетчик при каждом переходе, а также проверять его на ноль). '

Я не совсем уверен, что понимаю, о чем он спрашивает. Если кто-то может дать подсказку, которая будет принята с благодарностью. (то есть, к примеру, каким будет умножение a и b)

Answer 1

Если все, что вам нужно, это просто подсказка , то я думаю, этого должно быть достаточно:

1. Некоторые строки представляют допустимые арифметические выражения, такие как

a + b
(a + b)*(c + d)

и некоторые недействительны, такие как

a + - b
a b
)
()
(a + b)*)c+d(

" может быть распознан DFA со счетчиком " здесь означает, что вы можете построить детерминированный конечный автомат такой, что он останавливается на одном из "принимающих состояний" после обработкижало в том и только в том случае, если эта строка представляет действительное арифметическое выражение

PS Дополнительная подсказка: здесь важна счетная часть, потому что простой DFA даже не может распознать, правильно ли сопоставлена ​​произвольная строка скобок.