Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
equivalence_of_finite_state_machine_and_regular_expression_languages [2008/09/23 21:08] vkuncak |
equivalence_of_finite_state_machine_and_regular_expression_languages [2008/09/23 21:09] vkuncak |
||
|---|---|---|---|
| Line 35: | Line 35: | ||
| At the end, we are left with one non-empty edge from $q_i$ to $q_f$, whose label is the desired regular expression. | At the end, we are left with one non-empty edge from $q_i$ to $q_f$, whose label is the desired regular expression. | ||
| + | |||
| Line 46: | Line 47: | ||
| === Exercise === | === Exercise === | ||
| - | Consider alphabet $\Sigma = \{a,b\}$. A string $s \in \Sigma^*$ is //desperate// if it contains 'aaa' as a substring. Construct a regular expression that describes the set of all strings that are **not** desperate. ++One solution:| ((""|a|aa)b)* (""|a|aa) ++ | + | Consider alphabet $\Sigma = \{a,b\}$. A string $s \in \Sigma^*$ is //desperate// if it contains 'aaa' as a substring. Construct a regular expression that describes the set of all strings that are **not** desperate. |
| + | |||
| + | ++++One solution:| | ||
| + | (($\epsilon$|a|aa)b)* ($\epsilon$|a|aa) ++++ | ||