Regular Languages in $ \mathsf{\text{}NC^1}$

Question

Theorem : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$.

To prove the theorem stated above we need some theorems and definitions given below :

Barrington Theorem : A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in $\mathsf{\text{}NC^1}$.

Proof Idea of Barrington Theorem is like small depth boolean circuit implies small group program and small group program implies small branching program.

Monoid : In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

I google and find out a research paper but not able to understand much (some of the things that I have understood I have written above). A high level proof idea or an resource to prove the theorem stated above will be helpful.

Answer 1

Let $L$ be a regular language. Take some DFA $\langle q_0, Q, \delta, F \rangle$ that accepts $L$. There is a constant size circuit whose input is a symbol $\sigma$, and whose output is the function $q \mapsto \delta(q,\sigma)$. In other words, if $Q = \{q_1,\ldots,q_m\}$, then in input $\sigma$, the circuit computes the sequence $\delta(q_1,\sigma), \ldots, \delta(q_m,\sigma)$.

There is another constant size circuit whose inputs are two functions $f,g\colon Q \to Q$ (such as the outputs of the circuit above), and whose output is their composition $q \mapsto f(g(q))$. As before, we encode the inputs and outputs as sequences of $m$ states.

Given $n$, construct a circuit that computes whether a given input word $\sigma_1 \ldots \sigma_n$ belongs to $L$ as follows. Assume by simplicity that $n = 2^t$.

• Compute the functions $q \mapsto \delta(q,\sigma_1), \ldots, q \mapsto \delta(q,\sigma_n)$ using the constant size circuit from the first paragraph.
• Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2), \ldots, q \mapsto \delta(q,\sigma_{n-1}\sigma_n)$ using the constant size composition circuit from the second paragraph.
• Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2\sigma_3\sigma_4), \ldots, q \mapsto \delta(q,\sigma_{n-3} \sigma_{n-2} \sigma_{n-1} \sigma_n)$ using the constant size composition circuit.
• Continue in the same way for $t-2$ more levels, until you compute the function $\varphi$ given by $q \mapsto \delta(q, \sigma_1\ldots\sigma_n)$.
• Using a constant size circuit, determine whether $\varphi(q_0) \in F$.

This circuit has depth $O(\log n)$ and size $O(n)$, and moreover it is uniform in $n$. This shows that $L \in \mathsf{NC^1}$.