Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:playground [2008/03/19 16:00] vkuncak |
sav08:playground [2010/09/29 21:54] hossein |
||
---|---|---|---|
Line 1: | Line 1: | ||
====== Playground ====== | ====== Playground ====== | ||
- | Therefore $ subst(sigma)( x ) = x,\ sigma {\rm not defined at } x $ | ||
+ | ===== Problem 1: Linear Extension ===== | ||
+ | |||
+ | Let $r\subseteq A\times A$ be an arbitrary relation and $\leq$ a partial order on $A$. | ||
+ | |||
+ | a) Assume $a,b\in A$ to be incomparable: $a\not\leq b$ and $b\not\leq a$. Show that the transitive closure of the relation $r_{\text{ex}}$ is a partial order on $A$. | ||
+ | |||
+ | $r_{\text{ex}} = \{(x,y) | x\leq y\}\cup\{(a,b)\}$ | ||
+ | |||
+ | b) Use (a) to show if $A$ is finite then every order $\leq$ on $A$ has a linear extension. | ||
+ | A total order $\leq_{1}$ is a linear extension of a partial order $\leq$ if, whenever $x\leq y$ implies that $x\leq_{1} y$. | ||
+ | |||
+ | c) Use (a) to show there is a finite number of total orders $(A,\leq_1),\cdots,(A,\leq_n)$ such that for all $a,b\in A$ we have | ||
+ | |||
+ | $a\leq b \Leftrightarrow (a\leq_1b \wedge\cdots\wedge a\leq_n b)$ | ||
+ | |||
+ | d) Show that $\leq_1$ is a linear extension of $\leq$ if and only if $(A,\leq_1)$ is a total order and the identity function is a monotone function from $(A,\leq)$ to $(A,\leq_1)$. | ||
+ | |||
+ | ===== Perl ===== | ||
+ | |||
+ | * Write a regular expression that matches a pair of <d> and </d> XML tags and the text between them. The text between the tags can include any other tags. | ||
+ | |||
+ | * The lexical analyzer typically finds the longest matches. Some languages such as Perl have introduced laziness in matching. By adding a question mark to the end of an operator its lazy version is obtained. For example, given an input 'aaaaa', the expression $a*$ will match the entire input. But the lazy version $a*?$ matches the minimum number of possible characters, which is the empty string. Using lazy repetition find a compact representation for the first part. |