ADP for MCFL

An in-depth description of ADP for MCFL can be found in my master’s thesis. Below is a very short end-user summary.

How are MCFL integrated into ADP?

Regular tree grammars are used for that purpose, as in ADP for CFL. To incorporate the expressive power of MCFL, the rewriting functions of MCFG are made part of the term language over which the tree grammar is described.

Therefore, we define an ADP-MCFL grammar over $\Sigma$ as $\mathcal{G} = (V,\mathcal{A},Z,F,P)$ which is a regular tree grammar over $\Sigma \times F$.

$\mathcal{A}$ is the alphabet of the input string.

$\Sigma$ is a signature over $\mathcal{S}$, where the return type of each function symbol is $\mathcal{S}$ and each argument is of type $\mathcal{S}$ or $\mathcal{A}^n$.

$V$ is the set of non-terminals.

$Z \in V$ is the axiom.

$F$ is the set of rewriting functions as in MCFG.

$P$ is the set of productions with the form $v \rightarrow t$ with $v \in V, t \in T_{\Sigma \times F}(V)$.

The language generated by ADP-MCFL grammars is

$\mathcal{L}(\mathcal{G}) = \mathcal{L}(Z) = \{ t \in T_{\Sigma \times F} \mid Z \rightarrow^* t \}$

Example

$$ \begin{equation*} \mathcal{G} = (\{Z,K,P,B\},\{a,u,g,c\},Z,F,P) \text{ over } \Sigma \end{equation*} $$

$P:$

$$ \newcommand{\op}[1]{\operatorname{#1}} \begin{align} Z &\rightarrow (\op{f}_1,\op{r}_1) (B,S) \mid (\op{f}_2,\op{r}_2) (P,S,S) \mid (\op{f}_3,\op{id}) () \mid (\op{f}_4,\op{r}_3) (K,K,S,S,S,S)\\ K &\rightarrow (\op{f}_5,\op{r}_4) (K,P) \mid (\op{f}_6,\op{id}) (P)\\ P &\rightarrow (\op{f}_7,\op{id})((a,u)) \mid (\op{f}_7,\op{id})((u,a)) \mid ...\\ B &\rightarrow (\op{f}_8,\op{id}) (a) \mid (\op{f}_8,\op{id}) (g) \mid (\op{f}_8,\op{id}) (c) \mid (\op{f}_8,\op{id}) (u) \end{align} $$

$F:$

$$ \begin{align*} \op{id} (x) &= x\\ \op{r}_1 (b,s) &= bs\\ \op{r}_2 ((p_1,p_2),s,s) &= p_1 s p_2 s\\ \op{r}_3 [(k^1_1,k^1_2),(k^2_1,k^2_2),s_1,s_2,s_3,s_4] &= k^1_1 s_1 k^2_1 s_2 k^1_2 s_3 k^2_2 s_4\\ \op{r}_4 ((k_1,k_2),(p_1,p_2)) &= (k_1 p_1, p_2 k_2) \end{align*} $$

$\Sigma:$

$$ \begin{align*} \op{f}_1,\op{f}_5&: \mathcal{S} \times \mathcal{S} &\rightarrow \mathcal{S} \\ \op{f}_2&: \mathcal{S} \times \mathcal{S} \times \mathcal{S} &\rightarrow \mathcal{S} \\ \op{f}_3&: \{()\} &\rightarrow \mathcal{S}\\ \op{f}_4&: \mathcal{S}^6 &\rightarrow \mathcal{S} \\ \op{f}_6&: \mathcal{S} &\rightarrow \mathcal{S}\\ \op{f}_7&: (\mathcal{A} \times \mathcal{A}) &\rightarrow \mathcal{S}\\ \op{f}_8&: \mathcal{A} &\rightarrow \mathcal{S} \end{align*} $$

How does the syntax of adp-multi look like?

Have a look at the syntax page.