Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next 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:08] vkuncak |
||
|---|---|---|---|
| Line 46: | Line 46: | ||
| === 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:| ((""|a|aa)b)* (""|a|aa) ++ |