Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
regular_expressions_for_automata_with_parallel_inputs [2009/04/28 20:26] vkuncak |
regular_expressions_for_automata_with_parallel_inputs [2015/04/21 17:32] (current) |
||
|---|---|---|---|
| Line 2: | Line 2: | ||
| Given an alphabet $\Sigma$, we consider a larger (but still finite) alphabet $\Sigma^n$ for some $n$. Keep in mind that $(a_1,\ldots,a_n) \in \Sigma_n$ is just one symbol; we often write it as | Given an alphabet $\Sigma$, we consider a larger (but still finite) alphabet $\Sigma^n$ for some $n$. Keep in mind that $(a_1,\ldots,a_n) \in \Sigma_n$ is just one symbol; we often write it as | ||
| - | \[\left( | + | \begin{equation*}\left( |
| \begin{array}{l} | \begin{array}{l} | ||
| a_1 \\ | a_1 \\ | ||
| Line 9: | Line 9: | ||
| \end{array} | \end{array} | ||
| \right) | \right) | ||
| - | \] | + | \end{equation*} |
| We can consider | We can consider | ||
| Line 15: | Line 15: | ||
| * automata | * automata | ||
| on such alphabets. | on such alphabets. | ||
| + | |||
| ====== Using Propositional Formulas to Denote Finite Sets of Symbols ====== | ====== Using Propositional Formulas to Denote Finite Sets of Symbols ====== | ||
| Line 25: | Line 26: | ||
| Language representing that the third coordinate is the logical **and** of the first two is: | Language representing that the third coordinate is the logical **and** of the first two is: | ||
| - | \[ | + | \begin{equation*} |
| \left( | \left( | ||
| \left( | \left( | ||
| Line 59: | Line 60: | ||
| \right) | \right) | ||
| \right)^* | \right)^* | ||
| - | \] | + | \end{equation*} |
| Instead of considering $\Sigma^3$, we can consider $\{x,y,z\} \to \Sigma$ where $x,y,z$ are three names of variables. | Instead of considering $\Sigma^3$, we can consider $\{x,y,z\} \to \Sigma$ where $x,y,z$ are three names of variables. | ||
| We then use propositional formulas to denote possible values of bits. For example, $[x \land y]$ denotes the regular expression | We then use propositional formulas to denote possible values of bits. For example, $[x \land y]$ denotes the regular expression | ||
| - | \[ | + | \begin{equation*} |
| \left( | \left( | ||
| \begin{array}{l} | \begin{array}{l} | ||
| Line 80: | Line 81: | ||
| \end{array} | \end{array} | ||
| \right) | \right) | ||
| - | \] | + | \end{equation*} |
| The bitwise **and** relation, shown above, is given by | The bitwise **and** relation, shown above, is given by | ||
| - | \[ | + | \begin{equation*} |
| [z \leftrightarrow (x \land y)]^* | [z \leftrightarrow (x \land y)]^* | ||
| - | \] | + | \end{equation*} |
| In general | In general | ||
| Line 109: | Line 110: | ||
| where $p(v_1,\ldots,v_n)$ is a propositional formula and $(a_{i1},\ldots,a_{in})$ for $1 \leq i \leq k$ are all tuples of values of propositional variables for which $p(v_1,\ldots,v_n)$ is true. | where $p(v_1,\ldots,v_n)$ is a propositional formula and $(a_{i1},\ldots,a_{in})$ for $1 \leq i \leq k$ are all tuples of values of propositional variables for which $p(v_1,\ldots,v_n)$ is true. | ||
| - | Notational advantage: the set of variables can be larger, the expression is still the same. | + | Notational advantage: even if we increase the number of components by adding new variables, the expression remains the same. |