Chapter Seven Review

#############
Formal Language:
#############
Any set of strings can be empty, finite, or infinite.
Length of string: s, number of symbols in s, ex: "+"=1, "e"=0.

#############
Regular Expressions(Regex):
#############
Basis : empty, empty string, one-symbol character;
Kleene star can be used to restrict the pattern of a regex:
even or odd numbers of some characters;
Idempotence of Kleene star: R** = R*
Distributivity: (A(B+C)) = (AB+AC), ((B+C)A) = (BA + BC)

Proving equality of two languages => Prove mutual inclusion:
1. Analyze the pattern of a language and divide into pieces if possible;
2. Transformations: in general case, expand some terms to make up the equality;
3. Check from both directions, conclusion.

###
FSA
###
Proof procedure, induction:
Basis: x=e, &*(q_e,x)=q_e. P(e) true.
Induction Step: Assume x = x'a, assume P(x'). Analyze the cases.
In all cases, x = x'a and &*(s,x) = &*(q_e,x'a)=&(&*(q_e,x'),a)
according to our induction hypothesis.
Then using the transistions functions, we prove P(x') => P(x), in all cases.

####
NFSA
####
Difference: Each transition takes the machine to a subset of states rather than a unique
state.

Notes:
Every regex has equivalent NFSA.
Every NFSA has equivalent DFSA.