Main topic of week 11: NFSA, equivalence of DFSA AND NFSA, cartesian product
A very closed definition to DFSA, the only differece I see is in NFSA an empty transition is allowed, and transition function are now sending from state to set of states. In summary, the DFSA just a special case of NFSA where empty transition and multiple state transition is not allowed.
DFSA and NFSA are equivalent and Every regular expression can be expressed by using DFSA or NFSA. To change a NFSA back to DFSA, we need some additional symbols.hatQ(all subset of the Q) HagSigma(same as Sigma), HatDelta(transition function that transfer all the state that current state can reach by a single transition. HatS(set of starting states) and HatF(non empty Final states).
cartesian product is used when we need to design a machine that has more than one independent requirement. For example, a string with odd length and odd number of 1s, then we could use two DFSA to keep track of the length of the string , and the number of 1s in the string. Or we could use cartesian product, to produce a machine with 4 states(keep track the lenght and 1s at the same time).
At last we learnt how to convert a FSA back to regular expressions. By eliminating one state at a time.
2008年11月18日星期二
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.
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.
2008年11月11日星期二
Week 9
Main topic of week 9: language and regex
A brand new material starts here and of course, a lot of definitions need to remember in this week. These inclued Strings, alphabet, length, and languages. Language is a set of strings over some alphabet. It has some operations such as intersection , union, kleene star and complement.
Regular expresion are used to denote a set of language in a special structure. It is also defined in a recursive way. Which has base cases single character, empty string and empty set, and if R and S are defined regular expressions, so do R+S, RS and R*. Language which can be denoted by regular expression are defined in the same sort. Base cases are include language that can be denoted by regular expression of empty string, single charcter and empty language, and if language one and two are defined by some regular expression, the language of union and concatenation and kleene star will also be defined in the regular expression.
More example of the regular expressions are provided here, with a little alrithmetic operation we could find some regular expression are the same easily.
To prove a language denoted by regular expression is equivalent to other language, is by proving mutually inclusive, that is, the expression is a subset of the other language A, and A also can be denoted by this regular expression.
A brand new material starts here and of course, a lot of definitions need to remember in this week. These inclued Strings, alphabet, length, and languages. Language is a set of strings over some alphabet. It has some operations such as intersection , union, kleene star and complement.
Regular expresion are used to denote a set of language in a special structure. It is also defined in a recursive way. Which has base cases single character, empty string and empty set, and if R and S are defined regular expressions, so do R+S, RS and R*. Language which can be denoted by regular expression are defined in the same sort. Base cases are include language that can be denoted by regular expression of empty string, single charcter and empty language, and if language one and two are defined by some regular expression, the language of union and concatenation and kleene star will also be defined in the regular expression.
More example of the regular expressions are provided here, with a little alrithmetic operation we could find some regular expression are the same easily.
To prove a language denoted by regular expression is equivalent to other language, is by proving mutually inclusive, that is, the expression is a subset of the other language A, and A also can be denoted by this regular expression.
2008年11月4日星期二
Week 8
Main topic of week 8: named repetition and prove of iteration
As disscussed previously, recursion is an extension of naming repetion process. A recursive function is formed by providing base case, and generating body. Iteration works in the simailary way, but with little variation. Unlike recursive function, iteration will have an end point somewhere, or it provided infinite loop and yield false result. Thus when proving the correctness of a iteration function, we need first to find the loop invariant that goes toward the final result, and a termination that garentee the function will end. Termination sometimes is not very easy to find, and definitely require some thinking on it.
As disscussed previously, recursion is an extension of naming repetion process. A recursive function is formed by providing base case, and generating body. Iteration works in the simailary way, but with little variation. Unlike recursive function, iteration will have an end point somewhere, or it provided infinite loop and yield false result. Thus when proving the correctness of a iteration function, we need first to find the loop invariant that goes toward the final result, and a termination that garentee the function will end. Termination sometimes is not very easy to find, and definitely require some thinking on it.
订阅：
评论 (Atom)