Регулярная аппроксимация КС-языков

Определения

Определение:

Контекстно-свободная грамматика $G = \langle N, \Sigma, P, S \rangle$ называется самоприменимой (англ. self-embeded), если $\exists A \in N: A \Rightarrow^* \alpha A \beta$, $\alpha \neq \varepsilon \land \beta \neq \varepsilon$ .

Определение:

Нетерминал $A \in N$ в грамматике $G = \langle N, \Sigma, P, S \rangle$ называется рекурсивным (англ. recursive), если $\exists \alpha,\beta \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha A \beta$ .

Определение:

Нетерминалы $A,B \in N$ в грамматике $G = \langle N, \Sigma, P, S \rangle$ называются взаимно рекурсивными (англ. mutual recursive), если $\exists \alpha_1,\beta_1,\alpha_2,\beta_2 \in (\Sigma \cup N)^* : A \Rightarrow^* \alpha_1 B \beta_1 \land B \Rightarrow^* \alpha_2 A \beta_2$ .

Алгоритм преобразования грамматики в конечный автомат

Лемма:

Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.

Доказательство:

$\triangleright$

В качестве конструктивного доказательства рассмотрим алгоритм построения конечного автомата по грамматике. Также приведем ссылку на формальное доказательство.

$\triangleleft$

Идея алгоритма

Пусть, $N^*$ множество рекурсивных нетерминалов из $N$. Пусть, $P = \{N_1,N_2,\ldots,N_K\}$ разбиение $N^*$ на $k$ дизъюнктных множеств взаимно рекурсивных нетерминалов, $N_1 \cup N_2 \cup \ldots \cup N_k = N^* \land \forall i$ $N_i \neq \emptyset$.

Определим вспомогательную функцию $\mathtt {isLeftType}(N_i)$, которая возвращает $true$, если существует $(A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]$.

Аналогично определим функцию $\mathtt {isRightType}(N_i)$, которая возвращает $true$, если существует $(A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]$

bool isLeftType($N_i$: nonterminal): 
    return $\exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \alpha \neq \varepsilon ]$

bool isRightType($N_i$: nonterminal): 
    return $\exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]$

Будем называть $\mathtt {typeRecursive}$ набор четырех величин $\{left, right, self, cycle\}$

Определим функцию $\mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow \mathtt {typeRecursive}$:

function getTheTypeOfMutualRecursiveSet($N_i$: nonterminal): typeRecurcive
   if !isLeftType($N_i$) and isRightType($N_i$) 
       return left
   if isLeftType($N_i$) and !isRightType($N_i$) 
       return right
   if isLeftType($N_i$) and isRightType($N_i$) 
       return self
   if !isLeftType($N_i$) and !isRightType($N_i$) 
       return cyclic

Состояние $left$ означает, что $N_i$ состоит только из лево-рекурсивных нетерминалов.

Состояние $right$ означает, что $N_i$ состоит только из право-рекурсивных нетерминалов.

Состояние $cyclic$ означает, что $N_i$ состоит только из правил, участвующих в рекурсии.

Состояние $self$ означает, что $i$ такое, при котором грамматика самоприменима.

Заметим, что $\forall i$ $\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) \neq self$, т.к в противном случае грамматика будет самоприменима. В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:

1. Символ алфавит или $\varepsilon$ — добавляем новое правило в автомат;
2. Нерекурсивный нетерминал — запускаемся от всех правых частей правил, который терминал порождает;
3. Рекурсивный нетерминал — в зависимости от типа рекурсивного нетерминала, продолжаем рекурсию (будет ясно из пседокода).

Псевдокод

$Q$ — множество состояний ДКА.

$\Delta$ — множество переходов ДКА.

$T$ — множество допускающих состояний.

function createFA(G: grammar): Automaton              // $G = \langle N, \Sigma, P, S \rangle$ 
    $\mathtt{Q} \leftarrow \varnothing$
    $\Delta \leftarrow \varnothing$
    s = createState()               // createState создает некоторый объект, не принадлежащий $Q$, возвращает этот объект и добавляет его в $Q$    
    f = createState()
    $F \leftarrow \{f\}$
    return makeFA(s,S,f)
     
function makeFA(q0: vertex, a: char, q1: vertex): Automaton
   if a == $\varepsilon$ or a $\in \Sigma$             // пришли в лист дерева разбора
        $\Delta = \Delta \cup \{(q_0,a,q_1)\}$
        return
   if a == $X\beta$ where $X \in (N \cup \Sigma) \land \beta \in (N \cup \Sigma)^* \land |\beta| \gt  0$  
        q = createState()
        makeFA($q_0,X,q_1$)
        makeFA($q, \beta, q_1$)
        return
    if exist $N_i$ where $a \in N_i$  
         foreach b in $N_i$ 
            $q_b$ = createState
         if getTheTypeOfMutualRecursiveSet($N_i$) == left 
            foreach C in $N_i$ where $C \rightarrow X_1 \ldots X_m \land X_1, \ldots X_m \neq N_i$
               makeFA($q_0, X_1 \ldots X_m, q_C$)             
            foreach C,D in $N_i$ where $C \rightarrow DX_1 \ldots X_m \land X_1, \ldots X_m \neq N_i$
               makeFA($q_D, X_1 \ldots X_m, q_C$)
               $\Delta = \Delta \cup \{(q_a,\varepsilon,q_1)\}$
          else                      // рекурсивный нетерминал right или cyclic   
            foreach C in $N_i$ where $C \rightarrow X_1 \ldots X_m \land X_1, \ldots X_m \neq N_i$
               makeFA($q_C, X_1 \ldots X_m, q_1$)             
            foreach C,D in $N_i$ where $C \rightarrow DX_1 \ldots X_m \land X_1, \ldots X_m \neq N_i$
               makeFA($q_D, X_1 \ldots X_m, q_C$)
               $\Delta = \Delta \cup \{(q_0, \varepsilon ,q_a)\}$ 
             return
    foreach p in $P$ where p == $a \rightarrow \beta$
       makeFA($q_0, \beta, q_1$)

