Формальні граматики

Матеріал з Вікіпедії — вільної енциклопедії.

Зміст

1 Формальні граматики
2 Класифікація граматик
3 Використання формальних граматик
4 Дивіться також

[ред.] Формальні граматики

Формальні граматики були введені американським вченим, математиком та філософом, Н.Хомським в 50-тих роках ХХ сторіччя.

[ред.] Поняття алфавіту

Алфавіт - це скінченна множина символів. ε - порожній ланцюжок, слово, послідовність. Алфавітом є об'єднання алфавітів, перетин, різниця алфавітів. Нехай Т - алфавіт, тоді:

Т⁺ - множина усіх можливих послідовностей, що складені з елемнтів цього алфавіту крім порожньої послідовності ε.
Т* - множина усіх можливих послідовностей, що складені з елементів цього алфавіту, будь-якої довжини. Отже: $T^* = T^+ \cup \{ \varepsilon \}$
Т^k - множина усіх можливих послідовностей,що складені з елементів цього алфавіту, довжини не більше k.

Мова в алфавіті Т це множина ланцюжків кінцевої довжини в цьому алфавіті. Зрозуміло, що кожна мова в алфавіті Т є підмножиною множини Т*.

[ред.] Формальна граматика

Формальна граматика - це четвірка $\boldsymbol{G = \{N,T,P,S\}}$ . Де:

Т - алфавіт термінальних символів, терміналів (від англ. terminate - завершетись);
N - алфавіт нетермінальних символів, нетерміналів. $\to, \Rightarrow, \Rightarrow^* \notin T \cup N$ ;
S - аксіома, спеціально виділений нетермінальний символ.

$\mbox{S}\in\mbox{N}$

P - кінцева підмножина множини $(T \cup N)^+ \times(T \cup N)^*$ . Інколи визначають так: $\alpha \in (T \cup N)^*\times N \times(T \cup N)^*, \beta \in (T \cup N)^*$ .

Елемент (α,β) з множини Р називається правилом виводу і записується у вигляді $\alpha \to \beta$ . Таким чином, ліва частина правила не може бути порожньою. Правила з однаковою лівою частиною записують: $\alpha \to \beta_1 \mid \beta_2 \mid ...\mid \beta_n$ , $β i, i = 1,2,..,n$ - називаются альтернативами правила виводу з ланцюжка $α$ .

[ред.] Виведення в формальних граматиках

Ланцюжок $\beta \in (T \cup N)^*$ назвемо безпосередньо виведеним з ланцюжка $\alpha \in (T \cup N)^+$ в граматиці $G = {T, N, S, P}$ (позначається $\alpha \Rightarrow \beta$ ), якщо $\alpha = \xi_1 \gamma \xi_2 , \beta = \xi_1 \delta \xi_2: \xi_1 ,\xi_2 , \delta \in (T \cup N)^* , \gamma \in (T \cup N)^+ , \gamma \to \delta \in P$ .

Ланцюжок $\beta \in (T \cup N)^*$ назвемо виведеним з ланцюжка $\alpha \in (T \cup N)^+$ в граматиці $G = {T, N, S, P}$ (позначається $\alpha \Rightarrow^* \beta$ ), якщо

$\exists \gamma_0,\gamma_1,...,\gamma_n, n\ge 0 : \alpha = \gamma_0 \Rightarrow \gamma_1 \Rightarrow ...\Rightarrow \gamma_n = \beta$

Термінальний рядок називається правильним(або сентенціальною формою) відносно граматики G якщо він виводиться з аксіоми цієї граматики.

[ред.] Формальні мови

Формальна мова породжена граматикою G - це множина термінальних рядочків, що виводяться з аксіоми, тобто множина усіх правильних рядків.

$L(G) = \{\alpha \in T^*\mid S \Rightarrow^* \alpha \}$

З іношого боку, множина термінальних рядків, таких, що вони можуть бути виведені в граматиці G, називається мовою, що може бути розпізнана в даній граматиці, або допускається даною граматикою.

Граматики G₁ та G₂ називаються еквівалентними, якщо $L (G 1) = L (G 2)$ .
Граматики G₁ та G₂ називаються майже еквівалентними, якщо $L(G_1) \cup \{\varepsilon\} = L(G_2) \cup \{\varepsilon\}$ , тобто мови, ними породжувані, відрізняються не більш ніж на ε.

Граматика може бути породжуючою та розпізнавальною, це залежить від "напрямку" застосування правил. Для породжучих граматик виведення починається з аксіоми і закінчується термінальним рядком (рядком, що скаладається тільки з терміналів). А розпізнавальні аналізують вхідний термінальний рядок на правильність, чи можна такий рядок вивести в цій граматиці. Коротоше кажучи - породжуючі це "згори вниз", а розпізнавальні - "знизу вгору". Остання задача є більш практичною і гострою.

[ред.] Класифікація граматик

Хомський також запропонував класифікацію граматик. Він виділив чотири типи граматик.

