LARA

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Last revision Both sides next 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:08]
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:| 
 +((""​|a|aa)b)* (""​|a|aa) ​++++