Differences
This shows you the differences between two versions of the page.
regular_expressions_for_automata_with_parallel_inputs [2009/04/28 20:24] vkuncak |
regular_expressions_for_automata_with_parallel_inputs [2015/04/21 17:32] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Regular Expressions and Automata with Parallel Inputs ====== | ||
- | |||
- | 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{array}{l} | ||
- | a_1 \\ | ||
- | \ldots \\ | ||
- | a_n | ||
- | \end{array} | ||
- | \right) | ||
- | \] | ||
- | |||
- | We can consider | ||
- | * regular expression | ||
- | * automata | ||
- | on such alphabets. | ||
- | |||
- | Suppose $\Sigma = \{0,1\}$. | ||
- | |||
- | Let $n=3$. | ||
- | |||
- | $\Sigma^3 = \{ (0,0,0),(0,0,1),\ldots,(1,1,1) \}$. | ||
- | |||
- | Language representing that the third coordinate is the logical **and** of the first two is: | ||
- | \[ | ||
- | \left( | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | 0 \\ | ||
- | 0 \\ | ||
- | 0 \\ | ||
- | \end{array} | ||
- | \right) | ||
- | + | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | 0 \\ | ||
- | 1 \\ | ||
- | 0 \\ | ||
- | \end{array} | ||
- | \right) | ||
- | + | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | 1 \\ | ||
- | 0 \\ | ||
- | 0 \\ | ||
- | \end{array} | ||
- | \right) | ||
- | + | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | 1 \\ | ||
- | 1 \\ | ||
- | 1 \\ | ||
- | \end{array} | ||
- | \right) | ||
- | \right)^* | ||
- | \] | ||
- | |||
- | 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 | ||
- | \[ | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | 1 \\ | ||
- | 1 \\ | ||
- | 0 \\ | ||
- | \end{array} | ||
- | \right) | ||
- | + | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | 1 \\ | ||
- | 1 \\ | ||
- | 1 \\ | ||
- | \end{array} | ||
- | \right) | ||
- | \] | ||
- | The bitwise and relation is given by | ||
- | \[ | ||
- | [z \leftrightarrow (x \land y)]^* | ||
- | \] | ||
- | |||
- | In general | ||
- | \begin{equation*} | ||
- | [p(v_1,\ldots,v_n)] = | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | a_{11} \\ | ||
- | \ldots \\ | ||
- | a_{1n} | ||
- | \end{array} | ||
- | \right) | ||
- | + \\ | ||
- | \ldots \\ | ||
- | + \\ | ||
- | \left( | ||
- | \begin{array}{l} | ||
- | a_{k1} \\ | ||
- | \ldots \\ | ||
- | a_{kn} | ||
- | \end{array} | ||
- | \right) | ||
- | \end{equation*} | ||
- | 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. | ||