CMSC 31000 Data

Things I'd like well defined:

Translation of regular expressions into NFA's

The product operator (".")
a.b ->
```
NFA(a) -E-> NFA(b)
```

The union operator ("+")

a+b ->

      /->NFA(a)-\
     E           E
    /             v
-E->o             o-E->
    \             ^
     E           E
      \->NFA(b)-/

The astarate operator ("*")

a* ->

     ____________
    v            \
-E->o-E->DFA(a)-E/
    \
     E
      \->o

Anything else?

Kleene Algebra

What are the productions of the Kleene algebra?
- (a + b) + c = a + (b + c)
  associativity of +
- a + b = b + a
  commutativity of +
- a + a = a
  idempotence of +
- a + 0 = a
  identity for +
- a.(b.c) = (a.b).c
  associativity of .
- a.E = E.a = a
  identity for .
- a.0 = 0.a = 0
  annihilator for .
- a.(b + c) = a.b + a.c
  distributivity of . and +
- (a + b).c = a.c + b.c
  distributivity of . and +
- E + a.a* = E + a*.a = a*
  definition of astarate?
- b + a.c <= c -> a*.b <= c
  inductive rule?
- b + c.a <= c -> b.a* <= c
  inductive rule?
- a <= b -def-> a + b <= b
- a*.a* = a*
- a** = a*
- (a*.b)*.a* = (a + b)*
- (a.b)*.a = a.(b.a)*
- a* = (a.a)* + a.(a.a)*

Define the homomorphism operator.

A homomorphism is a function h : E* -> F*, for some alphabet E onto some alphabet F, such that for all x,y in E*:
1. h(xy) = h(x).h(y)
2. h($) = $ (Where $ is the empty string.)
The image of a language, A, which is a subset of E*, is defined as:
- h(A) = {h(x) | x is in A} (which is a subset of F*.)
Where the preimage of a language B, a subset of F*, is defined as:
- h^-1(B) = {x | h(x) is in B} (which is a subset of E*.)
This is useful in some cases because of theorem 10.1 (p.62) and 10.2 (p.63):
1. Let h : E* -> F* be a homomorphism. If B, a subset of F*, is regular, then so is the preimage h^-1(B) under h.
2. Let h : E* -> F* be a homomorphism. If A, a subset of E*, is regular, then so is its image h(A) under h.

Define a Myhill-Nerode relation.

Let R, a subset of E, be a regular set. The Myhill-Nerode relation for that set, =_R, is an equivalence relation on E*, such that:
- =_R is a right congruence : for any x, y, elements of E*, and a, a character in E:
- =_R refines R : for any x, y, elements of E*:
- =_R is of finite index, meaning that the number of equivalence classes in =_R is finite.
These identities follow because of an earlier definition of =_R, where M ( =(Q, E, d, s, F)) is a machine that recognizes R, and =_R was defined to mean:
Things such as finite index fall out from there being one state in the automaton for each equivalence class.

What is the quotient construction?

This is an algebraic formalism, useful in computing for finding the minimal DFA that is isomorphic to an arbitrary DFA.

It starts with defining an equivalence relation for states in Q, such that
This operator has the following properties:
- ~ is reflexive: for all p, p ~ p
- ~ is symmetric: for all p, q, if (p ~ q) then (q ~ p)
- ~ is transitive: for p, q, r, if (p ~ q) and (q ~ r) then (p ~ r)
The ~ operator defines an equivalence class for a state p in Q, [p], such that [p] = { q | q ~ p }.

This relationship lets us build the quotient automaton, M_/~, = ( Q', E, d', s', F' ), where:
- Q' = { [p] | p in Q }
- d'( [p], a ) = { f( p, a ) }
- s' = [s]
- F' = { [p] | p is in F }

Define isomorphism for DFA's.

Given two DFA's:
- M = (Q_M, E, d_M, s_M, F_M)
- N = (Q_N, E, d_N, s_N, F_N)
These DFA's are said to be isomorphic if there exists a one-to-one and onto mapping, f : Q_M -> Q_N, such that
- f( s_M ) = s_N
- f( d_M(p, a) ) = d_N( f(p), a ), for all p in Q _M, a in E
- p is in F_M iff f(p) is in F_N.

Midterm results
1. Construct an NFA with e-moves that accepts the language (ab + ba)*.
  See actual midterm - full points (used layouts above.)
2. Construct a DFA that accepts the language L = { x : #a(x) = #b(x) mod 3 }
  See actual midterm - full points. Note that I used the product construction, but there was an easier DFA where you count (#a(x) - #b(x) ) mod 3 and accept on 0.
3. Consider the language P = { x^ay^bz^c : ac > b² }. Prove that P is not regular.
  The demon beat me - see following section on pumping lemma for regular languages.
4. Suppose R is a regular language, and L is any language. Define
  R/L = { x in E* : There exists y in L, xy in R }
  Show that R/L is regular.
  Not done. Problem is a miscellaneous problem in the Kozen text.
5. Minimize the automaton in Figure 1 on page 2.
  See actual midterm - full points. See also state minimization summary below.
6. Give an example of two DFA's M₀, and M₁ that differ only in their start state, but where M₀ is minimal, and M₁ is not.
  Use your example to inspire an additional hypothesis that would guarantee that if M₀ is minimal, then M₁ is also minimal.
  
  An example of this is having a portion of the automata not be reachable from another part of the automaton (such as accepting a prefix.) M₀ would start in the prefix recognition states, while M₁ would not, and therefore have unreachable states, hence not minimal.
  As for the hypothesis, perhaps something like the following might be acceptable: if M₀ and M₁ differ only in their start state, and M₀ is minimal, then M₁ is minimal only if the set of states reachable from s₁ is the same as s₀.