The .hs file that caused the trouble.

bug.hs (text/plain), 5.51 KB, created by Koen on 2010-12-09 22:04:36 UTC

{--
-- This file represents a DFA, a Deterministic Finite Automaton.
-- It was written by Koen Wellens, student at the 
-- Katholic University Leuven in Belgium (www.cs.kuleuven.be).
-- For more information about DFA's, please refer to
-- en.wikipedia.org/wiki/Deterministic_finite-state_machine
--
-- This file has been made for a task in the bachelor computer science
-- program, where the task was to:
-- 1) Describe a DFA in Haskell, the most general way.
-- 2) Implement the example given with the assignment    
--       (this is the 'machine'-function)
-- 3) Write a check-function that checks whether a string is accepted
--    by a DFA. This function should return a Bool.
-- 4) Enable interactive strings. Write a main function that asks for
--    input from a user and shows the result.
--
-- I use Linux Ubuntu version 2.6.32.26 on a 64-bit laptop.
-- I installed the "GHC - the Glassgow Haskell Compilation System" (ghc6)
-- and I use GHCi in the ubuntu terminal.
--}



-- My description of a DFA. A DFA uses two types: 
-- One type for the states and one type for its alphabet.
-- I represent my DFA as a state where it begins, 
-- a function that calculates the next state, given a symbol
-- from the alphabet, and a condition to calculate whether
-- a state is an acceptance state.
data DFA state alphabet = 
	DFA state [alphabet] (state -> alphabet -> state) (state -> Bool)

-- This is the example machine given with the assignment,
-- in my representation of a DFA.
-- This DFA accepts all strings that end on "aab".
machine :: DFA Int Char
machine = DFA 0 "ab" delta (== 3)
	where
		delta 0 'a' = 1
		delta 0 'b' = 0
		delta 1 'a' = 2
		delta 1 'b' = 0
		delta 2 'a' = 2
		delta 2 'b' = 3
		delta 3 'a' = 1
		delta 3 'b' = 0  

-- The check function must make sure the alphabet type derives Equivalence.
-- This function gets a DFA and a string of symbols in the alphabet,
-- and returns a Bool.
-- This method uses the condition of the DFA to check whether the state
-- returned by the useString method is an acceptance state.
-- If that is the case, then the string is accepted by the DFA.
-- If not, then the string is not accepted by the DFA.
check :: (Eq alphabet) => DFA state alphabet -> [alphabet] -> Bool
check (DFA state alphabet delta isFinal) string = 
	isFinal (useString delta state alphabet string)

-- The useString function must make sure the alphabet type derives Equivalence.
-- This function gets the function of a DFA, a state, the entire alphabet of
-- a DFA and a string as input. This function returns in which state the DFA
-- is when the string is used to build a path between the states.
-- When the string is empty, it should return the state it is in at that moment.
-- When the string is not empty, the assignment read we had to make sure
-- that an error message was written when a symbol was given that is not in the
-- alphabet. Therefor, I wrote a contains method to check this.
useString :: (Eq alphabet) => (state -> alphabet -> state) -> state -> [alphabet] -> [alphabet] -> state
useString _ state _ [] = state
useString delta state alphabet (char : chars) = 
	case (contains alphabet char) of
	True -> useString delta (delta state char) alphabet chars
	False -> error ("*** Exception: Inputsymbol not in alphabet!")

-- The contains function must make sure the alphabet type derives Equivalence.
-- This function gets a list of symbols and a symbol, and returns whether
-- the one symbol is contained by the list of symbols.
-- If the list is empty, then the symbol cannot be in the list, so False is returned.
-- If the list is not empty, equivalence has to be checked to return True or
-- to keep searching in the list.
contains :: (Eq alphabet) => [alphabet] -> alphabet -> Bool
contains [] _ = False
contains (alph : alphs) char = 
	if (alph == char) then True
	else contains alphs char

-- The main function, part 4 of the assignment.
-- In this main function, a message is printed to ask for the input string.
-- After that, the check function checks whether the string is accepted or not.
-- Appropriate output will be printed. To finish the method, it is looped
-- so that a user can keep giving strings until he is sick of doing so.
main :: IO()
main = 
	do
		print ("Please enter a string (containing only \’a\’ and \’b\’): ")
		string <- getLine
		case (check machine string) of
			True -> putStrLn "The input is accepted by the DFA!"
			False -> putStrLn "The input is NOT accepted by the DFA!"
		main
		
{--
-- When I did this, I had a important error made by GHCi.
-- I copied the text "Please enter a string (containing only 'a' and 'b'):" from
-- the assignment, and adding the '\' for the '-characters resulted in
-- panic.png, which is also in the .zip as this file is.
--}

-- What did work, was this:
huh :: [Char]
huh = ['\'']

-- Strangely enough, this gave no errors.
main2 :: IO()
main2 = 
	do
		print ("Please enter a string (containing only "++huh++['a']++huh++" and "++huh++['b']++huh++"): ")
		string <- getLine
		case (check machine string) of
			True -> putStrLn "The input is accepted by the DFA!"
			False -> putStrLn "The input is NOT accepted by the DFA!"
		main2
		

-- When making this file, I found out that rewriting the print state also solves the problem.
-- This means that instead of copying the line from a .pdf file into this .hs file,
-- I typed it myself.
main3 :: IO()
main3 = 
	do
		print ("Please enter a string (containing only \'a\' and \'b\'): ")
		string <- getLine
		case (check machine string) of
			True -> putStrLn "The input is accepted by the DFA!"
			False -> putStrLn "The input is NOT accepted by the DFA!"
		main3