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
We can consider
- regular expression
on such alphabets.
Using Propositional Formulas to Denote Finite Sets of Symbols
Language representing that the third coordinate is the logical and of the first two is:
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
The bitwise and relation, shown above, is given by
where is a propositional formula and for are all tuples of values of propositional variables for which is true.
Notational advantage: even if we increase the number of components by adding new variables, the expression remains the same.