shkolaw.in.ua 1 2

Теоретичні та методологічні основи програмування


УДК 004:512
В.М. Ільман, В.І. Шинкаренко
СТРУКТУРНИЙ ПІДХІД ДО ПРОБЛЕМИ
ВІДТВОРЕННЯ ГРАМАТИК

Для опису формальних граматик застосовано структурний підхід. Наведені деякі властивості граматич­них структур та їх підструктур. Розглянуто проблему відтворення формально граматичних структур за мовними підструктурами.

Вступ


Як правило, в теорії формальних граматик [1, 2] розглядаються питання властивостей граматик, породжених ними мов, належності граматичних конструкцій до цих мов, тобто застосовується підхід «від граматик до мовних конструкцій». Але в багатьох інтелектуальних предмет­них областях виникає потреба відтворення, за заданими окремими граматичними конструкціями формальної мови необхід­ної формальної граматики. Відомо, що ал­горитмічно така проблема частково розв’язується, при чому не однозначно. На даний момент існує досить широкий спектр алгоритмів відтворення формаль­них граматик за заданим набором констру­кцій деякої припустимої мови [3]. Вихо­дячи з цього виникає потреба доповнення формальних граматик атрибутами алгебри. Тому запропоновано до застосування ма­тематичний об’єкт формальна граматична структура [4, 5], в межах якої, для заданої предметної області, можливо створювати мовні конструкції проводити дослідження їх властивостей, визначати будову-струк­тури та інше.

У матеріалах даної роботи розгля­нуто формальні породжувальні граматики з позицій формальних структур і на цій основі запропоновано новий підхід до розв’язання задачі, відтворення формаль­них породжувальних граматик.

Задача відтворення формальних по­роджувальних граматик досить актуальна при дослідженні структур об’єктів, напри­клад, стилістики викладення матеріалу, розпізнавання структур графічних об’єктів [3, 6-8] тощо.

Граматичні структури та підструктури

Дамо спочатку декілька важливих та необхідних для подальшого викладення визначень конструктивних об’єктів, понять і позначень.

Розглянемо довільний термінальний алфавіт з порожнім елементом , та нетермінальний алфавіт і нехай їх сло­вник. Позначимо F(V) – вільна мова побу­дована, наприклад, за допомогою операції конкатенації над словником V. Введемо у розгляд сигнатуру як множину m-міст­них операцій , наприклад, операції заміщення , операції конкатенації та інших операцій і введемо [4, 5] наступний формальний об’єкт.

Визначення 1. Породжувальною фо­рмальною граматичною структурою фор­мальної граматики з сигнатурою і аксіо­матикою назвемо упорядковану трійку

, (1)

де аксіоматика може складатися з насту­пних форм: аксіом початку, аксіом виводу та інших аксіом і систем продукцій та їх властивостей. Аксіоматика має скі­нчену кількість аксиом та продукцій.


Введений формальний об’єкт (1) відтворює будову формальної граматики і з одного боку узагальнює під аксіомати­кою синтаксис, аксіоми та правила ви­воду формальних систем математики [9], а з іншого боку - задає специфікацію алгеб­раїчної структури, яка застосовується при семантичному дослідженні програм [10].

Зрозуміло, що введена структура дозволяє виводити за допомогою операції заміщення різні конструктивні ланцюжки над словником V і сигнатурою згі­дно її визначеної аксіоматики. Ланцю­жок зветься виведеним у формаль­ній структурі C, якщо його вивід починається з аксіоми початку і в ньому застосовані операції за правилами та аксі­омами аксіоматики. Так формальна струк­тура зі словником , сигна­турою та аксіоматикою:

дозволяє вивести ланцюжки

,

;

, і т. д.

Множина виведених у структурі C ланцюжків таких, що утво­рює формальну мову .


За визначенням 1 структура C є граматичною, тобто є повною у тому ро­зумінні, що, так як і в граматиках, всі сим­воли словника (окрім можливо порож­нього) обов’язково використовуються в аксіомах і продукція її аксіоматики. Тому, зрозуміло, що за заданою аксіоматикою однозначно відтворюється формальна гра­матична структура і її граматика, а також породжується певна формальна мова. В подальшому розглядатимуться тільки гра­матичні структури з одноелементною сиг­натурою заміщення і зі спрощеною аксіо­матикою: з аксіомами початку та виводу. Так для вище наведеної аксіоматики спро­щена – має вигляд:



