моделировать детерминированный стек-автомат (DAS) в С++

Я читал упражнение UVA, которое мне нужно для имитации детерминированного автомата стека, чтобы увидеть, принимаются или нет DSA определенные строки для данной записи в следующем формате:

В первой строке ввода будет целое число C, указывающее количество тестовых случаев. Первая строка каждого набора входных данных содержит пять целых чисел E, T, F, S и C, где E — количество состояний в автомате, T — количество переходов, F — количество конечных состояний, S — начальное состояние и C количество тестовых строк соответственно. В следующей строке будет записано F целых чисел, представляющих конечные состояния автомата. Затем следуют T строк, каждая с 2 целыми числами I и J и 3 строками, L, T и A, где I и J (0 ≤ I, J ‹ E) представляют состояние происхождения и назначения переходного состояния соответственно. L представляет собой символ, считанный с ленты в переход, T представляет символ, находящийся на вершине стека, а A — действие, выполняемое с вершиной стека в конце этого перехода (символ, используемый для представления нижней части стека). куча всегда Z. для представления конца строки или распаковки используется действие без учета вершины стека для символа перехода £). Алфавит стека будет заглавными буквами. Для цепочки А символы укладываются справа налево (так же, как и в программе JFlap, т. е. новой вершиной стека будет тот символ, который находится слева). Затем идут C строк, каждая с входной строкой. Входные строки могут содержать строчные буквы и цифры (не обязательно присутствующие в каком-либо переходе).

Вывод в первой строке каждого теста должен отображать следующую строку «Case G:», где G представляет номер теста (начиная с 1). Затем C строк, на которых нужно напечатать слово «ОК», если автомат принимает строку, или «Отклонить» в противном случае.

Например:

Input:
2
3 5 1 0 5
2
0 0 1 Z XZ
0 0 1 X XX
0 1 0 X X
1 1 1 X £
1 2 £ Z Z
111101111
110111
011111
1010101
11011
4 6 1 0 5
3
1 2 b A £
0 0 a Z AZ
0 1 a A AAA
1 0 a A AA
2 3 £ Z Z
2 2 b A £
aabbb
aaaabbbbbb
c1bbb
abbb
aaaaaabbbbbbbbb

это вывод:

Output:
Case 1:
Accepted
Rejected
Rejected
Rejected
Accepted

Case 2:
Accepted
Accepted
Rejected
Rejected
Accepted

Мне нужна помощь или любая идея, как я могу смоделировать этот DSA, я не прошу меня код, который решает проблему, потому что я хочу сделать свой собственный код (Идея состоит в том, чтобы научиться правильно??), Но мне нужна помощь. (какая-то идея или псевдокод), чтобы начать реализацию.


c++ finite-automata dsa
person franvergara66    schedule 13.07.2011    source источник
comment
автоматы во множественном числе. автомат в единственном числе.   -  person Lightness Races in Orbit    schedule 13.07.2011

Ответы (1)


arrow_upward
2
arrow_downward

Сначала вам нужна структура данных для сохранения переходов. Вы можете использовать вектор со структурой перехода, которая содержит пятерки перехода. Но вы можете использовать тот факт, что состояния являются целыми числами, и создать вектор, который сохраняет индекс 0, переходы из состояния 0; по индексу 1 переходит из состояния 1 вот так. Таким образом, вы можете сократить время поиска правильного перехода.

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

int findIndex(vector<quintuple> v)//which finds the index of correct transition otherwise returns -1

затем используйте возвращаемое значение, чтобы получить новое состояние и символ стека новостей.

Или вы можете использовать цикл for для вектора и логического флага, который представляет переход найден или нет.

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

Для ввода вы можете использовать что-то вроде вектора или вектора в зависимости от личного вкуса. Вы можете реализовать свой основной метод с помощью циклов for, но если вам нужны дополнительные трудности, вы можете реализовать рекурсивную функцию. Пусть будет легко.

person Gökhan Uras    schedule 13.07.2011
comment
Я использую вектор со структурой перехода, которая содержит пятерки перехода, я немного запутался в том, что нужно создать функцию поиска. - person franvergara66; 18.07.2011