4
$\begingroup$

I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N.

Afaik the Chomsky-Schützenberger representation theorem states that you can convert and context-free language into a Dyck-N language, using a homomorphism and a intersection to regular language.

It appears that Dyck-2 is already enough for that? Or is Dyck-2 simply necessary, but not sufficient, so it is just used to disprove a models ability to learn Dyck-N?

I thought maybe you can represent any Dyck-N language by a Dyck-2 language that uses "binary" representations of brackets. This would theoretically be also possible for Dyck-1 by unary encoding, but decoding there would not be suffix-free, which breaks the homomorphism, I guess? Maybe someone could validate this approach, because I have never seen it formulated out.

Thank you very much.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Whether 2-bracket Dyck is equivalent to $n$-bracket Dyck ($n\ge2$)? Short answer: that depends which operations one allows.

The Chomsky–Schützenberger Theorem states that every context-free language $L\subseteq \Sigma^*$ can be written as $L=h(D_{T}\cap R)$, where $D_T$ is the Dyck language over the bracket pairs on $T\cup \overline T$, $R\subseteq (T\cup \overline T)^*$ a regular language, and $h: (T\cup \overline T) \to \Sigma^*$ a homomorphism.

Some intuition here. We can prove the CST using a representation of $L$ as a pushdown automaton. Each transition is represented as a sequence of brackets. These brackets represent both the input letter that is read and the symbols that are popped and pushed during that instruction. It is possible to show that two different pushdown symbols suffice for the PDA. On the othet hand $\Sigma$ is not bounded. As we use a homomorfism to decode $\Sigma$ from $T$, in general $T$ must be as least as large as $\Sigma$. Hence we cannot bound the number of bracket-pairs.

In the theory of Abstract Families of Languages one studies language families and their closure properties. We have the result that the context-free languages are a cone, the smallest family of languages that includes $D_2$ (the Dyck language over two bracket pairs) and is closed under homomorphisms, inverse homomorphisms, and indersection with regular languages.

Basically the CST construction works to obtain such a result. The inverse homomorphism however can be used to code both input letters and pushdown symbols into two pairs of brackets. The context-free language is of the form $L = h( g^{-1} (D_2) \cap R)$.

PS. Below an old slide I have. (note. The roles of $g$ and $h$ are reversed.) It illustrates that we can see a PDA diagram as a finite state automaton, which defines regular sequences of instructions: the set $R$. Whether such a sequence is allowed as a computation has to be verified by checking that the pop and push instructions are legal. Legal sequences are Dyck sequences (with matching brackets). Thus we map the instructions to $D_2$ here using $h$. Finally the language of the PDA is the sequence of input letters, which is obtained from the instructions using the second morphism $g$.

enter image description here

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Haha you again, thank you! I however didn't quite get your construction (and in fact the construction of CST). Could you break this down for dummys or tell me if my above construction is right? I.e. in case of the PDA I would simply (binary) encode the bracket type as a sequence of brackets of both types and replace any state transition by $log_2(n)$ states that decode the next $log_2(n)$ symbols to obtain the "real" bracket type . This is equivalent to enacting an auxillary homomorphism that translates sequences of $\Sigma_2$ to $\Sigma_n$. $\endgroup$
    – Crea Teeth
    Oct 27 at 19:19
  • $\begingroup$ I guess the auxiliary homomorphism would be $g$ then? $\endgroup$
    – Crea Teeth
    Oct 28 at 13:03
  • 1
    $\begingroup$ @CreaTeeth Correct. The additional morphism $g$ maps input symbols and pusdown symbols into (binary) sequences of brackets. Thus ensuring we only need two pairs of brackets. (I did not reconstruct all details, that is probably too much for this answer.) It is not necessary to encode the states of the PDA as the sequences of instructions of the PDA are completely specified by regular $R$. $\endgroup$
    – Hendrik Jan
    Oct 28 at 13:55
  • 1
    $\begingroup$ @CreaTeeth Apart from the Dyck representation of CFL it is already instructive to consider the construction that shows every PDA can be restricted to have only two stack symbols. Again the alphabet of stack symbols can be binary encoded, and the PDA pops and pushes such binary sequences. This will increase the number of states (because we pop in several steps). $\endgroup$
    – Hendrik Jan
    Oct 28 at 13:59
  • $\begingroup$ Ah, I only now see the parallel between the stack alphabet and $T$ as described in your initial answer. Intuitively, the stack keeps track of where in the tree we are and thus needs a symbol for at least every Non-Terminal. This is equivallent how the stack keeps track of all unclosed bracket types when parsing $\mathcal{D}_T$. Binary encoding the stack alphabet already answers my question. This was very helpful, thank you very much! $\endgroup$
    – Crea Teeth
    Oct 28 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.