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 20:55] 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. | + | 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) ++++ | ||