module type NFA =
  sig
    (* You may NOT change this signature *)


    (* Abstract type for NFAs *)
    type nfa

    (* Type of an NFA transition.

       (s0, Some c, s1) represents a transition from state s0 to state s1
       on chracter c

       (s0, None, s1) represents an epsilon transition from s0 to s1
     *)
    type transition = int * char option * int
      
    (* Returns a new NFA.  make_nfa s fs ts returns an NFA with start
       state s, final states fs, and transitions ts.
     *)
    val make_nfa : int -> int list -> transition list -> nfa

    (* Takes a step in an NFA.  step m ss c returns a list of states that m
       could be in on seeing input c, starting from any state in ss.

       There should be no duplicates in the output list of states.

       If some state n is in the input list, then this function should
       behave as if any states reachable from n via epsilon
       transitions are also in the input list.

       Similarly, if some state n is in the output list, then any
       states reachable from n via epsilon transitions should also be
       in the output list.
     *)
    val step : nfa -> int list -> char -> int list

    (* Returns true if the NFA accepts the string, and false otherwise *)
    val accept : nfa -> string -> bool


    type regexp =
	Empty_String
      | Char of char
      | Union of regexp * regexp
      | Concat of regexp * regexp
      | Star of regexp

    (* Given a regular expression, return a string for regular expression in 
       postfix notation (as in project 2), with symbols and operators separated
       by a single space.  Always print the first regexp operand first, so 
       the output string will always be same for each regexp.
     *)
    val regexp_to_string : regexp -> string 

    (* Given a regular expression as string, parses it and returns the
       equivalent regular expression represented as the type regexp.    
     *)
    val string_to_regexp : string -> regexp

    (* Given a regular expression, return an nfa that accepts the same
       language as the regexp
     *)
    val regexp_to_nfa : regexp -> nfa
end


module Nfa : NFA =
  struct

    (* Fix this! *)

    type nfa = unit
    type transition = int * char option * int

    let make_nfa s fs ts = ()

    let step m l c = l

    let accept m s = false

    type regexp =
	Empty_String
      | Char of char
      | Union of regexp * regexp
      | Concat of regexp * regexp
      | Star of regexp

    let regexp_to_string r = ""

    let string_to_regexp s = Empty_String

    let regexp_to_nfa r = make_nfa 0 [] []

end