Реферат на тему:
Формальні мови та їх завдання
1. Формальна мова та задача належності
Алфавітом називається скінченна множина символів. Позначатимемо його X.
Словом (фразою, або ланцюжком) у алфавіті X називається послідовність
символів із X. Множина всіх скінченних слів у алфавіті X позначається
X*. Зауважимо, що вона нескінченна. Вона містить порожнє слово –
послідовність довжиною 0, позначену буквою ? . Множину X*\{? } позначимо
X+, а слово вигляду ww? w, де слово w із X+ записано n разів – wn.
Вважатимемо, що w0 = ? .
Довільна підмножина множини X* називається формальною мовою. Далі в
цьому розділі вона буде називатися просто мовою.
Приклади
1. Множина всіх слів у алфавіті {a} позначається {a}* = {? , a, aa, aaa,
… } = { an | n ? 0 }. {an|n–непарне} позначає множину, або мову слів
непарної довжини в алфавіті {a}; обидві мови нескінченні.?
2. Ідентифікатор є послідовністю букв і цифр, що починається буквою.
Множина всіх ідентифікаторів у алфавіті X={a, b, 1} нескінченна. Якщо
записати їх за зростанням довжини, то початок буде таким: { a, b, a1,
aa, ab, b1, ba, bb, ? }.?
Задача перевірки, чи належить слово w мові L, називається задачею
належності, або проблемою слів. Як правило, множина L задається певним
скінченним описанням, що визначає не тільки її саму, а й структуру її
елементів.
Задача належності розв’язується найчастіше шляхом перевірки, чи має
слово відповідну структуру, тобто шляхом синтаксичного аналізу, або
розпізнавання. Наприклад, структура всіх можливих синтаксично правильних
Паскаль-програм визначається скінченною та відносно невеликою сукупністю
БНФ. Саме на її основі будуються синтаксичні аналізатори в трансляторах,
тобто програми аналізу синтаксичної правильності вхідних програм.
Формальні мови розглядатимуться далі як мови, задані саме скінченним
описом. Отже, головним у вивченні формальних мов стає засіб їх задання.
У розділі 10 ми вже познайомилися з одним із них – це були БНФ та їх
сукупності. Розглянемо ще деякі.
2. Регулярні операції, вирази та мови
Означимо регулярні операції над мовами: об’єднання, катенацію та
ітерацію. Нехай L1 , L2 , L позначають довільні мови в алфавіті X.
Вираз L1? L2 позначає об’єднання L1 і L2 – мову {w|w? L1 або w? L2}.
Наприклад, {a, ab}? {a, b, ba}={a, b, ab, ba}.
Катенацією слів v і w називається дописування w після v: vw. Вираз L1L2
позначає катенацію мов – мову {vw|v? L1, w? L2}. Так, за L1={a, bc},
L2={x, y} катенація L1L2={ax, bcx, ay, bcy}, за L1={a, ab}, L2={? , b}
катенація L1L2={a, ab, abb}.
Від катенації походить піднесення до степеня: L0={? }, Li=Li-1L за i>0.
Так, вираз {? , a, aa}2 задає мову {? , a, aa, aaa, aaaa}.
Вираз L* позначає ітерацію мови L – мову {wi|w? L за i? 0}, тобто {? }?
L? L2? ? . Зазначимо, що ітерація не подається жодним скінченним виразом
з операціями катенації та ? і тому не є похідною від них. Якщо в мові L
є непорожнє слово, то мова L* нескінченна. Наприклад, вираз {ab}* задає
мову {? ,ab,abab,ababab,? }, {a,b}{a,b,1}* – множину ідентифікаторів у
алфавіті {a, b, 1}.
Регулярні вирази й задані ними регулярні мови означимо індуктивно.
Вирази ? , ? та a при a? X є регулярними в алфавіті X і задають
відповідно регулярні мови ? , {? }, {a}. Якщо r1 і r2 – регулярні
вирази, що задають регулярні мови L1 і L2 , то вирази (r1), r1+r2, r1r2,
r1* є регулярними й задають відповідно регулярні мови L1, L1? L2, L1L2,
L1*.
Очевидно, що кожна скінченна мова є регулярною, оскільки задається
регулярним виразом як скінченне об’єднання одноелементних регулярних
мов.
Множина регулярних мов, заданих усіма можливими регулярними виразами в
алфавіті X, називається класом регулярних мов над X.
Регулярні операції застосовні до будь-яких мов, а не тільки до
регулярних. За означенням, застосування їх до регулярних мов породжує
регулярні мови.
Не всі мови є регулярними. Наприклад, “мова вкладених дужок”, задана БНФ
::= ( ) | ( ),
є множиною {(n)n|n>0}, яка не задається жодним скінченним регулярним
виразом (доведення можна знайти в [АУ]). Отже, розглянемо інші,
потужніші засоби задання мов.
3. Граматики Хомського
Граматикою Хомського називається четвірка G = (X, N, P, S). Тут
X – алфавіт означуваної мови, або множина термінальних символів
(терміналів).
N – множина позначень понять мови, тобто нетермінальних символів
(нетерміналів).
P – множина правил виведення (продукцій) вигляду v? w, де
v ? ( X ? N )* N ( X ? N )* , w ? ( X ? N )*
тобто правий ланцюжок є довільною послідовністю терміналів і
нетерміналів, а лівий містить принаймні один нетермінал.
S – початковий нетермінал із множини N, або позначення головного
поняття, яким позначаються слова мови.
Нетермінали записуються словами в дужках або великими латинськими
буквами. Термінали за необхідності часом беруться в апострофи. Як і в
мові БНФ, замість продукцій вигляду v? w1ww2 і v? w1w2 записується
продукція v? w1[w]w2, а замість продукцій v? w1u1w2 і v? w1u2w2 –
продукція v1? w1(u1|u2)w2 .
Приклад 3. Множину продукцій граматики
G1 =({ a, 1, 2 },
{ A, B, C, D },
{ A ? BC, A ? BD, A ? B, B ? a, C ? 1, D ? 2 },
A )
можна переписати у вигляді
{ A ? B [ C | D ], B ? a, C ? 1, D ? 2 }.?
Як бачимо, продукції граматики дуже схожі на БНФ як за формою, так і за
змістом – лише замість знака “::=” вживається “? “. Проте в лівій
частині їх продукцій може бути не поодинокий нетермінал, а цілий
ланцюжок, у якому обов’язково є нетермінал. За рахунок такого
узагальнення граматики виявляються більш потужним засобом задання мов,
ніж системи БНФ, тобто існують мови, які задаються граматиками, але не
задаються БНФ. Тепер опишемо спосіб, у який граматика G = (X, N, P, S)
задає мову.
1. На множині слів об’єднаного алфавіту (X? N)* означається відношення
безпосередньої виводимості, позначене знаком ? G (або ? , коли відомо,
якою саме є G):
v ? G w, якщо v = x1 u x2 , w = x1 y x2 , u ? y ? P.
При цьому кажуть, що w безпосередньо виводиться з v застосуванням
продукції u? y. Наприклад, у граматиці G1 із прикладу 21.3 BC? aC
застосуванням продукції B? a, aC? a1застосуванням C? 1.
2. На множині (X? N)* означається відношення виводимості, позначене ? *G
(або ? *, коли відомо, якою саме є G): v? *w, якщо v=w або існує
послідовність w1, w2, … , wn слів, де n? 1, така, що v? w1, w1? w2, … ,
wn-1? wn, wn=w. Так, у граматиці G1 BC? *a1, оскільки BC? aC, aC? a1.
Послідовність v? w1? w2? …? wn називається виведенням wn із v, а n –
довжиною виведення. Інколи довжину записують замість ‘*’ таким чином: v?
nw, наприклад, BC ? 2a1.
3. Якщо S? G*w, то послідовність S? …? w називається виведенням слова w
у граматиці G, а слово w – вивідним. Так, слова A, BC, aC, a1 вивідні в
граматиці G1.
4. Вивідні слова в алфавіті X називаються породжуваними, а множина їх
усіх – мовою, що задається (породжується) граматикою G: L(G) = {w | w?
X* та S ? * w }.
Приклади
4. Граматика G1 із прикладу 21.3 задає мову { a, a1, a2 }.?
5. Граматика
G2 = ( { a, …, z, 0, …, 9 }, { I, L, D },
{ I ? L | IL | ID, L ? a | … | z, D ? 0 | … | 9 },
I )
породжує множину ідентифікаторів.?
6. Граматика G3 = ( { (, ) }, { S }, { S ? ? | ( S ) }, S ) задає
множину “вкладених дужок” { (n)n | n ? 0 }.?
7. Граматика
G4 = ( { a, b, c }, { S, A, B, C},
{ S ? aSBC | abC, CB ? BC, bB ? bb, bC ? bc, cC ? cc },
S )
визначає мову { anbncn | n ? 1 }.?
Граматики називаються еквівалентними, якщо задають ту саму мову.
Наприклад, граматика
( { a, 1, 2 }, { A }, { A ? a [ 1 | 2 ] }, A )
еквівалентна граматиці G1, граматика
( {a, …, z, 0, …, 9}, {I, C}, {I ? (a|…|z)C, C ? ? |C(a |…|z|0|…|9)}, I
)
– граматиці G2.
Є два види граматик з продукціями обмеженого вигляду, якими задаються
регулярні мови, – це праволінійні та ліволінійні граматики.
Праволінійною (ліволінійною) називається граматика, всі продукції якої
мають вигляд A? w або A? wB (відповідно, A? w або A? Bw), де A, B –
нетермінали, w? X*. Усі можливі праволінійні та ліволінійні граматики з
термінальним алфавітом X породжують в точності клас регулярних мов над
X. Це доводиться, наприклад, в [АУ].
Нашли опечатку? Выделите и нажмите CTRL+Enter