[ред.] Класифікація за Хомським

Тип 0. Граматики Типу 0

це найбільш загальний клас граматик. На правила не накладаються ніяких обмежень, окрім зазначених у візначенні. Вони еквівалентні Машині Тюринга. Доведено існування мов, які породжуються граматиками типу 0, але не граматиками типу 1, але невідомі прості приклади таких мов.

Тип 1. Граматики Типу 1

нескорочуюча або контекстно-залежна(КЗ) граматика. Вибір означення не впливає на множину мов, породжуваних граматиками цього класу, оскільки доведено, що множина мов, породжуваних граматиками, що не укорочують, збігається із множиною мов, породжуваних КЗ-граматиками.

Нескорочуючі граматики. Всі правила мають вигляд

$\alpha\to\beta$

$\alpha \in (T \cup N)^+, \beta \in (T \cup N)^*$

$|\alpha|\le |\beta|$

де $| α |$ означає кількість символів у рядку $α$ .
Контекстно-залежні граматики. Всі правила мають вигляд:

$\alpha\to\beta$

$\alpha = \xi_1A\xi_2, \beta = \xi_1\gamma\xi_2: A \in N, \gamma \in (T \cup N)^+, \xi_1,\xi_2 \in (T \cup N)^*$

Тип 2. Граматики Типу 2. Контекстновільні граматики(КВ)

Всі правила мають вигляд

$\alpha\to\beta$

$\alpha \in N, \beta \in (T \cup N)^*$

Тобто в усіх правилах цього виду зліва стоїть тільки один нетермінал. Тому вони і контекстно вільні, бо на використання правила для даного нетерміналу не впливають символи, що оточують його. Ці символи називають контекстом.

Тип 3. Граматики Типу 3. Регулярні граматики. А-граматики

можно визначити як праволінійну або ліволінійну граматику, або як змішану. Також ці мови називають скінченно-автоматними, бо вони еквівалентні скінченним автоматам, тобто клас мов, що породжуються граматиками типу 3, співпадає з класом мов, які розпізнаються скінченими автоматами. Також ці граматики є основою регулярних виразів.

Праволінійна граматика. Всі правила мають вигляд:

$\alpha\to\beta$

$\alpha \to \omega\beta, \beta\in N, \omega \in T^*$

або

$\alpha \to \omega, \omega \in T^*$
Ліволінійна граматика. Всі правила мають вигляд:

$\alpha\to\beta$

$\alpha \to \beta\omega, \beta\in N, \omega \in T^*$

або

$\alpha \to \omega, \omega \in T^*$

Доведено, що праволінійні та ліволінійні граматики еквівалентні, і існує алгоритм для переведення правил граматики одного типу в інший тип.

[ред.] Співвідношення між типами граматик

Будь-які граматики типу 3 є грамтиками типу 2.
Будь-які КВ-граматики є грамтиками типу 1(КЗ або неукорочуючі), з точністью до ε.
Будь-які граматики типу 1 є грамтиками типу 0.

Мова L(G) є мовою типу k, якщо її можна описати граматикою типу k.

[ред.] Співвідношення між типами мов

кожна регулярна мова є КВ-мовою, але існують КВ- мови, що не є регулярними (наприклад, $L = \{a^nb^n \mid n>0\}$ );
кожна КВ- мова є КЗ- мовою, але існують КЗ-мови, що не є КВ-мовами ( наприклад, $L = \{a^nb^nc^n \mid n>0\}$ );
кожна КЗ-мова є мовою типу 0.

Варто підкреслити, що якщо мова задана граматикою типу k, то це не означає, що не існує граматики типу k' (k'>k), що описує ту ж мову. Тому, коли говорять про мову типу k, звичайно мають на увазі максимально можливе k.

[ред.] Використання формальних граматик

Формальні граматики це дуже потужній математичний інструмент, який використовується в математичній та комп'ютерній лінгвістиці, описі мов програмування, розробці компіляторів в теорії програмування. Найбільш вживаними є КВ-граматики і регулярні, бо їх найлегше описати алгоритмічно.

Сама по собі концепція формальних граматик доволі гнучка, тому не дивно, що з'явилося багато інших інструментів, що розширють використання та потужність КВ-граматик і граматик третього типу. Наприклад, атрибутні граматики, LL-k граматики, скінченні автомати, регулярні вирази та множини.

[ред.] Дивіться також

Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.

Формальні граматики

Матеріал з Вікіпедії — вільної енциклопедії.

Зміст

[ред.] Формальні граматики

[ред.] Поняття алфавіту

[ред.] Формальна граматика

[ред.] Виведення в формальних граматиках

[ред.] Формальні мови

[ред.] Класифікація граматик

[ред.] Класифікація за Хомським

[ред.] Співвідношення між типами граматик

[ред.] Співвідношення між типами мов

[ред.] Використання формальних граматик

[ред.] Дивіться також

Перегляди

Особисті інструменти

Навігація

Участь

Пошук

Панель інструментів

Іншими мовами