Аппроксимации самоприменимой грамматики

В данном разделе покажем методы апроксимации: $\mathrm {RTN}$ (recursive transition network) аппроксимацию и $\mathrm {MN}$ (Mohri and Nederhof's) аппроксимацию — самоприменимой контекстно-свободной грамматики $G = \langle N, \Sigma, P, S \rangle$ к регулярной грамматике. Для удобства будем считать, что грамматика представлена в НФХ.

Автоматы $T_A,T_B$ для грамматики $A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f$

RTN аппроксимация

Построим, по данной грамматике аппроксимирующий ее конечный автомат.

Конечный автомат для грамматики $A \rightarrow aBb \\ A \rightarrow cA \\ B \rightarrow dAe \\ B \rightarrow f$

1. Для каждого нетерминала $A$ в грамматике, создадим новый конечный автомат $T_A$, добавим в него два состояния $q_A$ и $q_{A^*}$.
2. Для каждого правила грамматике $(A \rightarrow X_1 \ldots X_m ) \in P$, введм новые состояния в автомат этого нетерминала $q_0^A \ldots q_m^A$, а также добавим новые правила перехода в $\Delta$: $(q_A, \varepsilon, q_0),(q_0^A,X_1,q_1^A), \ldots,(q_{m-1}^A,X_m,q_m^A),(q_m^A,\varepsilon,q_{A^*})$.
3. Таким образом мы построили множество конечных автоматов $T$ = $\{ T_A \mid A \in N\}$ для каждого нетерминала $A$. Теперь объединим все в один автомат. Объединим все состоянии автоматов из $T$ в множество $Q$. Скопируем все переходы каждого автомата из $T$ в $\Delta$. Далее для каждого перехода вида $(q,A,p), A\in N$, вместо него добавим два новых перехода: $(q, \varepsilon, q_A),(q_A^{*}, \varepsilon, p)$.

MN аппроксимация

Построим по данной самоприменимой контекстно-свободной грамматике $G$ регулярную грамматику $G^*$.

1. Для каждого нетерминала $A \in N$ из $G$, добавим нетерминалы $A$ и $A^*$ в $G^*$.
2. Для каждого правила $A \rightarrow {\alpha}_{0} B_1 {\alpha}_{1} B_2 {\alpha}_{2} \ldots B_m {\alpha}_{m}$, где $B_1, \ldots, B_m \in N \land {\alpha}_i \in \Sigma^*$. Добавим в $G^*$ нетерминалы $B_1 \ldots B_m , B_1^* \ldots B_m^*$ и следуюшие правила: $\begin{cases} A \rightarrow {\alpha}_0 B_1 \\ B_1^* \rightarrow {\alpha}_1 B_2\\ \ldots \\ B^*_m \rightarrow {\alpha}_m A^* \end{cases}$.

(Если $m = 0$, тогда добавим правило $A \rightarrow {\alpha}_0 A^*$).

В итоге $G^*$ — правоконтекстная грамматика, эквивалентная конечному автомату, который задает регулярный язык.

Пример

$G = \begin{cases} A \rightarrow \alpha B \alpha \\ B \rightarrow \beta A | \beta \end{cases}\Rightarrow G^* = \begin{cases} A \rightarrow \alpha B \\ A^* \rightarrow B^* | \varepsilon \\ B \rightarrow \beta A | \beta B^* \\ B^* \rightarrow \alpha A^* | \varepsilon \end{cases}$

Исходная грамматика $G$ генерирует язык: $\{(ab)^n a^n \mid n \gt 0\}$. Результирущая грамматика $G^*$ генирирует регулярный язык: $(ab)^+ a^*$.

Сравнение двух методов

Ясно, что оба языка, генерируемых конечным автомат для первого метода и апрокисимируещей граматикой для второго метода, содержат в себе язык генерируемый исходной грамматикой. Привлекателным свойством $\mathrm {MN}$ аппроксимации по сравнению с $\mathrm {RTN}$, то, что она можеть быть применима к большим грамматикам: для каждого нетерминала грамматике $G$, добавляется не более одного нового нетерминала в $G^*$ и размер результирующий грамматики максимум в $2$ раза больше, чем размер исходной. Так как для $\mathrm {RTN}$ апроксимации грамматики $G = \langle N, \Sigma, P, S \rangle$, количество состаяний апроксимируещего автомата в худшем случаи может составлять $O(|N|^2)$, что может быть критично для аппроксимации больших грамматик. Также,еще несколько эффекивных методов аппрокимации можно найти в статьях, приведенных в ссылках.

См. также

• Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
• Замкнутость регулярных языков относительно различных операций
• Основные определения, связанные со строками
• Замкнутость КС-языков относительно различных операций

Источники информации

• Jean-Claude Junqua,Gertjan van Noord — Robustness in Language and Speech Technology — Kluwer Academic Publishers, 2001 — ISBN 0-7923-6790-1
• Strongly Regular Grammars and Regular Approximation of Contex-Free Languages
• Practical Experiments with Regular Approximation of Context-Free Languages
• Willem J. M. Levelt — An Introduction to the Theory of Formal Languages and Automata — John Benjamin B.V., 2008 — ISBN 978-90-272-3250-2