LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
closure_properties_of_finite_state_machines [2008/09/17 09:18]
vkuncak
closure_properties_of_finite_state_machines [2008/09/17 09:19] (current)
vkuncak
Line 29: Line 29:
 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?