Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | |||
|
sav08:homework01 [2008/05/29 11:47] barbara typo |
sav08:homework01 [2009/03/11 17:22] vkuncak |
||
|---|---|---|---|
| Line 103: | Line 103: | ||
| * generate a random assignment to propositional variables of the formula | * generate a random assignment to propositional variables of the formula | ||
| * compare the truth value of the original and of the transformed formula | * compare the truth value of the original and of the transformed formula | ||
| + | |||
| ===== Optional Problem 5 ===== | ===== Optional Problem 5 ===== | ||
| Line 108: | Line 109: | ||
| Consider [[:regular expression]]s with variables denoting subsets of $\Sigma^*$ where $\Sigma=\{0,1\}$. Define function $W$ that takes such a regular expression and replaces | Consider [[:regular expression]]s with variables denoting subsets of $\Sigma^*$ where $\Sigma=\{0,1\}$. Define function $W$ that takes such a regular expression and replaces | ||
| * each constant 0 with some relation $r_0$ and each constant 1 with some relation $r_1$ | * each constant 0 with some relation $r_0$ and each constant 1 with some relation $r_1$ | ||
| - | * for each variable $L$ denoting a subset of $\Sigma^*$, replaces all of its occurrences with some relation $r_L$ | + | * for each variable $L$ denoting a subset of $\Sigma^*$, replaces all of its occurrences with a relation variable $r_L$, denoting relations on $S$ |
| * replaces regular set union with relation union $\cup$ | * replaces regular set union with relation union $\cup$ | ||
| * replaces concatenation with relation composition $\circ$ | * replaces concatenation with relation composition $\circ$ | ||