Question

Prove that if A is a regular language, a family of branching programs$\mathbf{(}{\mathbf{B}}_1\mathbf{,}{\mathbf{B}}_2\mathbf{\dots }\mathbf{)}$ exists wherein each${\mathbf{B}}_n$ accepts exactly the strings in A of length n and is bounded in size by a constant times n.

Short answer

The definition of regular language needs to be understood to solve the above problem i.e., “a formal language that is expressed using a regular expression, is called as a regular language”.

Step-by-step solution

Define Regular Language

Now consider a regular language,$A$ then a family of branching program $\mathbf{(}{\mathbf{B}}_1\mathbf{,}{\mathbf{B}}_2\mathbf{\dots }\mathbf{)}$in which a string, of length $n$in language,$A$ is accepted by each $B_n$and is bounded by a fixed time$n$ in size. It is possible to do so in the manner described below.

Understand the Branching Program

Now consider a branching program. A branching program is known as “a directed acyclic graph where labels of all the nodes are maintained by the variables, except for two output nodes which are labelled as 1 or 0 .

The term "query node" refers to all nodes whose labels are kept up to date by the variables. Every query node consists of two outgoing edges: one is labelled 1 and another one is labelled .0 Both output nodes don’t consist outgoing edges.

Prove that 1(n-1)*2=O(n) 

The n-input function or a finite regular language can therefore be computed by a branching programme that consists of a constant$O\left(n\right)$ size, according to the definitions of branching programme and regular language A as given above.
A circuit n is implemented as a Bubble-sort. Each branching programme in a group is chosen so that they all accept exactly the strings in A of length n.

After carefully comparing, it can be used to compare two bits. Let the inputs be$x_1,x_2$and the outputs be$y_1,y_2$.

A sub-circuit can be written which accomplishes this as$y_1=OR(x_1,x_2)$ &$y_2=AND(x_1,x_2)$. This circuit contains a size of two.

Now, an array can be mimicked using the action of the bubble-sort algorithm. It can be implemented one step at position to be the n input, n-output subcircuit that passes through all the inputs taken as$<k$ and $\ge k+1$are unchanged.

Now, the above described compare-swap sub-circuit, on $<k$and$\ge k+1st$ input is used for the generation of $kth$and output.$k+1st$ This still has size two. Now, a pass can be implemented as the serial concatenation of steps for each of , $k=1,2,\dots ,n-1$which has a size.$(n-1)*2$

A bubble-sort can be Proceed to implement as the serial concatenation of one pass. Therefore, this gives a size

$1(n-1)*2=O\left(n\right)$

This means that "a family of branching programmes $\mathbf{(}{\mathbf{B}}_1\mathbf{,}{\mathbf{B}}_2\mathbf{\dots }\mathbf{)}$in which a string, of length n in language A, is accepted by each member ${\mathbf{B}}_n$" may be inferred from the reasoning given above.