68832

Загальна форма означення мови

Лекция

Информатика, кибернетика и программирование

Задати синтаксис це означає задати алфавіт та множину форм усіх речень мови семантика визначає смислове значення усіх цих речень. Існує декілька формальних засобів опису синтаксису мови. Оскільки синтаксис мови пов’язаний з множиною речень рядків символів необхідно домовитись про позначення...

Украинкский

2014-09-26

123.5 KB

2 чел.

Лекція 2

Загальна форма означення мови

Означення мови складається з завдання її синтаксису та семантики. Задати синтаксис - це означає задати алфавіт та множину форм усіх речень мови, семантика визначає смислове значення усіх цих речень. Існує декілька формальних засобів опису синтаксису мови. Один з них (БНФ) розглядався у попередній лекції. Формальні засоби означення семантики ґрунтуються на введенні властивостей (атрибутів) символів граматики і правил обчислення значень цих атрибутів. Оскільки синтаксис мови пов'язаний з множиною речень (рядків символів), необхідно домовитись про позначення таких множин та означити операції на них.

Регулярні множини та регулярні вирази

Нехай   = {a1, a2, … , an} – множина символів, яку назвемо алфавітом.

Означення 2.1. Мовою над алфавітом  називається множина рядків (ланцюжків або послідовностей) символів, що належать  .

Наприклад, коли   = {a, b, с}, то L1 = {aa, bc, abc} є мова, а L2 = {ab, abb, aac} - інша мова. Мова може мати і нескінчену кількість рядків, хоча алфавіт містить тільки скінчену кількість символів. Надалі будемо вважати, що рядок символів - це синонім речення мови.

Означення 2.2. Конкатенацією (зчепленням або добутком) мов L1 та L2 називається мова L1L2, що задовольняє умові 

L1L2 = {xy | x  L1 & y  L2}.

Наприклад, якщо L1 = {a, b}, L2 = {c, d}, то L1L2 = {ac, ad, bc, bd}. Для позначення конкатенації однакових мов будемо застосовувати символ степеня. Наприклад, L1L1 = L12 = {aa, ab, ba, bb}. Будемо вважати, що

L0 = ,

де   - пустий рядок, або рядок, що не містить жодного символу.

Означення 2.3. Об’єднанням мов  L1  та  L2  називається мова  L1  L2, що містить усі рядки, які належать хоча б до однієї з мов L1 чи L2 

L1        L2 = {x | x     L1  або  x     L 2}.

Означення 2.4. Ітерацією мови L називається мова L*, що задовольняє умові 

L* =           Ln.

Позитивна ітерація мови  L+:

L+ =            Ln.

 

Регулярна множина над алфавітом означається рекурсивно таким чином

(1) пуста множина рядків   - регулярна множина над  ;

(2) {} - регулярна множина над  ;

(3) {x} - регулярна множина над ,  x  ;

(4) якщо P та Q регулярні множини над , то  P    Q, PQ, P+, Q+ - регулярні множини над  .

Регулярний вираз - це запис, що позначає регулярну множину. Наприклад, PQ - це регулярний вираз, що позначає конкатенацію регулярних множин P та Q. У регулярних виразах операцію об’єднання позначають символом «+», використовують дужки «(» та «)» для зміни порядку операцій, пусту множину  рядків позначають як 0, а множину {} - як 1.

Означення 2.5. Регулярною алгеброю називається множина рядків символів скінченого алфавіту, на якій визначені три операції: об’єднання, конкатенація та ітерація, що задовольняють аксіомам:

  1.  A + B = B + A; 2) A + (B + С) = (A + B) + С; 3) A + A = A; 4) A + 0 = A;

5) A(BС) = (AB)С; 6) A1 = A = 1A; 7) A0 = 0 = 0A; 8) A(B + С) = AB + AC;

9) (A + B)С = AB + BС; 10) 0* = 1; 11) A* = A + A*; 12) (A*)* = A*.

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

L = {ambn | m, n   0}

Означення граматики

Тепер повернемося до граматики парних чисел, розглянутої у минулій лекції. По-перше, її можна використати для визначення, чи є подана послідовність цифр (літер) парним числом. Наприклад, перевіримо послідовність 138. Літера 1 є за формулою (1) ненульовою цифрою і тому за формулою (4) - початком. Літера 3 - цифра (формула(1)), отже, 13 - початок (формула (4)). Нарешті, 8 - парна цифра (формула (3)), і з формули (5) випливає, що 138 - парне число.

По-друге, подану БНФ можна використати для написання (або, кажуть, породження) довільного парного числа. Наприклад, для того щоб одержати парне число, згідно з формулою (5) треба взяти парну цифру або початок, після якого записується парна цифра. Зупинимося на другому варіанті та одержимо послідовність 

<початок><парна цифра>.

Можна взяти одну з п’яти цифр, вказаних у формулі (3), і тоді одержати, наприклад,

<початок> 6.

Цифра 6 ніде у лівій частині формул не зустрічається. Тому за формулою (4) перетворюємо метасимвол <початок>, наприклад, так

