A guide to the right path on accomplishing the haskell commands

Question

I am totally newbie on haskell. My java know how just isnt helping me alot.

i need any help or guide on finishing the code. I have tried most of the parts and also indicated comments on what i tend to achieve.

A DFA has been defined as follows (original image of DFA definition):

Q = {q1,q2,q3,q4,q5}
qs = q1
F = {q4}
delta = {
  <q1,0,q2>,<q1,1,q2>,<q1,.,q3>,
  <q2,0,q2>,<q2,1,q2>,<q2,.,q4>,
  <q3,0,q4>,<q3,1,q4>,<q3,.,q5>,
  <q4,0,q4>,<q4,1,q4>,<q4,.,q5>,
  <q5,0,q5>,<q5,1,q5>,<q5,.,q5>
  }
Sigma = {0,1,.}

task:

1. Create a Haskell language program that can be used to execute any arbitrary Deterministic Finite Automaton corresponding to the FDA definition above. Represent the DFA as a four-tuple

   a. represent each state with its name as a String

   b. represents all states as a list of states

   c. represent each transition as three tuple and the list of transitions as a list.

2. To assist you, implement the following functions in your solution:

   a. stateFactory – returns a DFA definition (i.e. a four tuple)

   b. allStates, firstState, finalStates, and allTransitions – take a DFA and return the corresponding component of the DFA. For example, in the above DFA instance, allStates would return the list of states, q₁, q₂, q₃, q₄, and q₅.

   c. transFrom, transInput, and transTo – take a transition and return the corresponding component of the transition

   d. findTransition – takes a state, a label, and a list of transitions and returns a list containing the single transition matching the given state and character (note the transitions emanating from a state are uniquely determined by each character label

   e. findNextState – takes a DFA, a label, and a state and returns a state

   f. dfaAccept – takes a DFA and an input String and returns True if the DFA accepts the input and False otherwise (i.e. decompose the string one character at a time, don’t match the entire string since your solution must work for any DFA). It is helpful to separate this into two functions each with different sets of parameters (one for an empty list and one for a non-empty list). One function takes a current state and one simply takes a DFA, whose state is assumed to be the initial state of the DFA.

this is my code has lots of errors but am trying to fix them

allStates = ["q1","q2","q3","q4","q5"] -- iniitialize all states
firstState = "q1"
finalStates = "q4"

--define all transitions as a tuple

t1 = ("q1",'0',"q2")
t2 = ("q1",'1',"q2")
t3 = ("q1",'.',"q3")

-- place all transitions in a list
allTransitions = [t1,t2,t3]

lst =[]

stateFactory = (allStates, firstState, finalStates, allTransitions)

findTransition state label listOfTransition = 
    if (state , label , "q1") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

    if (state , label , "q2") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

    if (state , label , "q3") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

findNextState DFA label state = 
    --get the transition and extract the last element which is the state
    last findTransition state label allTransitions

dfaAccept DFA inputString = 
    if inputString == null then False

expected Output

Prelude> dfaAccept stateFactory “”
False
Prelude> dfaAccept stateFactory “1”
False
Prelude> dfaAccept stateFactory “1.0”
True
Prelude> dfaAccept stateFactory “11.11”
True
Prelude> dfaAccept stateFactory “10.10.10”
False

Answer 1

Is this homework for a class that you're taking, or is this self-guided Haskell study? If this is self-guided, I think you might be trying an exercise that's too hard for you at this stage. I would suggest taking a look at this answer: Getting started with Haskell. Even though it's an old answer, it's been updated now and again, and most of the resources there are still useful. The http://www.haskell.org website also has links to lots of resources for learning Haskell, in the "Documentation" section.

If this is homework for a class you're taking, you might be in trouble. You're making some pretty basic mistakes in your code (using elem where you need `elem`; trying to apply last to four arguments; using an uppercase identifier DFA as a variable name) which shows that you don't have the Haskell fundamentals nailed down yet.

Perhaps you should talk to your professor and let him or her know that this assignment is beyond you. Maybe you can get an extension, or maybe you can offer to turn in a Java solution for partial credit (assuming that this course isn't specifically a Haskell course).

If you insist on forging ahead, here's a hint. You're asking for help writing one of the hardest functions, findTransition, but you haven't even written the "easy" ones, like allStates, firstState, and so on. (You've used the same names in your solution, but you've defined them as constants for a specific DFA instead of making them functions applied to a general DFA tuple, which is what the assignment requires).

So, can you complete the following template by filling in the underscores, in order to answer parts 1 and 2(b)?

-- simple type synonyms to make things easier to read
type State = String
type Symbol = Char

-- some more complicated type synonyms
type Transition = (State, Symbol, State)
type DFA = ( [State]        -- all states
           , State          -- first state
           , [State]        -- final states
           , [Transition]   -- all transitions
           )

allStates :: DFA -> [State]
allStates _ = _

firstState :: DFA -> State
firstState _ = _

finalStates :: DFA -> [State]
finalStates _ = _

allTransitions :: DFA -> [Transition]
allTransitions _ = _

Once you're able to do that, write the functions in part 2(c). Once you've done all that, you might be ready to tackle findTransition. At this point, you'll probably need to learn about the find or filter functions, or else you'll need to learn how to write recursive list functions.