Головна

Поняття формальної граматики

  1.  I. 1. 1. Поняття про психологію
  2.  I. 1. 3. Поняття про свідомість
  3.  I. Поняття про мови і її функціях
  4.  I. Поняття про інформацію. Загальна характеристика процесів збору, передачі, обробки та накопичення інформації
  5.  I. Поняття про інформацію. Загальна характеристика процесів збору, передачі, обробки та накопичення інформації
  6.  I. Поняття патристики. Короткий огляд патріотичної традиції. 1 сторінка
  7.  I. Поняття патристики. Короткий огляд патріотичної традиції. 2 сторінка

формальна граматика - Це четвірка G = N, VT, P, S>, в якій

VN - нетермінальний словник (Безліч нетермінальних символів);

VT - термінальний словник (Множина термінальних символів);

P - безліч граматичних правил;

S I VN - початковий нетермінальний символ.

Мотузки - Мова, за допомогою якого описується мова:

:: = - Є за визначенням;

| - "Виключне або";

<...> - Всередині - один нетермінальний символ;

[] - Необов'язкова частина;

,- Кома - роздільник при перерахуванні.

приклад: Побудуємо граматику G1:

<Прог> :: = <оп> | <Оп>; <Прог>

<Оп> :: = <пров>: = <вир>

<Пров> :: = a | b | c

<Вир> :: = <пров> | <Пров> <зн> <вир>

<Зн> :: = + | - | * | /

V = VN E VT - узагальнений словник.

V * - ланцюжок символів (рядок, слово) з узагальненого словника;

V * N - ланцюжок символів (рядок, слово) з нетермінального словника;

V * T - ланцюжок символів (рядок, слово) з термінального словника.

e I V - порожній символ, Входить в узагальнений словник.

рядок a безпосередньо породжує рядок b і позначається: a ? b,

якщо a = vxw b = vyw і існує деякий правило p: x :: = y,

де v, w, I V *  , Х I VN, У = V * \ {E}

рядок a породжує рядок b і позначається a ? *  b, коли від рядка a можна перейти до рядка b за допомогою послідовності безпосередніх породжень.

Продовжуючи приклад:

<Прог> ? <оп>; <Прог> ? <оп>; <Оп> ? <пров>: = <вир>; <Оп> ? *

a: = b + c; c: = a + b - c;

Граматика, що використовує процедури (безпосереднього) породження - породжує граматика.

рядок b безпосередньо згортається У рядку a і позначається: a U b,

якщо a = vxw b = vyw і існує деякий правило p: x :: = y,

де v, w, I V *  , Х I VN, У = V * \ {E}

рядок b згортається У рядку a і позначається a * U b, коли від рядка b можна перейти до рядка a за допомогою послідовності безпосередніх згортання.

Граматика, що використовує процедури (безпосереднього) згортання -распознающая граматика.

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

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

L (G) = {x I V * N | S ? *  x}

Аналогічно можна визначити мову L через згортання.

L (G) = {x I V * N | S * U x}

Зауваження. Інший варіант метамови

замість :: = використовується стрілка ®, термінальні символи записуються маленькими (малими) літерами, а нетермінальні - великими (прописними) літерами.

Такий варіант мета мови частіше використовується в математичній літературі. Перший воліють використовувати в літературі для програмістів. Так що ми будемо користуватися і тим і іншим варіантам ...

 




 ядро графа |  Побудова Кліки. |  морфізм груп |  Група Клейна четвертого ступеня |  поняття алгоритму |  складність обчислень |  машини Тьюринга |  Нормальні алгорифм Маркова |  Нормальна схема преобразуемое |  рекурсивні функції |

© um.co.ua - учбові матеріали та реферати