Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
closure_properties_of_finite_state_machines [2007/05/11 17:11] ghid.maatouk |
closure_properties_of_finite_state_machines [2008/09/17 09:18] vkuncak |
||
---|---|---|---|
Line 13: | Line 13: | ||
Let $A = (\Sigma, Q_A, q_0^A, \Delta_A, F_A)$ and $B = (\Sigma, Q_B, q_0^B, \Delta_B, F_B)$.\\ | Let $A = (\Sigma, Q_A, q_0^A, \Delta_A, F_A)$ and $B = (\Sigma, Q_B, q_0^B, \Delta_B, F_B)$.\\ | ||
Then the union of the two automata will be $C=(\Sigma, Q_A \cup Q_B, q_0, \Delta_A \cup \Delta_B \cup \{(q_0,\epsilon, q_0^A), (q_0,\epsilon, q_0^B)\}, F_A \cup F_B)$. | Then the union of the two automata will be $C=(\Sigma, Q_A \cup Q_B, q_0, \Delta_A \cup \Delta_B \cup \{(q_0,\epsilon, q_0^A), (q_0,\epsilon, q_0^B)\}, F_A \cup F_B)$. | ||
+ | |||
==== Intersection ==== | ==== Intersection ==== | ||
- | Product of state spaces for deterministic machines.\\ | + | Product of state spaces, even for non-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 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.\\ |