I am tasked with defining a (minimal) DFA in haskell. It is in the form ([states], "language", transition function, start state, [accept states]), and is supposed to take in an integer, and create a DFA for it for binary numbers that are divisible by that number. For example, function 4 will create a DFA for binary numbers that are divisible by 4.
I started off with creating DFAs for 1 to 6 to kind of see the pattern that it is taking, and I have figured out that if it is in a state and receives a 0, the binary number is doubled, so it means the state is doubled, and if it receives a 1, the state is doubled and added with a 1.
Here is an example of one I made for all numbers divisible by 4.
create 4
= ([0,1,2,3], "01", ts, 0, [0])
where
ts = [ ((0, '0'), 0)
, ((0, '1'), 1)
, ((1, '0'), 2)
, ((1, '1'), 3)
, ((2, '0'), 0)
, ((2, '1'), 1)
, ((3, '0'), 2)
, ((3, '1'), 3)
]
Here is the start of my generalised DFA creator which accepts an integer n.
create n
= ([0..(n-1)], "01", ts, 0, [0])
where
ts = [ ((x, '0'), x `mod` n)
, ((x, '1'), (x*2 + 1) `mod` n)
]
#where x is an iterated number through the states array
I am not sure if this is the best or correct way to do it..
I essentially want it to iterate through the states array, and for each state, create 2 transition functions one for if it receives '0', and one for if it receives '1', and apply the logic above.
I am new to haskell, so am not really sure how to approach this. Any advice would be greatly appreciated!
Hint: list comprehensions are a sort of loop. So, you can write
ts =
[ {- this part is your job -}
| x <- [0..n-1]
, char <- ['0', '1']
]
and this will be a sort of nested loop that iterates through all numbers in the 0 to n-1 range, and through all of the binary digits. In the {- this part is your job -} spot, you can use the names x and char for the current values of the two loops, respectively.