# 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.