за якою породжується формальна мова .

Очевидно, для структури (1) в осно­вному зберігаються результати отримані для формальних граматик, наприклад, у класі формально граматичних структур при введені конструктивних обмежень на продукції аксіоматики можливо виділити класи BC - структур і VC - структур, які відповідають контекстно залежним і кон­текстно вільним граматикам відповідно, при чому, VC - структура є частковим ви­падком BC - структури. Крім того для структур (1) можливо ввести поняття фун­кціональної еквівалентності.

Визначення 2. Дві граматичні струк­тури і функціонально еквівалентні (слабко), якщо вони породжують одну і ту ж мову, тобто .

Визначення 3. Структура C зветься нескороченою, якщо продукції і аксіоми її аксіоматики задовольняють властивості , де - дов­жина ланцюжка .


Визначення 4. Структура C зветься - вільною граматичною структурою, якщо її аксіоматика не містить у собі про­дукцій і аксіом типу .

Не складно довести, що в будь якому класі еквівалентності граматичних структур завжди існує нормальна струк­тура , тобто структура продукції і аксі­оми аксіоматики, якої мають властивість . А також, що у всякому класі еквівалентності з нескороченою од­нозначною структурою існує однозначна - вільна BC- граматична структура.

Але для формальних граматичних структур можливо встановити нові алгеб­раїчні результати, наприклад, структура (1) є універсальною відносно вільної мови F(V) у тому розумінні, що структура ви­значена на словникові і поро­джує множину ланцюжків L(V), по опера­ції заміщення за аксіоматикою , таку, що має місце ланцюг за включенням . Серед множини фор­мальних структур можливо виділити го­моморфні та ізоморфні структури. Так фо­рмальні структури і ізо­морфні, якщо для будь яких елементів і будь яких операцій , та форм аксіоматик , існує взаємно однозначне відобра­ження множини на множину і форм аксіоматики на форми аксіома­тики таке, що


.

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

Визначення 5. Структуру назвемо підструктурою структури , якщо викону­ються включення і - по спрощеній аксіоматиці, і скорочено це по­значимо . Підструктура є порож­ньою підструктурою, якщо вона породжує тільки порожню мову , тобто для підструктури задовольняється хоча б одна з умов


  1. ;

  2. ;

  3. ( і );

  4. аксіоматика не може поро­джувати ні одного ланцюжка мови .

Зауваження 1. Очевидно, наведене визначення порожньої підструктури за умовами 1) – 4) еквівалентні згідно визна­ченню 2.

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


Породжувальні, повні та утворюючі граматичні підструктури

Визначення 6. Підструктуру фор­мальної граматичної структури (1) назвемо породжувальною підструктурою, якщо існує вивід W(l) ланцюжка l у струк­турі , такий, що . Породжу­вальну підструктуру , в якій виво­диться тільки один ланцюжок фор­мальної мови граматичної структури C назвемо структурою ланцюжка l формаль­ної мови L(A).

Отже довільна підструктура грама­тичної структури C тоді і тільки тоді поро­джувальна, коли її аксіоматика містить у собі хоча б по одній аксіомі виводу та початку і сукупність продукцій, пов’язаних хоча б з одним виводом ланцюжка .

Так як під виводом W(l) ланцюжка розуміється упорядкована послідо­вність безпосередньо виведених у структурі проміжних ланцюжків [1, 2], то взагалі між структурою ланцюжка і його виводом існує тільки гомоморфне відношення, і тому вивід W(l) задає будову ланцюжка l.

Не складно бачити, що будь яка підструктура структури є частково уні­версальною відносно вільної мови , тобто і відносно мови .


Нехай і довільні підструк­тури структури C, під їх об’єднанням і пе­ретином будемо розуміти і , де - звичайні теоретико-множинні операції. Причому перетин вважається порожнім, якщо ї , або ( і ), тоді, справед­лива така теорема.



следующая страница >>