# 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
• 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:

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

In general

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.