<початок><цифра> 6.

Знову застосувавши формулу (4), можемо одержати

<ненульова цифра><цифра> 6.

Подальше послідовне застосування формул (2) та (1) дає, наприклад, парне число 106.

 Показуючи можливість переходу від лівої частини формули до правої символом «    » та використовуючи великі латинські букви для позначення власно метасимволів: A - <парне число>, B - <початок>, С - <парна цифра>, D -<цифра>, Е - <ненульова цифра>, - одержимо опис граматики парних чисел у формі 

A C|BC

B  E|BD

C   012141618

D   0|E

E   1|2|3|4|5|6|7|8|9.

З означення БНФ випливає, що від поданої форми можна перейти до еквівалентної, що не містить символів « | ». Наприклад, формулу для А можна перетворити у дві формули

А      С

А      ВС.

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

Розглянемо граматику мови

L = {0 n1n |  n  0},

що містить усі послідовності, складені з однакової кількості нулів та одиниць таким чином, що спочатку записуються нулі, а потім - одиниці. Продукції цієї граматики мають вигляд 

1. S      0S1

2. S      .

Для того, щоб одержати деяке речення треба до символу S застосувати декілька разів правило 1, а потім - правило 2. Зрозуміло, що застосування правила 2 зупиняє процес. Наприклад,

S  0S1  00S11 000S111 000111.

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

Означення 2.6. Граматикою G називається алгебраїчна структура, що являє собою упорядковану четвірку (N, T , P, S), де

а) N та T - непусті скінчені алфавіти відповідно нетермінальних та термінальних символів такі, що N  T = ; об’єднання цих алфавітів будемо позначати символом  V  і називати словником граматики G: V = N  T;

б) P - скінчена множина продукцій вигляду

                 ,                                                                             

де       V* N V*,    V*, і тому  P  V* N V* x V*;

в) S  N  і називається початковим символом, джерелом або аксіомою.

Якщо      P, і ,   V*, то кажуть, що рядки    та    задовольняють відношенню безпосередньої виводимості, і записують це так

    

Транзитивне замикання цього відношення позначають символом +, а рефлексивно-транзитивне - *. Якщо для рядків та має місце   + , то кажуть, що    нетривіально виводиться з  .

Приклади формальних граматик

 Розглянемо граматику G1 мови L1, що описується виразом

L1 = {a m b n | m, n  0}.

Ця граматика має вигляд

G1 = ({S, A, B}, {a, b}, P1, S}).

Елементами P1 є правила

1. S  AB

2. A  aA

3. A  

4. B  bB

5. B  

Вивід рядка aaabb:

 S  AB  aAB  aaAB  aaaAB  aaaB  aaabB  aaabbB  aaabb.

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

Часто речення мови можна породжувати за допомогою різних граматик. Дві граматики Gi та Gj, що породжують одну і ту ж саму мову, тобто L(Gi) = L(Gj), називають еквівалентними. Наприклад, розглянутій вище граматиці G1 еквівалентна граматика G2 = ({S, Y}, {a, b}, P2, S), де P2:

1. S  aS             5. Y  b

2. S  a              6. Y  bY

3. S  b              7. S  

4. S  bY

При створенні компілятора одна з еквівалентних граматик може виявитись зручнішою за іншу.

У розглянутих вище прикладах ліві частини правил складалися з одного нетерміналу. Але означення граматики цього зовсім не потребує. Як приклад граматики, що містить правила, у лівій частині яких знаходиться більше одного символа, розглянемо граматику G3 для породження мови L3:

L3 = {ak | k = 2n  &  n  0}.

G3 = ({S, M, Q, R}, {a}, P3, S),

де P3:

1. S  QMQ                4. RQ  MMQ

2. QM  QR                 5. M  a

3. RM  MMR             6. Q  .

Послідовне виконання правил 2, 3 (можливо багаторазове) та 4 призводить до подвоєння символів M. Причому, почавши виконувати таку послідовність кроків виводу, не можна зупинитися у довільний момент, тому що сентенціальна форма буде містити символ R. А у цьому випадку перейти до рядка, що містить тільки термінали, за допомогою правил 5 та 6 нема можливості. Тому мова, що визначається граматикою G3, дійсно містить тільки рядки s, довжина яких дорівнює цілому невід’ємному степеню 2. Це позначається так | s | = 2k , k    0.

Приклад виводу:

S  QMQ  QRQ  QMMQ  QRMQ  QMMRQ  QMMMMQ + aaaa.

Класифікація Хомського

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

Якщо на продукції граматики не накладаються ніякі обмеження, то така граматика називається граматикою Хомського типу 0.

Граматика G = (N, T, P, S) називається граматикою Хомського типу 1 або контекстно-залежною граматикою (КЗГ), якщо усі елементи P мають вигляд 

  ,

де   = 1A2,   =  12,  1, 2  V*, A  N,    V+.

