ТМВ-2020-Семинар-25.02.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Контекстно-свободные грамматики

Рассмотрим алфавит \(\Sigma=\{i,+,-,*,/,(,)\}\)

Опишем грамматику для корректного арифметического выражения:

\( Exp \to i \\ Exp \to Exp \; Op \; Exp \\ Exp \to (Exp) \\ \\ Op \to + \\ Op \to - \\ Op \to * \\ Op \to / \)

Используя символ \(\mid\), можно записать соответствующую грамматику более компактно:

\( Exp \to i \mid Exp \; Op \; Exp \mid (Exp) \\ Op \to + \mid - \mid * \mid / \)

В таких автоматах используется стек (теоретически с бесконечной памятью). По РВ можно составить КС грамматику. Например, построим грамматику по выражению \(a^*b\).

\( S \to Ab \;\; \color{gray}{a^*b} \\ A \to \varepsilon \mid Aa \)

Теперь рассмотрим преобразование для выражения \(a(b+c^*)\).

\( S \to aB \;\; \color{gray}{a(b+c^*)} \\ B \to b \mid C \\ C \to Cc \mid \varepsilon \)

Отметим, что множество регулярных языков входит в множество КС грамматик

Задачи на построение КС грамматик

Задача 1

Построить для языка \(L=\{a^nb^n\mid n \in \mathbb{N_0}\}\) КС грамматику.

Решение

\(S \to aSb \mid \varepsilon\)

Задача 2. Палиндром

Построить для языка \(L=\{\omega\in\{a,b\}^*\mid \omega \text{— палиндром}\}\) КС грамматику.

Попробуем описать простейшие палиндромы и правила их создания:

  • \(\varepsilon,a,b\) — палиндромы;
  • если \(\omega\) — палиндром, то \(a\omega a, b\omega b\) — тоже палиндромы.

Решение

\(S \to aSa \mid bSb \mid a \mid b \mid \varepsilon\)

Задача 3. Правильная скобочная последовательность

Построить для языка \(L=\{\omega\in\{(,)\}^*\mid \omega \text{— правильная скобочная последовательность}\}\) КС грамматику.

Примеры правильных последовательностей \(\varepsilon, (), ()(), ((())((())))\).

Решение

\(S \to (S) \mid SS \mid\varepsilon \\ S \to (S)S \mid \varepsilon\)

Задача 4. Поиск грамматики, удовлетворяющей языку

Какая из нижеприведённых грамматик генерирует все слова языка с одинаковым количеством \(a,b\).

\( S \to aSb \mid bSa \mid \varepsilon \\ S \to abS \mid baS \mid \varepsilon \\ S \to abSba \mid baSab \mid \varepsilon \\ S \to SabS \mid SbaS \mid \varepsilon \)

Ответ

Никакая. Ни одна из вышеприведённых грамматик не генерирует все слова. Например, слово \(baab\), входящее в наш язык, не генерируется первой грамматикой, а слово \(aabb\) — оставшимися грамматиками.

Грамматика должна содержать все слова, принадлежащие языку, и не должна генерировать новые, не принадлежащие ему.

Задача 5. Определение языка по грамматике

Какие слова генерирует грамматика \(S \to aSb\)

Ответ

\(\emptyset\). Никакие слова нельзя получить из приведённой в задании грамматики.

Задача 6. Объявление функции на C++

