Don't Cross the Wires Prove that CVP ${?}_L$ FLAT$-$CVP$,$ where wires are not allowed to overlap in the flat circuit.

Dyck Languages in $N{C}^1$

The ordinary Dyck Language $D_1$ is essentially the language we have called "Paren" in the lectures $-$ here we'll redefine it to have alphabet $\{a,b\}$ and context$-$free grammar $S$aBb,$SSS,$ and $S.$ The Dyck$-2$ Language $D_2$ is similar, but has two types of parentheses which must be nested properly. Its alphabet is $\{a,b,c,d\}$ and its context$-$free grammar is $S$aSb,$ScSd,SSS,$ and $S.$

$($a$)$ Prove that $D_1$ is in the class $N{C}^1.$

$($b$)$ Prove that $D_2$ is in the class $N{C}^1.$

In fact both languages are in the perhaps smaller class $T{C}^0,$ and you should concentrate on methods using the MAJORITY language that we will prove to be in $N{C}^1$ in Week $13.$ You may also find it useful to think about why these languages are in LOGSPACE, but you will have to adapt those methods to use them in $N{C}^1.$