У цьому означенні рядки  1  та  2  можна розглядати як контекст (оточення), у якому символ A може бути замінений на  . Звідси походить назва граматики.  

Якщо усі елементи P мають вигляд

A  ,

де  A  N,    V+,

то граматику називають граматикою Хомського типу 2.

Нарешті, якщо P складається тільки з продукцій виду

 A  ,

де  A  N та   {T  TN} (тобто права частина є або термінал, або термінал, за яким прямує один нетермінал), то кажуть, що G - це граматика Хомського типу 3.

Якщо припустити, що граматики Хомського типу 2 та 3 можуть містити -продукцію вигляду 

S  ,

де   - пустий рядок, то утворюються відповідно контекстно-вільна та регулярна граматики.

Ієрархія граматик природним чином переноситься на ієрархію мов. Наприклад, якщо мову можна генерувати за допомогою граматики типу 2, то її називають мовою типу 2.

Характерна властивість контекстно-залежної мови

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

  

задовольняють умові

1   |  |       |  | .          

 Доведення. Якщо L контекстно-залежна мова, то існує контекстно-залежна граматика G = (N, T, P, S), що породжує її (L = L(G)), і всі продукції G мають вигляд 

1A2  12,

де  A  N,     V+,  1, 2  V*.

Тоді можна записати

| 1 A 2 | = | 1 | + | A | + | 2 | = | 1 | + 1 + | 2 |  1,

| 12 | = | 1 | + |  | + | 2 |  | 1 | + 1 + | 2 | = | 1 A 2 | ,

і тому

1 | 1 A 2 |  | 1 2 |.

Цим доведено необхідність.

Тепер доведемо достатність. Нехай G = (N, T, P, S)- граматика, усі продукції якої

  

задовольняють умові

1 |  | |  |.

Побудуємо граматику R, еквівалентну граматиці G, з продукціями вигляду 

1A2  12 

Продукції G мають вигляд

1) A  1n;

2)  1m  1k ,   де  m  k,  і   A  N,  i, i  V.

В усіх продукціях замінимо кожний елемент ai  T новим нетерміналом Ai і включимо продукцію  Ai     ai  у  R. Продукції типу 1) також включимо в R, оскільки вони мають правильну форму, а кожну продукцію типу 2), що має вигляд 

W1Wn   Y1Yq,  n  q,

перетворимо в n + q нових продукцій:

W1 … Wn  X1W2 … Wn,

X1W2 … Wn  X1 X2W3 … Wn,

…………….

                                    X1… X n-2Wn-1Wn  X1 … X n-1Wn ,

                                             X1… X n-1Wn  X1 … X n-1Xn X n+1Xq,

                                                    X1… X q  Y1X2 … Xq ,

                                               Y1 X2… X q   Y1Y2X3 … Xq ,

…………….

                                             Y1 … Yq-1 X q  Y1 … Yq .

Усі ці продукції мають вигляд      1A2  12,  і R еквівалентна G.


 

А также другие работы, которые могут Вас заинтересовать

67774. Расчет требуемой степени очистки производственных стоков 74.37 KB
  Оценка требуемой очистки сточных вод СВ которая позволяет сделать обоснованный выбор типа и мощности очистных сооружений вариантов размещения оголовков выпуска у берега или в стрежень и их конструктивных особенностей. Участок водоема от места выпуска стоков условно делят на зоны: 1 начального разбавления...
67775. Преобразования Фурье 101.5 KB
  ДПФ определяет спектр дискретной периодичной функции x(t). ДПФ – обратимая операция отображения временных рядов в область частот. Свойства ДПФ аналогичны свойствам интегрального преобразования Фурье. ДПФ определяет линейчатый спектр периодичной дискретизации функции времени, а обратное дискретное...
67777. Изучение счетчика Гейгера-Мюллера 168.01 KB
  На рабочей точке рассчитать истинное количество частиц попавших в счетчик с учетом мертвого времени исходя из τ=104 сек. Каковы основные характеристики счетчиков числа частиц В чем отличие счетчиков Гейгера-Мюллера от других счетчиков Что называют счетной характеристикой счетчика...
67778. МАТЕМАТИЧЕСКАЯ ОБРАБОТКА РЕЗУЛЬТАТОВ ИЗМЕРЕНИЙ 47.02 KB
  Цель работы: Ознакомиться со статистическим характером явлений, рассматриваемых в ядерной физике; изучить законы, которым подчиняется распределение случайных величин; классификацию случайных и систематических ошибок; конкретное приложения изученных закономерностей для оценки ошибок измерения.
67779. ОПРЕДЕЛЕНИЕ АКТИВНОСТИ ИСТОЧНИКОВ БЕТТА-ИЗЛУЧЕНИЯ 194.6 KB
  Вычислить по формуле 2 поправку ω учитывающую взаимное расположение счётчика и источника β частиц. Вычислить по формуле 4 поправку f учитывающую поглощение β частиц. Найти поправку q на отражение β частиц от подложки по графику рис. Взаимодействие β частиц с веществом.