В алфавите \(\Sigma=\{\)int, double, void, name,(,),,,",;\(\}\) построить грамматику правильного объявления функции на языке C++.

Примеры корректных объявлений функций: int name();, void name(void);, int name(double name);, double name(double name, int name);.

Решение

\(S \to T \) name (\(L\))
\(T \to \)int \(\mid\) double \(\mid\) void
$$L \to \varepsilon \mid L_k $$
$$L_k \to A \mid A$$ , $$ L_k$$
$$A \to T \mid T $$ name

Расширив алфавит символом *, можем добавить в грамматику указатели. Тогда одно из правил примет вид:
\(T \to \)int \(\mid\) double \(\mid\) void \(\mid\) \(T\)*

Задача 7. Построение грамматик по РВ

Задача 7.1

Построить КС грамматику для РВ \((ab+ba)^*\).

Решение

\( S \to ST \mid \varepsilon \\ T \to ab \mid ba \\ \text{или более компактная запись} \\ S \to Sab \mid Sba \mid \varepsilon \)

Задача 7.2

Построить КС грамматику для РВ \((ab)^+ + (aba)^+\).

Решение

\( S \to A \mid B \\ A \to A_1ab \\ A_1 \to A_1ab \mid \varepsilon \\ B \to B_1aba \\ B_1 \to B_1aba \mid \varepsilon \)

Задача 7.3

Построить КС грамматику для РВ \(ab^*+a(ba)^*\).

\( S \to aA \mid aB \\ A \to Ab \mid \varepsilon \\ B \to Bba \mid \varepsilon \)

Приведение КС грамматики в нормальную форму

Правила в нормальной форме по Хомскому выглядят следующим образом:
\( U \to AB \\ U \to a \\ S \to \varepsilon\)
и не может быть правила вида:
\(U \to \varepsilon\),
где \(A, B, U\) — нетерминалы, не являющиеся аксиомой, \(a\) — терминал, \(S\) — аксиома.

Алгоритм приведения в нормальную форму дан в лекции 3.

Пример

Привести к нормальной форме следующую грамматику:
\( S \to ASA \mid aB \\ A \to B \mid S \\ B \to b \mid \varepsilon \)

  • Определение новой аксиомы

Будем считать теперь аксиомой \(S_0\) с правилом \(S_0 \to S\)

  • Удаление \(\varepsilon\)-правил

Имеем правило $$B \to \varepsilon$$, удаляя его, дополним все правила, где встречается нетерминал \(B\). Получим:
\( S_0 \to S \\ S \to ASA \mid aB \mid\color{red}{a} \\ A \to B \mid S \mid \color{red}{\varepsilon} \\ B \to b \)

Теперь имеем правило $$A \to \varepsilon$$, удаляя его, дополним правила:
\( S_0 \to S \\ S \to ASA \mid aB \mid a \mid \color{red}{SA \mid AS}\ \color{gray}{\mid S \text{— это правило можно опустить}} \\ A \to B \mid S \\ B \to b \)

  • Устранение длинных правил

Имеем длинное правило $$S \to ASA$$. Устраним его, введя нетерминал $$A_1$$. Получим:
\( S_0 \to S \\ S \to AA_1 \mid aB \mid a \mid SA \mid AS \\ A \to B \mid S \\ \color{red}{A_1 \to SA} \\ B \to b \)

  • Удаление цепочки терминалов

Имеем правило с терминалом в цепочке $$S \to aB$$. Введём нетерминал \(U\). Получим:
\( S_0 \to S \\ S \to AA_1 \mid \color{red}{U}B \mid a \mid SA \mid AS \\ A \to B \mid S \\ A_1 \to SA \\ B \to b \\ \color{red}{U \to a} \)

  • Удаление цепных правил

Имеем следующие цепочки \( A \to B \to b \), \(A \to S \to \ldots\) и \(S_0 \to S \to \ldots\). Сворачивая их, получим:
\( S_0 \to AA_1 \mid UB \mid a \mid SA \mid AS \\ S \to AA_1 \mid UB \mid a \mid SA \mid AS \\ A \to b \mid AA_1 \mid UB \mid a \mid SA \mid AS \\ A_1 \to SA \\ U \to a \\ B \to b \)

Видим, что правила с нетерминалами $$S_0$$ и $$S$$ совпадают. Можем снова считать $$S$$ аксиомой и убрать первое правило (пункт добавления аксиомы выполнялся для общности алгоритма). Тогда окончательно, получаем:
\( S \to AA_1 \mid UB \mid a \mid SA \mid AS \\ A \to b \mid AA_1 \mid UB \mid a \mid SA \mid AS \\ A_1 \to SA \\ U \to a \\ B \to b \)

Задача для самостоятельного разбора

Привести к НФ следующую грамматику:
\( R \to XRX \mid S \\ X \to a \mid b \\ S \to aTb \mid bTa \\ T \to XTX \mid X \mid \varepsilon \)