{- Assignment 2 - Finite Automata (due November 11, noon)

Notes:
- You may import Data.List; you may not import any other modules

***Write the names and CDF accounts for each of your group members below.***
<Name>, <CDF>
<Name>, <CDF>
-}
module Dfa (State, Symbol, Transition, Automaton(..),
            allStrings, tableToDelta, extend, possibleOutcomes,
            accept, language,
            removeUseless, isFiniteLanguage, language') where

import Data.List

-- Basic data types
type State = Integer
type Symbol = Char
type Transition = (State, Symbol, State)

-- Automaton Data Type
-- Automaton states alphabet transitions initial final
data Automaton = Automaton [State] [Symbol] [Transition] State [State]
-- Some helper functions for you to access the different automaton components
states :: Automaton -> [State]
states (Automaton s _ _ _ _) = s
alphabet :: Automaton -> [Symbol]
alphabet (Automaton _ a _ _ _) = a
transitions :: Automaton -> [Transition]
transitions (Automaton _ _ ts _ _) = ts
initial :: Automaton -> State
initial (Automaton _ _ _ i _) = i
final :: Automaton -> [State]
final (Automaton _ _ _ _ f) = f


-- Questions 1-4: transitions
tableToDelta :: [Transition] -> State -> Symbol -> [State]
tableToDelta ((tr_s,tr_a,tr_next_s):xs) s a  =
	if length xs > 0 then
		if (s == tr_s) && (a == tr_a) then
			 (head [tr_next_s]):(tableToDelta xs s a)
		else
			tableToDelta xs s a
	else
		if (s == tr_s) && (a == tr_a) then
			[(head [tr_next_s])]
		else
		  []

extend :: (State -> Symbol -> [State]) -> (State -> String -> [State])
extend f  a (x_a:xs_a) =
	let f1 = f a x_a in
		if length xs_a > 0 then
	   		extend f (head f1) xs_a
		else
			f1

--allStrings :: [Symbol] -> [[String]]
allStrings  = undefined



allStrings_private_n1 a =
	if length (tail a) > 0 then
		[head a] : allStrings_private_n1 (tail a)
	else
		[[head a]]

allStrings_private_n2 a =
	if length (tail a) > 0 then
		((head a) : (head (allStrings_private_n1 a))) : allStrings_private_n2 (head $ tail $ allStrings_private_n1 a)
	else
		[head a : (head $ allStrings_private_n1 a)]


possibleOutcomes :: Automaton -> State -> [[(String, [State])]]
possibleOutcomes = undefined


-- Questions 5-6: acceptance
accept :: Automaton -> String -> Bool
accept = undefined

language :: Automaton -> [String]
language = undefined


-- Questions 7-9: finiteness
removeUseless :: Automaton -> Automaton
removeUseless = undefined

isFiniteLanguage :: Automaton -> Bool
isFiniteLanguage = undefined

language' :: Automaton -> [String]
language' = undefined


-- Question 10: epsilon transitions
epsilonClosure :: Automaton -> [State] -> [State]
epsilonClosure = undefined