Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
closure_properties_of_finite_state_machines [2007/05/11 17:09] ghid.maatouk |
closure_properties_of_finite_state_machines [2007/05/11 17:11] ghid.maatouk |
||
---|---|---|---|
Line 16: | Line 16: | ||
==== Intersection ==== | ==== Intersection ==== | ||
- | Product of state spaces for deterministic machines. For nondeterministic machines, must use DeMorgan's laws with complementation and union. Note that every time we want to complement an machine, we must determinize it first. | + | Product of state spaces for deterministic machines.\\ |
+ | For nondeterministic machines, must use DeMorgan's laws with complementation and union. Note that every time we want to complement an machine, we must determinize it first. | ||
==== Concatenation ==== | ==== Concatenation ==== | ||
Line 25: | Line 26: | ||
==== Iteration ==== | ==== Iteration ==== | ||
- | Create a new initial state and put a loop around the existing machine. | + | Create a new initial state which is accepting and has an epsilon transition to the old start state.\\ |
+ | Put a loop around the existing machine by adding epsilon transitions from the accepting states to the new start state. | ||
==== Comments ===== | ==== Comments ===== |