This is an old revision of the document!
Regular Expressions and Automata with Parallel Inputs
Given an alphabet , we consider a larger (but still finite) alphabet for some . Keep in mind that 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.
Using Propositional Formulas to Denote Finite Sets of Symbols
Suppose .
Let .
.
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 , we can consider where are three names of variables.
We then use propositional formulas to denote possible values of bits. For example, 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, shown above, is given by \[
[z \leftrightarrow (x \land y)]^*
\]
In general
where is a propositional formula and for are all tuples of values of propositional variables for which is true.
Notational advantage: the set of variables can be larger, the expression is still the same.