Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
closure_properties_of_finite_state_machines [2007/05/24 00:42] vkuncak |
closure_properties_of_finite_state_machines [2008/09/17 09:19] vkuncak |
||
---|---|---|---|
Line 24: | Line 24: | ||
The new accepting states are those of the second machine. | The new accepting states are those of the second machine. | ||
- | ==== Iteration ==== | + | |
+ | ==== Iteration (Kleene star) ==== | ||
Create a new initial state which is accepting and has an epsilon transition to the old start state.\\ | 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. | Put a loop around the existing machine by adding epsilon transitions from the accepting states to the new start state. | ||
+ | |||
==== Comments ===== | ==== Comments ===== | ||
- | Deterministic versus non-deterministic machines in input and output. | + | If we start with deterministic machines, for which of the above constructions will we get a deterministic machine as a result? |
- | Cost of complementation. Cost of determinization. | + | What is the cost of computing the machine for the complement of the language? |