Multiple_Context-Free_Languages.tex

\chapter[Многокомпонентные контекстно-свободные языки]{Многокомпонентные контекстно-свободные языки}

\textit{Многокомпонентные контекстно-свободные грамматики (MCFG)} \sidenote{
    Мы дадим лишь базовые определения и приведём краткий обзор данного класса. В качестве отправной точки для более детального изучения можно порекомендовать материалы, подготовленные Сильваном Салвати (Sylvain Salvati) \url{https://www.labri.fr/perso/salvati/downloads/cours/esslli/}.
} --- это строгое расширение контекстно-свободных грамматик для описания синтаксиса естественных языков.

Класс языков, порождаемых MCFG (называемых многокомпонентными контекстно-свободными языками, MCFL), входят в класс контекстно-зависимых языков и включают в себя класс контекстно-свободных языков.

\begin{definition}
    \textit{m-MCFG(r)} это четвёрка $\langle \Sigma, N, S, P \rangle$
    \begin{itemize}
      \item $\Sigma$ --- терминальный алфавит
      \item $N$ --- нетерминальные символы. Максимальный ранг (арность, местность) равен $m$.
      \item $S$ --- стартовый нетерминальный символ ранга 1
      \item $P$ --- множество правил вида
      $$
      A(s_1,\ldots,s_k) \leftarrow B_1(x_1^1,\ldots,x_{k_1}^1), \ldots, B_n(x_1^n,\ldots,x_{k_n}^n)
      $$
      \begin{itemize}
        \item $A$ --- нетерминал ранга $k$, $B_i$ --- нетерминалы ранга $k_i$, $n \leq r$;
        \item Все $x^i_j$ попарно различны (переменные)
        \item Строки $s_i \in (\Sigma \cup X)^*, X = \bigcup_{i=1}^n \bigcup_{j=1}^{k_i} {x^i_j}$
        \item Каждая $x^i_j$ встречается не более одного раза в последовательности $s_1,\ldots, s_k$. Если допустить несколько вхождений, то это PMCFG.
      \end{itemize}
  \end{itemize}
\end{definition}

MCFG позволяет правилам грамматики оперировать несколькими компонентами одновременно. Нетерминалы в MCFG могут выводить не одну строку, а кортеж из нескольких строк.
Также, можно произвольно комбинировать компоненты — переставлять их, дублировать, вставлять между ними терминалы.

В литературе можно еще встретить следующую запись правил вывода:
$$
A_0 \leftarrow f[A_1, A_2,\ldots,A_q]
$$
где $f$ — функция, аргументы и значения которой представляют собой кортежи строк, и
удовлетворяет следующим условиям:
\begin{enumerate}
  \item Каждый компонент значения $f$ представляет собой конкатенацию некоторых константных строк и некоторых компонентов своих аргументов
  \item Каждый компонент не может встречаться в $f$ более одного раза.
\end{enumerate}


Приведём примеры многокомпонентных контекстно-свободных грамматик.
Для начала рассмотрим грамматики для известных нам контекстно-свободных языков и перепишем их в MCFG грамматику:

\begin{itemize}
    \item \textbf{Язык вложенных скобок}

    \begin{align*}
      S &\rightarrow aSb &\quad& S(axb) \leftarrow S(x) \\
      S &\rightarrow \varepsilon &\quad& S(\varepsilon) \leftarrow
    \end{align*}

    \item \textbf{Язык Дика на одном типе скобок}

     \begin{align*}
      S &\rightarrow aSbS &\quad& S(ax_1bx_2) \leftarrow S(x_1), S(x_2) \\
      S &\rightarrow \varepsilon &\quad& S(\varepsilon) \leftarrow
    \end{align*}

    В MCFG-варианте ранг $S$ равен двум, то есть $S$ возвращает две компоненты. Такая грамматика записывается как 2-MCFG.

\end{itemize}

Теперь рассмотрим грамматику для языка $L = \{a^nc^mb^nd^m \mid n \in \mathbb{N}, m \in \mathbb{N} \}$, не являющегося контекстно-свободным, но выразимого в 2-MCFG(2) грамматике :
\begin{align*}
    S(x_1 y_1 x_2 y_2) & \leftarrow P(x1,x2),Q(y_1,y_2) \\
    P(ax_1, bx_2) & \leftarrow P(x_1,x_2) \\
    P(\varepsilon,\varepsilon) &\leftarrow  \\
    Q(cx_1, dx_2) & \leftarrow Q(x_1,x_2) \\
    Q(\varepsilon,\varepsilon) &\leftarrow
\end{align*}

\section{Расширения MCFG}

Как было сказано раннее, в MCFG каждая переменная в левой части правила встречается ровно один раз в его правой части, и наоборот.
Если мы откажемся от этого ограничения, мы получим более общие грамматики.

\begin{enumerate}
  \item \textbf{PMCFG} (Parallel Multiple Context-Free Grammar).\\
  \\
  PMCFG задает некоторое ограничение над MCFG.
  В правилах PMCFG компоненты должны комбинироваться параллельно, без перемешивания между разными нетерминалами: $i$-й компонент результата формируется только из $i$-х компонентов правой части.

  $$
  A(xy, xz) \leftarrow B(x), C(y, z)
  $$

  \item \textbf{sLMG (Simple LMG, Simple Literal Movement Grammar)}.\\
  \\
  sLMG является ограниченным подклассом LMG (Literal Movement Grammar).
  Общее определение LMG допускает любую комбинацию переменных и терминалов в компонентах левой и правой части правила.
  LMG являются грамматическими формализмами, основанными на предикатах над строковыми кортежами и расширяют класс контекстно-свободных грамматик.

  Предикатом будем называть синтаксическую единицу вида $A(\alpha_1, \alpha_2, ..., \alpha_n)$, где A — нетерминальный символ (имя предиката),
  $\alpha_1, \alpha_2, ..., \alpha_n$ --- аргументы (последовательности терминалов и переменных).

  Правила (так же называемые клаузы, clauses) в такой грамматике имеют вид $\varphi \leftarrow \psi_1, \psi_2, ..., \psi_m$, где $\phi$ --- предикат в левой части (голова),
  $\psi_1, \psi_2, ..., \psi_m$ --- последовательность предикатов в правой части (тело). Клауза может инстанцироваться (т.е конкретные значения будут подставлены в аргументы) путем замены каждой переменной в клаузе на строку.\\
  \\
  \textbf{Simple LMG} — это подкласс LMG, где каждая клауза (правило) должна удовлетворять трём синтаксическим ограничениям:
  \begin{itemize}
    \item Non-combinatorial (некомбинаторность). Аргументы каждого $\psi_i$ должны быть переменными.
    \item Bottom-up nonerasing (восходящая неудаляемость). Все переменные из каждого $\psi_i$ также должны встречаться в $\varphi$. Это означает, что правая часть не может вводить новые переменные --- все переменные должны "приходить" из левой части.
    \item Bottom-up linear (восходящая линейность). Ни одна переменная не встречается в $\varphi$ более одного раза.
  \end{itemize}
\end{enumerate}