?={?0,?1,?2,?3,?4}
??=?0
?={?3}
?=〈?0,0,?1〉,〈?0,1,?1〉,〈?0,.,?2〉,〈?1,0,?1〉,〈?1,1,?1〉,
〈?1,.,?3〉,〈?2,0,?3〉,〈?2,1,?3〉,〈?2,.,?4〉,〈?3,0,?3〉,〈?3,1,?3〉,
〈?3,.,?4〉〈?4,0,?4〉,〈?4,1,?4〉,〈?4,.,?4〉}
Where Σ={0,1,.}.
Я работаю над программой на Haskell, которая может обрабатывать любой произвольный детерминированный конечный автомат на основе приведенного выше определения.Я должен представлять каждое состояние с его именем в виде строки, представлять все состояния в виде списка состояний и представлять каждый переход в виде трех кортежей, а список переходов - в виде списка.
Я изменил свой коди это работает, но я могу сказать, что я не на правильном пути, насколько требования идут.Я очень новичок в Haskell и был бы очень признателен за некоторые рекомендации о том, как я могу улучшить свой код или если я полностью не в курсе этого.Я действительно пытаюсь понять, как все это работает;Я прошел через много разных примеров и учебных пособий, но я просто борюсь с моим кодом, в частности.
Редактировать : Если быть точным, при вводе примеров, приведенных ниже, я получаю правильный выводкроме dfaAccept dfaFactory "10.11".это возвращается как ложь, а не истина, и dfaAccept dfaFactory "" приводит к истине вместо ложь.Я не вижу, где моя ошибка, которая вызывает это.Также я хочу быть уверен, что мой код имеет смысл с точки зрения читабельности.
type State = Int
type DFA = ([State], [Char], State->Char->State, State, [State])
dfaFactory :: DFA
dfaFactory = (states, alphabet, delta, s, fs)
where states = [1,2,3]
alphabet= ['1','0','.']
s = 1
fs = [1]
delta 1 '1' = 2
delta 1 '0' = 2
delta 1 '.' = 2
delta 2 '1' = 3
delta 2 '0' = 3
delta 2 '.' = 3
delta 3 '1' = 1
delta 3 '0' = 1
delta 3 '.' = 1
extendDelta :: (State -> Char -> State) -> (State -> String -> State)
extendDelta delta = deltaStar
where deltaStar q [] = q
deltaStar q (a:w) = deltaStar (delta q a) w
dfaAccept :: DFA -> String -> Bool
dfaAccept (qs,alpha,delta,s,fs) w =
let deltaStar = extendDelta delta
q = deltaStar s w
in elem q fs
Пример вывода будет выглядеть следующим образом:
Prelude> dfaAccept dfaFactory “”
False
Prelude> dfaAccept dfaFactory “1”
False
Prelude> dfaAccept dfaFactory “1.0”
True
Prelude> dfaAccept dfaFactory “10.11”
True
Prelude> dfaAccept dfaFactory “10.10.10”
False
Редактировать Яработать над выполнением этих окончательных требований ... просто не знаю, как туда добраться.а.представлять каждое состояние с его именем в виде строки b.представляет все состояния в виде списка состояний c.представлять каждый переход как три кортежа, а список переходов - как список.а.dfaFactory - возвращает «жестко закодированное» определение DFA (т. е. четыре кортежа). b.getStates, getFirstState, getFinalStates и getTransitions - принимают один аргумент DFA и возвращают соответствующий компонент DFA.с.getFromState, getLabel и getToState - принимают один аргумент перехода и возвращают соответствующий компонент перехода d.matchTransition - принимает состояние, входной символ и переход и возвращает True, если данное состояние и входные данные соответствуют состоянию from и метке данного перехода e.findNextState - принимает DFA, символ ввода и текущее состояние и возвращает состояние в DFA на основе этого ввода и состояния.е.dfaAccept - принимает DFA и входную строку и возвращает True, если DFA принимает ввод, и False в противном случае.Используйте это для вызова вспомогательной функции dfaAccept1 g.dfaAccept1 - принимает входную строку, текущее состояние и DFA.Разложите входную строку по одному символу за раз, не сопоставляйте всю строку, так как ваше решение должно работать для любого DFA).Это рекурсивная функция с базовым и рекурсивным регистром.