Week 10

Main topic of week 10: equivalence of the regular expression and DFSA

Additional problem of proving two regular expression are equivlent, same as to prove the equivalent of regular expreesion and laguages.

Deterministic Finite State Automata is a powerful tool to examine whether a specific string satify a given formula. Some general attribute of DFSA containing Q(states), sigma(alphabet), delta(transision function) and s, and F. Extended transition function delta* take a string to a state, rather than a single character. DFSA may reach some state that don't have link to other states. Such state is called dead end, which can be eliminated out when drawing a DFSA diagram.