1. DEFINE
    1. Phrase-Structure Grammar- A phrase-structure grammar(V, T, S, P) consists of a vocabulary V, a subset T of V consisting of terminal elements, a start symbol S from V, and a set of productions P.
    2. Vocabulary- a finite non-empty set of symbols in a grammar
    3. Word- a string of finite length of elements of V
    4. Production Rules- rules showing how nonterminal symbols can be replaced by nonterminal and/or terminal symbols.
    5. Finite-State Machine- a finite-state machine (M = (S, I, O, f, g, ) consists of a finite set of states, a finite input alphabet I, a finite output alphabet O, a transition function f that assigns to each state and input pair a new state, an output function g that assigns to each state and input pair an output and an initial state
  2. SHORT ANSWERS
    1. Describe the difference(s) between terminal symbols and non-terminal symbols in a grammar.

      2. Non-terminal symbols can be replaced by other symbols in the vocabulary, terminal symbols cannot be replaced.

    2. List the parts of a phrase-structured grammar.
      1. V- Vocabulary
      2. S- States
      3. T- Terminal Symbols
      4. P- Production rules
    3. List the parts of a finite-state machine.
      1. S- states
      2. I- Input alphabet
      3. O- Output alphabet
      4. f- a function that assigns to each pair of states and input a state
      5. g- a function that assigns to each pair of states and input an output
      6. - an initial state
    4. List the parts of a finite automaton.
      1. S- States
      2. I- input alphabet
      3. f- transition function
      4. - an initial state
      5. F- a set of final states
    5. Describe the differences between a deterministic finite automaton and a non-deterministic automaton.

      6. The function in a deterministic finite automaton assigns only 1 state to each pair of unique state and input symbol.

  3. PROBLEMS
    1. Represent the following relation using a i) graph and, ii) matrix.

      2. {(1,1), (1,2), (1,3), (2,2), (3,3)}

      1. Graph representation

      2. Matrix

    2. Use the Matrix representation from Problems #1 to determine the properties of the relation above.

      3. Reflexive property

    3. Show how the matrix from #1 ii would have to change to show the following properties:
      1. Irreflexive

        2.  

        1

        2

        3

        1

        0

        1

        1

        2

        0

        0

        0

        3

        0

        0

        0

      2. Symmetric

        3.  

        1

        2

        3

        1

        1

        1

        1

        2

        1

        1

        0

        3

        1

        0

        1

    4. Determine if the following Relations are Equivalence Relations
      1. {(0,0), (1,1), (1,2), (2,1), (2,2), (3,3)} - Yes
      2. {(0,1), (1,1), (2,2), (3,3)} - No
    5. Show the partitions of the equivalence relation from Problems #4.

      6. [0] = 0

      [1] = 1, 2

      [2] = 1, 2

      [3] = 3

    6. Determine if the following relation on the set {a, b} is a partial order.

      7. {(a,a), (a,b), (b,b)}

      Yes, because it is reflexive, antisymmetric, and transitive