Структурний підхід до проблеми відтворення граматик

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

Full description

Saved in:

Bibliographic Details
Date:	2007
Main Authors:	Ільман, В.М., Шинкаренко, В.І.
Format:	Article
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2007
Subjects:	Теоретичні та методологічні основи програмування
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/276
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Структурний підхід до проблеми відтворення граматик / В.М. Ільман, В.І. Шинкаренко // Пробл. програмув. — 2007. — N 1. — С. 5-16. — Бібліогр.: 11 назв. — укp.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-276
record_format	dspace
spelling	Ільман, В.М. Шинкаренко, В.І. 2008-02-22T17:16:33Z 2008-02-22T17:16:33Z 2007 Структурний підхід до проблеми відтворення граматик / В.М. Ільман, В.І. Шинкаренко // Пробл. програмув. — 2007. — N 1. — С. 5-16. — Бібліогр.: 11 назв. — укp. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/276 004:512 Для опису формальних граматик застосовано структурний підхід. Наведено деякі властивості граматичних структур та їх підструктур. Розглянуто проблему відтворення формально граматичних структур за мовними підструктурами. uk Інститут програмних систем НАН України Теоретичні та методологічні основи програмування Структурний підхід до проблеми відтворення граматик Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Структурний підхід до проблеми відтворення граматик
spellingShingle	Структурний підхід до проблеми відтворення граматик Ільман, В.М. Шинкаренко, В.І. Теоретичні та методологічні основи програмування
title_short	Структурний підхід до проблеми відтворення граматик
title_full	Структурний підхід до проблеми відтворення граматик
title_fullStr	Структурний підхід до проблеми відтворення граматик
title_full_unstemmed	Структурний підхід до проблеми відтворення граматик
title_sort	структурний підхід до проблеми відтворення граматик
author	Ільман, В.М. Шинкаренко, В.І.
author_facet	Ільман, В.М. Шинкаренко, В.І.
topic	Теоретичні та методологічні основи програмування
topic_facet	Теоретичні та методологічні основи програмування
publishDate	2007
language	Ukrainian
publisher	Інститут програмних систем НАН України
format	Article
description	Для опису формальних граматик застосовано структурний підхід. Наведено деякі властивості граматичних структур та їх підструктур. Розглянуто проблему відтворення формально граматичних структур за мовними підструктурами.
issn	1727-4907
url	https://nasplib.isofts.kiev.ua/handle/123456789/276
citation_txt	Структурний підхід до проблеми відтворення граматик / В.М. Ільман, В.І. Шинкаренко // Пробл. програмув. — 2007. — N 1. — С. 5-16. — Бібліогр.: 11 назв. — укp.
work_keys_str_mv	AT ílʹmanvm strukturniipídhíddoproblemivídtvorennâgramatik AT šinkarenkoví strukturniipídhíddoproblemivídtvorennâgramatik
first_indexed	2025-11-24T11:50:27Z
last_indexed	2025-11-24T11:50:27Z
_version_	1850846392864473088
fulltext	Теоретичні та методологічні основи програмування © В.М. Ільман, В.І. Шинкаренко, 2007 ISSN 1727-4907. Проблеми програмування. 2007. № 1 5 УДК 004:512 В.М. Ільман, В.І. Шинкаренко СТРУКТУРНИЙ ПІДХІД ДО ПРОБЛЕМИ ВІДТВОРЕННЯ ГРАМАТИК Для опису формальних граматик застосовано структурний підхід. Наведені деякі властивості граматич- них структур та їх підструктур. Розглянуто проблему відтворення формально граматичних структур за мовними підструктурами. Вступ Як правило, в теорії формальних граматик [1, 2] розглядаються питання властивостей граматик, породжених ними мов, належності граматичних конструкцій до цих мов, тобто застосовується підхід «від граматик до мовних конструкцій». Але в багатьох інтелектуальних предмет- них областях виникає потреба відтворення, за заданими окремими граматичними конструкціями формальної мови необхід- ної формальної граматики. Відомо, що ал- горитмічно така проблема частково розв’язується, при чому не однозначно. На даний момент існує досить широкий спектр алгоритмів відтворення формаль- них граматик за заданим набором констру- кцій деякої припустимої мови [3]. Вихо- дячи з цього виникає потреба доповнення формальних граматик атрибутами алгебри. Тому запропоновано до застосування ма- тематичний об’єкт формальна граматична структура [4, 5], в межах якої, для заданої предметної області, можливо створювати мовні конструкції проводити дослідження їх властивостей, визначати будову-струк- тури та інше. У матеріалах даної роботи розгля- нуто формальні породжувальні граматики з позицій формальних структур і на цій основі запропоновано новий підхід до розв’язання задачі, відтворення формаль- них породжувальних граматик. Задача відтворення формальних по- роджувальних граматик досить актуальна при дослідженні структур об’єктів, напри- клад, стилістики викладення матеріалу, розпізнавання структур графічних об’єктів [3, 6-8] тощо. Граматичні структури та підструктури Дамо спочатку декілька важливих та необхідних для подальшого викладення визначень конструктивних об’єктів, понять і позначень. Розглянемо довільний термінальний алфавіт },,,{ 21 naaaA Kο= з порожнім елементом ο , та нетермінальний алфавіт },,{ 21 kB ααα K= і нехай BAV U= їх сло- вник. Позначимо F(V) – вільна мова побу- дована, наприклад, за допомогою операції конкатенації над словником V. Введемо у розгляд сигнатуру Σ як множину m-міст- них операцій )( m∗ , наприклад, операції заміщення )( 2→ , операції конкатенації )( 2×__][ та інших операцій і введемо [4, 5] наступний формальний об’єкт. Визначення 1. Породжувальною фо- рмальною граматичною структурою фор- мальної граматики з сигнатурою Σ і аксіо- матикою Λ назвемо упорядковану трійку ΛΣ= ,,VC , (1) де аксіоматика Λ може складатися з на- ступних форм: аксіом початку, аксіом ви- воду та інших аксіом і систем продукцій та їх властивостей. Аксіоматика Λ має скі- нчену кількість аксиом та продукцій. Введений формальний об’єкт (1) відтворює будову формальної граматики і з одного боку узагальнює під аксіомати- кою Λ синтаксис, аксіоми та правила ви- воду формальних систем математики [9], а з іншого боку - задає специфікацію алгеб- раїчної структури, яка застосовується при семантичному дослідженні програм [10]. Зрозуміло, що введена структура дозволяє виводити за допомогою операції заміщення різні конструктивні ланцюжки над словником V і сигнатурою }{\ 2→Σ Теоретичні та методологічні основи програмування 6 згідно її визначеної аксіоматики. Ланцю- жок )(VFl ∈ зветься виведеним у форма- льній структурі C, якщо його вивід почи- нається з аксіоми початку і в ньому засто- совані операції за правилами та аксіомами аксіоматики. Так формальна структура зі словником },{},{ ασUbaV = , сигнатурою },{ 22 ×→=Σ __][ та аксіоматикою: дозволяє вивести ланцюжки )(VFaa ∈=×__][ αα , )(AFabba ∈=×__][ ; )(VFabba ∈=×× ____ ][][ αα , )(AFabbbba ∈=×× ____ ][][ і т. д. Множина виведених у структурі C ланцюжків }{ il таких, що )(AFli ∈ утво- рює формальну мову )()( AFAL ⊂ . За визначенням 1 структура C є граматичною, тобто є повною у тому ро- зумінні, що, так як і в граматиках, всі сим- воли словника (окрім можливо порож- нього) обов’язково використовуються в аксіомах і продукція її аксіоматики. Тому, зрозуміло, що за заданою аксіоматикою однозначно відтворюється формальна гра- матична структура і її граматика, а також породжується певна формальна мова. В подальшому розглядатимуться тільки гра- матичні структури з одноелементною сиг- натурою заміщення і зі спрощеною аксіо- матикою: з аксіомами початку та виводу. Так для вище наведеної аксіоматики спро- щена – має вигляд:      → −→ −→ =Λ αα ασ α b a b ,початкуаксіома ,виводуаксіома за якою породжується формальна мова };{)( NkabAL k ∈= . Очевидно, для структури (1) в осно- вному зберігаються результати отримані для формальних граматик, наприклад, у класі формально граматичних структур при введені конструктивних обмежень на продукції аксіоматики можливо виділити класи BC - структур і VC - структур, які відповідають контекстно залежним і кон- текстно вільним граматикам відповідно, при чому, VC - структура є частковим ви- падком BC - структури. Крім того для структур (1) можливо ввести поняття фун- кціональної еквівалентності. Визначення 2. Дві граматичні струк- тури 1C і 2C функціонально еквівалентні (слабко), якщо вони породжують одну і ту ж мову, тобто )()( 21 ALAL = . Визначення 3. Структура C зветься нескороченою, якщо продукції і аксіоми її аксіоматики задовольняють властивості ))(,,;( VFyxyxyx ∈≤→ , де l - дов- жина ланцюжка l . Визначення 4. Структура C зветься ο - вільною граматичною структурою, як- що її аксіоматика не містить у собі про- дукцій і аксіом типу ))(;( VFxx ∈→ ο . Не складно довести, що в будь яко- му класі еквівалентності граматичних структур завжди існує нормальна струк- тура hC , тобто структура продукції і аксі- оми аксіоматики, якої мають властивість ))(;( NFxyx ∈→ . А також, що у всякому класі еквівалентності з нескороченою од- нозначною структурою існує однозначна ο - вільна BC- граматична структура. Але для формальних граматичних структур можливо встановити нові алгеб-              ∈∈ =××=××≠=× =→→→≠→=→ ×→ −×→ −=→ =Λ __________ __ __ ][][][][][ ][ ][ );(;, ;)()(,, ;,, :операційівластивост ;: початку;аксіома: виводу;аксіома\|: :виводупродукції 3 2 1 VFcN ccccccc cccccccсс bр aр bbp γβ βγγβγβββββ βγβββ αα ασ αα Теоретичні та методологічні основи програмування 7 раїчні результати, наприклад, структура (1) є універсальною відносно вільної мови F(V) у тому розумінні, що структура ви- значена на словникові )(VFV ⊂ і поро- джує множину ланцюжків L(V), по опера- ції заміщення за аксіоматикою Λ , таку, що має місце ланцюг за включенням )()()( VFVLAL ⊂⊂ . Серед множини фор- мальних структур можливо виділити го- моморфні та ізоморфні структури. Так фо- рмальні структури C і 1111 ,, ΛΣ= VC ізо- морфні, якщо для будь яких елементів Vb ∈ і будь яких операцій Σ∈∗)( , 11)( Σ∈∗ та форм аксіоматик Λ∈ϕ , 11 Λ∈ϕ існує взаємно однозначне відобра- ження ρ множини V на множину 1V і форм аксіоматики Λ на форми аксіома- тики 1Λ таке, що )))((),(( )))(,((),(())(( 11 1 bb bbbb ρρϕ ϕρρρ ∗= =∗∗=∗ . Так як нас цікавить питання відтво- рення формальних структур, то розглянемо їх будову за допомогою формальних гра- матичних підструктур. Визначення 5. Структуру 1 2 11 },{, Λ→= VC назвемо підструктурою структури Λ→= },{, 2VC , якщо викону- ються включення VV ⊆1 і Λ⊆Λ1 - по спрощеній аксіоматиці, і скорочено це по- значимо CC _ 1 p . Підструктура 1C є порож- ньою підструктурою, якщо вона породжує тільки порожню мову ∅=L , тобто для підструктури задовольняється хоча б одна з умов 1) ∅== ){1 οV ; 2) };{1 Jixi ∈→=Λ ο ; 3) ( ){1 ο=V і };{1 Jixi ∈→=Λ ο ); 4) аксіоматика 1Λ не може поро- джувати ні одного ланцюжка мови )( 1VL . Зауваження 1. Очевидно, наведене визначення порожньої підструктури за умовами 1) – 4) еквівалентні згідно визна- ченню 2. Зрозуміло, що довільна не порожня підструктура граматичної структури C частково зберігає за собою той же тип, який має структура C , тобто як сама стру- ктура так і її підструктури можуть належа- ти до одного з класів, наприклад, BC , VC - структур, крім того ця підструктура може частково породжувати або зовсім не поро- джувати ні одного ланцюжка мови )(AL . Породжувальні, повні та утворюючі граматичні підструктури Визначення 6. Підструктуру ∗C фо- рмальної граматичної структури (1) назве- мо породжувальною підструктурою, якщо існує вивід W(l) ланцюжка l у структурі CC _p∗ , такий, що )(ALl ∈ . Породжу- вальну підструктуру CC _p∗ , в якій виво- диться тільки один ланцюжок )(ALl ∈ фо- рмальної мови граматичної структури C назвемо структурою ланцюжка l формаль- ної мови L(A). Отже довільна підструктура грама- тичної структури C тоді і тільки тоді поро- джувальна, коли її аксіоматика ∗Λ містить у собі хоча б по одній аксіомі виводу та початку і сукупність продукцій, пов’язаних хоча б з одним виводом )(lW ланцюжка )(ALl ∈ . Так як під виводом W(l) ланцюжка )(ALl ∈ розуміється упорядкована послі- довність безпосередньо виведених у струк- турі ∗ lC проміжних ланцюжків [1, 2], то взагалі між структурою ланцюжка і його виводом існує тільки гомоморфне відно- шення, і тому вивід W(l) задає будову лан- цюжка l. Не складно бачити, що будь яка підструктура iC структури є частково уні- версальною відносно вільної мови )()( VFVF i ⊆ , тобто і відносно мови )(VF . Нехай 1C і 2C довільні підструк- тури структури C, під їх об’єднанням і пе- ретином будемо розуміти 212121 ,, ΛΛΣ=∪ UUVVCC і 212121 ,, ΛΛΣ=∩ IIVVCC , де IU, - звичайні теоретико-множинні операції. Причому перетин вважається порожнім, якщо ∅=21 VV I ї ∅=ΛΛ 21 I , або Теоретичні та методологічні основи програмування 8 ( ∅=21 VV I і ∅=ΛΛ 21 I ), тоді, справед- лива така теорема. Теорема 1. Не порожній перетин (об’єднання) сукупності підструктур },{ IiCi ∈ ο - вільної граматичної струк- тури C також утворюють підструктуру даної структури. Крім того сукупність усіх підструк- тур структури C є структурою – решіткою на операціях об‘єднання та перетину. Між двома підструктурами 1C і 2C можливо ввести відношення включення: за словником 212211 );()( VVVCVC ⊆p , за аксі- оматикою 212211 );()( Λ⊆ΛΛΛ CC p . Під включенням підструктур 21 CC p в пода- льшому розуміється включення за словни- ком і за аксіоматикою цих підструктур. Отже між двома підструктурами 1C і 2C існує відношення включення )(p тоді і тільки тоді, коли мають місце включення 2121 , Λ⊆Λ⊂ VV або 2121 , Λ⊂Λ⊆ VV , або наступне - 2121 , Λ⊂Λ⊂ VV . Визначення 7. Сукупність (не всіх порожніх) підструктур iC , для яких вико- нується умова },;{ CCIiC i i i =∪∈ назива- ється системою утворюючих підструктур структури C. Якщо система утворюючих підструктур структури C складається з двох підструктур 1C і 2C , таких, що CCC =∪ 21 і ∅=∩ 21 CC , то підструк- тура 2C є доповненням підструктури 1C до формальної структури C. Система утворюючих підструктур називається повною системою у тому ро- зумінні, що вона повністю відтворює фор- мальну структуру C і в ній нема зайвих підструктур, які не впливають на відтво- рення структури C. Виходячи з того, що словник V і аксіоматика Λ формальної граматичної структури C є скінченими приходимо до висновку, що система утво- рюючих підструктур }{ iC також є скінче- ною множиною. Лема 1. Нехай підструктура 2C є доповненням підструктури 1C до форма- льної структури C, тоді множину всіх під- структур }{ iC структури C можна розбити на три класи підструктур: };{ 11 CCCK jj p= , };{ 22 CCCK jj p= , },;{ 22113 KCCKCCCK jjj ∈∩∈∩= . Наслідок 1. Очевидно, лема 1 має місце і в тому випадку, коли доповнення k k CC ∪=2 , де 1CCk p/ - підструктури фор- мальної структури C. Результат леми розбиття на класи є корисним при визначені будови множини підструктур формальної структури, зок- рема будови її системи утворюючих підст- руктур. Теорема 2. У будь якій системі утворюючих підструктур },;{ CCIiCS i i i =∪∈= формальної гра- матичної структури C можливо виділити систему SS ⊆∗ утворюючих поро- джувальних підструктур або побудувати на системі S систему підструктур ∗S таку, що },;{ CCIJjCS j j j =∪⊂∈= ∗∗∗ . Зазначимо, що теорема стосується як існування системи підструктур ∗S , так і існування процедури побудови такої під- системи, За умовою теореми система S є утворюючою структури C, аксіоматики підструктур яких містять форми ( ; )ip i I∈ необхідні для виведення у структурі C всіх ланцюжків мови L(A). Тому для доведення теореми розіб’ємо скінчену систему S на дві підмножини 1S - яка складається з по- роджувальних підструктур і 2S - з не поро- джувальних підструктури так, що SSS =21 U і ∅=21 SS I . Якщо система 1S є утворюючою, тобто 1SS =∗ , тоді тео- рема доведена. У протилежному випадку за теоремою 1 на підструктурах систем 1S і 2S за допомогою суперпозицій if над операціями )(∪ і )(∩ утворимо підструк- тури kC на окремих формах );( IJjCfp jii ⊂∈= або їх комбінаціях. Очевидно, в силу повноти множини форм Теоретичні та методологічні основи програмування 9 );( Iipi ∈ , об’єднання k k C∪ зі словником V є породжувальною підструктурою з од- ного боку і утворюючою системою сис- теми C з другого боку. Доповнюючи поро- джувальні підструктури системи 1S підст- руктурою k k C∪ знову отримаємо систему утворюючих підструктур граматичної структури C. Зрозуміло, що це доведення справедливе і у випадку, коли окремо одна з систем 1S і 2S є порожньою. Серед сукупності підструктур }{ iC граматичної структури C існують такі під- структури jC , аксіоматика яких jΛ повні- стю відтворює їх структуру, тобто jjj VC ΛΣ= ,, . Назвемо такі підструк- тури повними підструктурами jC , а відпо- відні їм аксіоматики відтворюючими аксі- оматиками jΛ . Теорема 3. На будь-якій системі утворюючих підструктур S структури C можна побудувати систему утворюючих повних підструктур },;{ CCJjCS j j j =∪∈= . Для доведення теореми розглянемо довільну підструктуру SCi ∈ . Якщо ця структура не є ο - вільною і на її словни- кові iV за аксіоматикою iΛ можливо виве- сти тільки порожній ланцюжок тоді за ви- значенням 5 за умов 1), 3) і 4) підструктура - порожня. За зауваженням 1 замінимо структуру iC еквівалентною структурою з умовою 2) так, що аксіоматика jΛ буде складатися тільки з продукцій вигляду ο→ix , після заміни правих частин проду- кцій порожнім символом ο , а словник jV створимо з різних символів аксіоматики jΛ . Таким чином у цьому випадку маємо SC j ∈ . Нехай тепер структура iC не поро- жня, тоді приймемо аксіоматику iΛ за ак- сіоматику jΛ , при цьому можливі такі ви- падки: 1) аксіоматика iΛ повністю від- творює структуру iC , тобто ji VV = ; 2) аксіоматика iΛ не повністю відтворює структуру iC , але ij VV ⊂ . З чого за сукупністю випадків 1) і 2) слідує включення, ij CC p . Якщо для аксіоматики ii Λ=Λ ма- ємо ii VV ⊂ , то розбиваючи аксіоматику jiji −ΛΛ=Λ U , так, щоб ij VV ⊆ отрима- ємо і в цьому випадку включення ij CC p . При цьому завершується доведення тео- реми. Зауваження 2. За результатом тео- реми 2 маємо для систем утворюючих під- структур наступне включення SS ⊆∗ і за теоремою 3 – ланцюг за включенням SSS ⊆⊆∗ . Максимальні граматичні підструктури. Умови повноти системи утворюючих підструктур З’ясуємо тепер питання критеріїв, за якими можливо встановити існування систем утворюючих підструктур формаль- ної граматичної структури і визначимо ефективні критерії, за якими можливо від- творити граматичну структуру за структу- рами утворюючих ланцюжків заданої фо- рмальної мови. Для розв’язку проблема існування критеріїв про знаходження систем утво- рюючих підструктур скористуємося алгеб- раїчним підходом [11]. Визначення 8. Нехай C довільна граматична структура (1), тоді підструк- тура mC структури C називається максима- льною підструктурою CCm p , якщо не існує такої підструктури CC p1 , для якої мало б місце власне включення 1CCm p . Позначимо ip довільну продукцію аксіоматики Λ структури C. Тепер, підст- руктура mC буде максимальною відносно структури C тоді і тільки тоді, коли для будь якого елемента mCCv < r∈ такого, що },{ IipVv i ∈∈ U має місце CvCm =+ __][ }{ . Теоретичні та методологічні основи програмування 10 Тут під різницею mCC < структур розумі- ється підструктура: ΛΣ,,\ mVV або mV ΛΛΣ \,, формальної граматичної структури C, а операція )( + __][ визначає при- єднання елемента v до словника або аксіо- матики підструктури mC до структури C. Позначимо M множину всіх підст- руктур максимальних щодо структури C. Зрозуміло, що граматична структура C має скінчену кількість максимальних підструк- тур. Для подальшого необхідна наступна лема розширення будь-якої підструктури граматичної структури ΛΣ= ,,VC . Лема 2. Будь яку підструктуру CC p1 можливо розширити до максима- льної підструктури MCm ∈ структури C. За ствердженням леми маємо, що для довільної підструктури 1C структури C у множині M існує підструктура mC , що можливе тільки таке включення mCC p1 , бо в протилежному випадку виконується включення mCC f1 і підструктура 1C не є власною підструктурою структури C. При- пустимо, що для підструктури 1C у мно- жині M не існує підструктури 1CCm f . Тоді приєднуючи до підструктури 1C усі елементи },{ IipVv i ∈∈ U , яких нема у цій підструктурі крім одного 1Cv ∉∗ r за скінчену кількість кроків отримаємо мак- симальну підструктуру mC ,1 щодо струк- тури C, що призводить до протиріччя з припущенням. Таким чином будь-яку вла- сну підструктуру граматичної структури завжди конструктивно можливо розши- рити до максимальної підструктури. Тепер розглянемо критерії, за яким визначається, що система підструктур гра- матичної структури є утворюючою систе- мою. Теорема 4. Для того, щоб система підструктур };{ IiCS i ∈= граматичної структури C була утворюючою необхідно і достатньо, щоб для будь якої підструктури MCm ∈ у системі S знайшовся хоча б один елемент }};;{{ , IiJjpVv jii ∈∈∈ U такий, що mCv ∉ r . За необхідністю система S- утво- рююча щодо структури C, тобто CCi Ii =∪ ∈ і так як для максимальної підструктури MCm ∈ , за її визначенням існує такий еле- мент mCv ∉ r , що mCCv < r∈ , то в системі S існує хоча б одна підструктура jC для якої jCv ∈r . При доведенні достатності розгля- немо таку систему S, що для будь-якої ма- ксимальної підструктури MCm ∈ струк- тури C в ній існує хоча б один елемент SCv i ∈∈r , такий, що mCv ∉ r . Доведемо, що система S є утворюючою, тобто CCi Ii =∪ ∈ . Припустимо, що система S не є сис- темою утворюючих підструктур - CCi Ii ≠∪ ∈ , тоді користуючись результатами леми 2, будь-яку підструктуру SCi ∈ роз- ширимо до максимальної підструктури MC mi ∈, структури C з чого маємо вклю- чення mii CC ,p . Але за умовою у підструк- турі iC існує такий елемент iv , для якого mii Cv ,∉ r , що призводить до порушення включення mii CC ,p . Таким чином наше припущення про те, що сукупність підст- руктур S не є системою утворюючих під- структур породжувальної граматичної структури C не вірне і теорема доведена. Зауваження 3. Нескладно бачити, що теорема 4 виконується також для сис- тем породжувальних підструктур ∗S і повних під структур S граматичної струк- тури C. Алгоритм побудови утворюючих підструктур. Мінімальні граматичні підструктури Визначення 9. Виведені ланцюжки у структурах ∗ iC системи утворюючих під- структур ∗S структури C називається зра- зком ls формальної мови L(A). Теоретичні та методологічні основи програмування 11 Отже за результатами леми 1 та те- ореми 4 можливо запропонувати наступ- ний алгоритм побудови системи утворюю- чих підструктур формальної структури C і дослідити будову цієї утворюючої системи підструктур: крок 1) побудувати множину максималь- них підструктур M структури C; крок 2) за елементами Cvi ∈r , які не вхо- дять до максимальних підструк- тур побудувати систему утворю- ючих підструктур, що містять у собі елементи iv ; крок 3) на системі утворюючих підструк- тур формальної системи побуду- вати структурний граф залежності підструктур; крок 4) виділити у системі утворюючих підструктур підструктуру 1C і до- повнену до неї підструктуру 2C , відносно яких за лемою 1 побуду- вати три класи 21 , KK та 3K ; крок 5) з класів 1K і 2K видиліти макси- мальні за включенням підструк- тури, тобто такі ik KC ∈ , що для всіх kjKC ij ≠∈ ; kj CC p ; крок 6) на об’єднані незалежних структур класів 1K і 2K побудувати повну систему утворюючих підструктур формальної структури. Приклад 1. Застосуємо наведений алгоритм до формальної структури C з ак- сіоматикою: І побудуємо породжувальну сис- тему ∗S граматичної структури на аксіо- матиці (2). Крок 1. Так як система ∗S повна, тому для неї і максимальної множини M достатньо скористуватися відповідними аксіоматиками. Так множина аксіоматик для сукупності M є }\,\,\,\,\,\{ 245678 pppppp ΛΛΛΛΛΛ . Підструктури з аксіоматиками 1\ pΛ та 3\ pΛ не залучені до множини M бо вони не породжувальні. Крок 2. Система утворюючих під- структур повинна включати такі елементи: 876542 ,,,,, pppppp . Такою системою, на- приклад, буде утворююча система з аксіо- матиками: },,,,{ 54321 ΛΛΛΛΛ , (3) де },,{ 8311 ppp=Λ , },,,{ 83212 pppp=Λ , },,,{ 84313 pppp=Λ , },,,{ 75314 pppp=Λ і },,,,{ 765315 ppppp=Λ . Крок 3. Структурний граф системи утворюючих підструктур формальної структури C з відповідними аксіоматиками за включеннями: CCC pp ∗∗ 54 , CCC pp ∗∗ 31 і CCC pp ∗∗ 21 ; наведений на рис. 1. Крок 4. Серед системи підструктур з аксіоматиками (3) виберемо структуру ∗ 5C , для якої доповненою до формальної структури C буде структура ∗∗ ∪ 32 CC . Так                → → → → → → → −→ =Λ cp cp cp cp bp bp ap ap β γ γγ γβ ββ βα αα ασ : : виводуаксіоми : : : : : початкуаксіома: 8 7 6 5 4 3 2 1 та мовою },,;{ NmnkcbaL mnk ∈= . (2) Теоретичні та методологічні основи програмування 12 як CCCC =∪∪ ∗∗∗ 325 і аксіоматика струк- тури )( 325 ∗∗∗ ∪∩ CCC складається з проду- кцій },{ 31 pp , які дозволяють породжувати лише порожню мову тому система утво- рюючих підструктур розбивається на кла- си },{ 541 ∗∗= CCK , },,{ 3212 ∗∗∗= CCCK і ∅=3K . Крок 5. За структурним графом ма- ксимальними за включенням підструкту- рами класу 1K є ∗ 5C , а класу 2K - ∗∗ 32 , CC . Крок 6. На незалежних підструкту- рах класів 1K та 2K можливо отримати повну систему утворюючих породжуваль- них підструктур * * * 2 3 5{ , , }C C C . Покажемо, що побудована таким чином повна система утворюючих підст- руктур не єдина. Для цього спочатку побудуємо по- вний граф системи утворуючих підструк- тур . Граф вважається повним у тому ро- зумінні, що включає всі можливі повні (за визначенням 8) породжуючі підструктури формальної структури C. Граф будується за рекурентною процедурою: спочатку знаходяться всі максимальні підструктури формальної структури C, потім - максима- льні підструктури для них і т. д. Повний граф для прикладу 1 пока- зано на рис. 2 (для наочності та спрощення представлення деякі вершини графа зазна- чені кілька разів). Аксіоматики відповідних підструк- тур, для якого: },,,,,,{ 76543211,1 ppppppp=Λ , },,,,{ 843212,1 ppppp=Λ , },,,,,,{ 87543213,1 ppppppp=Λ , },,,,,,{ 87653214,1 ppppppp=Λ , },,,,,,{ 87654315,1 ppppppp=Λ , },,,,,{ 7654311,2 pppppp=Λ , ∗ 1C ∗ 3C ∗ 2C ∗ 4C ∗ 5C C Рис. 1. Структурний граф системи утворюючих підструктур ∗ 1,1C C ∗ 2,1C ∗ 3,1C ∗ 5,1C∗ 4,1C ∗ 1,2C ∗ 2,2C ∗ 3,2C ∗ 4,2C ∗ 5,2C ∗ 6,2C ∗ 7,2C ∗ 8,2C ∗ 3,2C ∗ 9,2C ∗ 2,2C ∗ 4,2C ∗ 1,2C∗ 8,2C ∗ 5,2C ∗ 6,2C ∗ 9,2C ∗ 1,3C ∗ 2,3C ∗ 3,3C ∗ 1,4C ∗ 4,3C ∗ 4,2C ∗ 5,3C ∗ 2,3C ∗ 4,3C ∗ 1,4C ∗ 4,2C ∗ 5,3C ∗ 3,3C∗ 4,2C ∗ 5,2C ∗ 1,3C ∗ 4,3C ∗ 5,3C Рис. 2. Повний структурний граф системи утворюючих підструктур Теоретичні та методологічні основи програмування 13 },,,,,{ 7653212,2 pppppp=Λ , },,,,,{ 7543213,2 pppppp=Λ , },,,{ 83214,2 pppp=Λ , },,,{ 84315,2 pppp=Λ , },,,,,{ 8754316,2 pppppp=Λ , },,,,{ 843217,2 ppppp=Λ , },,,,,{ 8753218,2 pppppp=Λ , },,,,,{ 8765319,2 pppppp=Λ , },,,,{ 765311,3 ppppp=Λ , },,,,{ 754312,3 ppppp=Λ , },,,,{ 753213,3 ppppp=Λ , },,{ 8314,3 ppp=Λ , },,,,{ 875315,3 ppppp=Λ , },,,{ 75311,4 pppp=Λ . За основні утворюючі підструктури (утворюючий базис) можливо взяти кін- цеві породжувальні структури графа 1,4C і 4,3C (рис. 2) з відповідними аксіоматиками (тобто такі, що не мають підструктур за відношенням включення) та додати до них підструктури з аксіоматиками 4,31,4 \\ ΛΛΛ . Отже отримаємо нову сис- тему утворюючих підструктур з аксіома- тиками }\\,,{ 4,31,44,31,4 ΛΛΛΛΛ . Таким чином на структурах двох простих ланцю- жків abcl =1,4 і abccl =4,3 та рекурсивних продукціях 2p , 4p і 6p аксіоматики (2) відтворюється формальна граматична структура C. Визначення 10. Систему утворюю- чих підструктур структури C побудовану на кінцевих породжувальних підструкту- рах структурного графа назвемо мінімаль- ною системою утворюючих підструктур oS структури C. Зауваження 4. Запропоновану ме- тодику побудови повної системи утворю- ючих підструктур також зручно застосову- вати тому випадку коли відомі дерева ви- водів утворюючих ланцюжків, при цьому слід звернути увагу на те, що однозначне відтворення формальних систем можливе тільки для VC - структур. Відтворення граматичних структур за зразками формальної мови Перш ніж перейти до розгляду за- дачі відтворення формальних граматик за заданими структурами ланцюжків зразка, введемо деякі припущення: 1) рішення щодо ланцюжків зразка формальної мови, кількості його елементів та повноти приймаються поза межами даної методи; 2) виходячи з того, що вибра- ному зразку може відповідати декілька мов, рішення щодо прийнятної формальної мови приймається поза межами даної ме- тоди; 3) формальні структури лан- цюжків зразку приймаються за систему утворюючих підструктур граматичної структури прийнятної мови, тобто мають загальну граматичну структуру; 4) структури ланцюжків зразка утворюють систему S . Нехай задано зразок )}(,;{ ALlIils iil ∈∈= і система структур ланцюжків цього зразка };{ IiCS i ∈= ∗ . Те- пер можливо поставити наступну задачу: на заданій парі Ssl , побудувати мініма- льну систему утворюючих підструктур oS (мінімальну формальну граматичну струк- туру oC ). Алгоритм розв’язку задачі спира- ється на вище наведену схему побудови системи утворюючих підструктур і полягає в наступному: 1. провести аналіз системи структур S на виконання пункту 3) щодо впо- рядкування підструктур системи S загаль- ній граматичній структурі, для цього слід скористатися операцією посимвольного перетину ланцюжків і внести корективи у відповідні структури ланцюжків зразка. Під посимвольним перетином тут мається на увазі однакові послідовності алфавітних символів присутні у кожному з ланцюжків (таких послідовностей може бути декі- лька); 2. з урахуванням результату кроку 1), побудувати структурні графи виводів лан- цюжків заданого зразка; Теоретичні та методологічні основи програмування 14 3. за результатами кроку 2), на системі S побудувати впорядковану систему yS і прийняти її за систему утворюючих підст- руктур граматичної структури; 4. на системі утворюючих підструктур формальної системи побудувати структур- ний граф залежності підструктур; 5. включити кінцеві підструктури yjk SC ∈ структурного графа до мі- німальної системи утворюючих підструк- тур oS ; 6. за допомогою багатократного засто- сування операцій ),( <∩ над кінцевими структурами * jkC структурного графа й ін- шими структурами системи yS та структу- рами результатів цих операцій (або над структурними графами виводів ланцюжків цих структур) виділити прості структури, які відповідають різним продукціям kp структур системи yS ; 7. доповнити систему oS простими структурами. Відтворену таким чином формальну структуру C назвемо мінімальною струк- турою oC . Зауваження 5. Виходячи з припу- щення 4) всі дії та перетворення за алгори- тмом можна виконувати над аксіомати- ками відповідних структур і підструктур. Для порівняння результату побу- дови мінімальної граматичної структури скористуємося прикладом 7.5 роботи [3]. Приклад 2. Нехай задано зразок }71;{ K== ils il з ланцюжками: bcal 3 1 = ( caaabl =1 ), babl 22 2 = , bcal 2 3 = , abbl 2 4 = , cabl =5 , 3 6 bl = і cbl =7 ; та їх відповідними структурами з аксіо- матиками:        → → → → =Λ ab a a c γ γβ βα ασ , , , 1 ;      → → → =Λ ab a bb η ηδ δσ , , 2 ;      → → → =Λ ab a c ψ ψϕ ϕσ , , 3 ;    → → =Λ ab bb µ µσ , 4 ;    → → =Λ ab c λ λσ , 5 ; { bbb→=Λ σ6 ; { cb→=Λ σ7 ; в яких перша продукція – аксіома початку, а остання – аксіома виводу. Крок 1. Аналізуючи наведені стру- ктури за посимвольною операцією (на множинах символів) перетину ланцюжків, наприклад, bllll == 6576 II з’ясовуємо, що в усіх аксіомах виводу повинна бути продукція виводу символу b . Отже аксі- оми виводу в аксіоматиках 1Λ , …, 5Λ слід замінити продукціями ba →→ ττξ , ; і нетермінали λµψηγ ,,,, у відповідних ак- сіоматиках замінити символом ξ , а у шос- тій і сьомій аксіоматиках замінити аксіоми початку відповідними парами продукцій    −→ −→ =Λ виводуаксіомаb початкуаксіомаbb τ τσ 6 ;    −→ −→ =Λ виводуаксіомаb початкуаксіомас τ τσ 7 . Крок 2. Тепер маємо можливість побудувати структурні графи виводів лан- цюжків зразка ( рис. 3). Крок 3. Аналіз підструктур за стру- ктурними графами виводів, з урахуванням перейменування нетермінального алфавіту Теоретичні та методологічні основи програмування 15 надає можливість виявити наступні відно- шення за включенням між підструктурами (збережені попередні позначки): * 2 * 4 * 6 CCC pp та * 1 * 3 * 5 * 7 CCCC ppp . Крок 4. За результатами кроку 3 не- складно побудувати структурний граф (рис. 4) залежності підструктур по вклю- ченнях системи }71;{ * K== iCS iy фор- мальної граматичної структури C. Крок 5. Кінцевими структурами графа є підструктури * 6C і * 7C . Крок 6. За операцією )(∩ на кінце- вих структури * 6C і * 7C та на інших струк- турах системи yS (див. рис. 3) виділяється тільки одна рекурсивна продукція αττ → . Крок 7. Поєднавши аксіоматику кі- нцевих підструктур з продукцією винай- дену на кроці 6 маємо аксіоматику мініма- льної граматичної структури         → −→ → → =Λ ττ τ τσ τσ а виводуаксіомаb c bb початкуаксіоми o : за якою породжується формальна мова }2,1,0,};{}{{)( KU == nkbcabbbaAL nk . Висновки У матеріалах даної роботи розгля- нуто формальні граматичні породжувальні структури та їх підструктури. Визначені їх властивості та з’ясована можливість пред- ставлення граматичних структур через си- стеми утворюючих підструктур. Отримано критерій повноти систем утворюючих під- структур формальної граматичної струк- тури і запропоновано алгоритмічне розв’язання проблеми побудови систем утворюючих підструктур. Таким чином розроблений формальний апарат, який до- зволяє досліджувати такі об’єкти, як гра- матики, включаючи графічні граматики зі спеціфічними операціями поєднання тер- міналів та нетерміналів у ланцюжки. Запропонований апарат зі зміною операцій та оксіоматики дозводляє дослі- джувати й інші об’єкти, такі як графи, ал- горитми, тощо. Запропонована методика алгорит- мічного розв’язання задачі відтворення граматичних структур та породжених ни- ми мов за структурами їх мовних конс- трукцій дозволить вирішувати задачі роз- пізнавання структур графічних об’єктів на відміну задачі розпізнавання самих графі- чних об’єктів за наданими структурами, скажімо у вигляді графічних граматик. Рис. 3. Структурні графи виводів ланцюжків зразка 11 : lC c a a a b 22 : lC bb a a b 33 : lC c a a b 44 : lC bb a b 55 : lC c a b 77 : lC c b 66 : lC bb b Рис. 4. Структурний граф залежності підструктур C 2C 4C 6C 1C 3C 5C 7C Теоретичні та методологічні основи програмування 16 1. Гинзбург С. Математическая теория кон- текстно-свободных языков. - М.: Мир, 1970. – 328 с. 2. Гладкий А.В. Формальные грамматики и языки. - М.: Наука, 1973. – 368 с. 3. Фу К.С. Структурные методы в распозна- вании образов. - М.: Мир, 1977. – 318 с. 4. Ильман В.М., Разумов С.Ю. Структурный подход в формальных системах // Пробле- ми математичного моделювання. Міжнар. науково-метод. конф. Тези доповідей. Дніпродзержинськ, 2005. – С. 147 – 148. 5. Ільман А.В., Ільман В.М. Формально – структурне моделювання економічних сис- тем. // Вісн. Дніпропетровського націона- льного у-ту залізничного транспорту. – Вип.. 10. – Д.: Вид-во Дніпропетр. нац. ун- ту залізн. трансп., 2006. с. 173 – 180. 6. Павлюк О.В., Савчинський Б.Д. Ефектив- ний синтаксический аналіз та розпізнаван- ня структурованих зображень // Управ- ляющие системы и машины. – 2005. – № 5 . – С. 13-24. 7. Ту Дж., Гонсалес Р. Принципы распознава- ния образов. - М.: Мир, 1978. – 411с. 8. Котенко И.В. Восстановление формальных грамматик, задающих сценарии компью- терных атак, по прецендентам // Искусст- венный интеллект. – 2002. – № 3 . – С. 581-589. 9. Смальян Р. Теория формальных систем. - М.: Наука, 1981. – 209 с. 10. Калинин А.Г., Мацкевич И.В. Универсаль- ные языки программирования. Семантиче- ский подход. М.: Радио и связь, 1991. – 400 с. 11. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. - Киев: Наук. думка, 1978. – 320 с. Отримано 11.12.2006 Про авторів: Ільман Валерій Михайлович, кандидат фіз.-мат. наук, доцент кафедри «Комп’ютерні інформаційні технології» Дніпропетровського національного універ- ситету залізничного транспорту імені ака- деміка В. Лазаря на, Шинкаренко Віктор Іванович, канд. техн. наук, доцент кафедри «Комп’ютерні інформаційні технології» Дніпропетровського національного універ- ситету залізничного транспорту імені ака- деміка В. Лазаряна. Місце роботи авторів: Дніпропетровський національний універ- ситет залізничного транспорту імені академіка В. Лазаряна. м. Дніпропетровськ, вул. Лазаряна 2, каф. КІТ, ДНУЗТ тел. 8-056-373-15-35. Дніпропетровський національний універ- ситет залізничного транспорту імені академіка В. Лазаряна. м. Дніпропетровськ, вул. Лазаряна 2, каф. КІТ, ДНУЗТ тел. 8-056-373-15-35. e-mail: ccp@diit-70.dp.ua

Структурний підхід до проблеми відтворення граматик

Institution

Similar Items