www.wikidata.uk-ua.nina.az

Висота ітерації мови У теоретичній інформатиці а саме теорії формальних мов висота ітерації це міра структурної складнос

Висота ітерації мови

У теоретичній інформатиці, а саме, теорії формальних мов, висота ітерації — це міра структурної складності регулярних виразів — висота ітерації регулярного виразу дорівнює найбільшій глибині вкладеності зірочок, наявних у регулярному виразі. Поняття висоти ітерації першим увів та вивчав Егган (1963).

Формальне визначення ред.

Формально, висота ітерації регулярного виразу над скінченним алфавітом визначається індуктивно так:

  • , і для будь-якого символу з .

Тут позначає порожню множину, означає порожній рядок, а і  — довільні регулярні вирази.

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

Приклади ред.

Хоча обчислити висоту ітерації регулярного виразу просто, визначення висоти ітерації мови іноді може видатися заплутаним. Наприклад, регулярний вираз

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

висота ітерації якого лише 1. Щоб довести, що висота ітерації мови дорівнює 1, потрібно виключити можливість опису мови регулярним виразом із меншою висотою ітерації. Наприклад, це можна зробити побічно, довівши, що мова з висотою ітерації 0 містить лише скінченне число слів. Оскільки наша мова нескінченна, вона не може мати висоту ітерації 0.

Висота ітерації групової мови[en] обчислювана. Наприклад, висота ітерації мови над , в якій число входжень і можна порівняти за модулем , дорівнює .

Теорема Еггана ред.

Приклад автомата з циклічним рангом 1. Алгоритм Кліні[en] перетворює його в регулярний вираз a*b*ba ((a|b)b*a|ε)* (a|b)b*|a*b*b, що має висоту ітерації 2. За теоремою Еггана має існувати еквівалентний регулярний вираз із висотою ітерації ≤1. Фактично a*b(b|a(a|b))* описує ту ж мову.

У своїх основоположних дослідженнях висоти ітерації регулярних мов Егган установив зв'язок між теорією регулярних виразів, теорією скінченних автоматів та орієнтованими графами. Надалі цей зв'язок став відомим як теорема Еггана. Нагадаємо деякі поняття з теорії графів та теорії автоматів.

У теорії графів циклічний ранг орієнтованого графа (орграфа) визначається індуктивно так:

  • Якщо не сильно зв'язний, то дорівнює найбільшому циклічному рангу серед усіх сильно зв'язних компонент графа .

У теорії автоматів недетермінований скінченний автомат з ε-переходами (ε-НСА) визначається як кортеж (Q, Σ, δ, q0, F), що складається з:

  • скінченної множини станів Q,
  • скінченної множини вхідних символів Σ,
  • множини помічених дуг δ, званих переходами : (тут ε позначає порожній рядок),
  • початкового стану q0 ∈ Q,
  • множини станів F, званих поглинальними, F⊆Q.

ε-НСА приймає слово w ∈ Σ*, якщо існує орієнтований ланцюг із початкового стану q0 до деякого кінцевого стану F, що використовує дуги з δ так що конкатенація всіх міток уздовж шляху утворює слово w. Множина всіх слів над Σ*, які приймає автомат, є мовою, яку приймає автомат A.

Якщо говорити про недетермінований скінченний автомат A зі множиною станів Q як про орієнтований граф, ми природно маємо на увазі граф із множиною вершин Q, породженою переходами. Тепер можна сформулювати теорему.

Доведення цієї теореми дав Егган, і пізніше Сакарович.

Узагальнена проблема висоти ітерації ред.

Наведене вище визначення передбачає, що регулярний вираз будується на елементах алфавіту A, з використанням тільки стандартних операцій об'єднання множин, конкатенації та замикання Кліні. Узагальнений регулярний вираз визначається як регулярний вираз, але включає ще операцію доповнення множини (доповнення завжди береться відносно всіх слів над A). Якщо вважати, що взяття доповнення не збільшує висоти ітерації, тобто

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

Зауважимо, що у той час як мови з нульовою (звичайною) висотою ітерації містять скінченну кількість слів, існують нескінченні мови з нульовою узагальненою висотою ітерації.

Приклад. Регулярний вираз

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

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

Мови з нульовою висотою ітерації називають мовами без зірочок[en]. Можна показати, що мова L є мовою без зірочок тоді й лише тоді, коли її синтаксичний моноїд[en] є аперіодичним[en].

Див. також ред.

  • Задача висоти ітерації мови[en]
  • Узагальнена задача висоти ітерації мови[en]

Примітки ред.

  1. Sakarovitch, 2009, с. 342.
  2. ↑ Eggan, 1963.
  3. ↑ Sakarovitch, 2009.
  4. Schützenberger, 1965.

Література ред.

  • Jean Berstel, Christophe Reutenauer. Noncommutative rational series with applications. — Cambridge : Cambridge University Press, 2011. — Т. 137. — (Encyclopedia of Mathematics and Its Applications) — ISBN 978-0-521-19022-0.
  • Rina S. Cohen. Techniques for establishing star height of regular sets // Theory of Computing Systems. — 1971. — Т. 5, вип. 2. — С. 97—114. — ISSN 1432-4350. — DOI:10.1007/BF01702866.
  • Rina S. Cohen, J.A. Brzozowski. General properties of star height of regular events // Journal of Computer and System Sciences. — 1970. — Т. 4, вип. 3. — С. 260—280. — ISSN 0022-0000. — DOI:10.1016/S0022-0000(70)80024-1. з джерела 5 червня 2022. Процитовано 5 червня 2022.
  • Lawrence C. Eggan. Transition graphs and the star-height of regular events // Michigan Mathematical Journal. — 1963. — Т. 10, вип. 4. — С. 385—397. — DOI:10.1307/mmj/1028998975.
  • Jacques Sakarovitch. Elements of automata theory. — Cambridge : Cambridge University Press, 2009. — ISBN 978-0-521-84425-3.
  • Arto Salomaa. Jewels of formal language theory. — Rockville, Maryland : Computer Science Press, 1981. — ISBN 0-914894-69-2.
  • M.P. Schützenberger. On finite monoids having only trivial subgroups // Information and Control. — 1965. — Т. 8, вип. 2. — С. 190—194. — ISSN 0019-9958. — DOI:10.1016/S0019-9958(65)90108-7. з джерела 5 червня 2022. Процитовано 5 червня 2022.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U teoretichnij informatici a same teoriyi formalnih mov visota iteraciyi ce mira strukturnoyi skladnosti regulyarnih viraziv visota iteraciyi regulyarnogo virazu dorivnyuye najbilshij glibini vkladenosti zirochok nayavnih u regulyarnomu virazi Ponyattya visoti iteraciyi pershim uviv ta vivchav Eggan 1963 Zmist 1 Formalne viznachennya 2 Prikladi 3 Teorema Eggana 4 Uzagalnena problema visoti iteraciyi 5 Div takozh 6 Primitki 7 LiteraturaFormalne viznachennya red Formalno visota iteraciyi regulyarnogo virazu E displaystyle E nbsp nad skinchennim alfavitom A displaystyle A nbsp viznachayetsya induktivno tak h 0 displaystyle h left emptyset right 0 nbsp h e 0 displaystyle h left varepsilon right 0 nbsp i h a 0 displaystyle h left a right 0 nbsp dlya bud yakogo simvolu a displaystyle a nbsp z A displaystyle A nbsp h E F h E F max h E h F displaystyle h left EF right h left E mid F right max left h E h F right nbsp h E h E 1 displaystyle h left E right h E 1 nbsp Tut displaystyle emptyset nbsp poznachaye porozhnyu mnozhinu e displaystyle varepsilon nbsp oznachaye porozhnij ryadok a E displaystyle E nbsp i F displaystyle F nbsp dovilni regulyarni virazi Visota iteraciyi h L displaystyle h L nbsp regulyarnoyi movi L displaystyle L nbsp viznachayetsya yak najmensha visota iteraciyi vsih regulyarnih viraziv sho predstavlyayut L displaystyle L nbsp Intuyitivno zrozumilo sho yaksho mova L displaystyle L nbsp maye visoku visotu iteraciyi vona sama po sobi skladna yiyi ne mozhna opisati v terminah prostih regulyarnih viraziv z nizkoyu visotoyu iteraciyi Prikladi red Hocha obchisliti visotu iteraciyi regulyarnogo virazu prosto viznachennya visoti iteraciyi movi inodi mozhe vidatisya zaplutanim Napriklad regulyarnij viraz b a a b a a displaystyle left b mid aa b right aa nbsp nad alfavitom A a b displaystyle A left a b right nbsp maye visotu iteraciyi 2 Odnak opisuvana mova yavlyaye soboyu mnozhinu vsih sliv sho zakinchuyutsya na a displaystyle a nbsp Cyu zh movu mozhna opisati za dopomogoyu virazu a b a displaystyle a mid b a nbsp visota iteraciyi yakogo lishe 1 Shob dovesti sho visota iteraciyi movi dorivnyuye 1 potribno viklyuchiti mozhlivist opisu movi regulyarnim virazom iz menshoyu visotoyu iteraciyi Napriklad ce mozhna zrobiti pobichno dovivshi sho mova z visotoyu iteraciyi 0 mistit lishe skinchenne chislo sliv Oskilki nasha mova neskinchenna vona ne mozhe mati visotu iteraciyi 0 Visota iteraciyi grupovoyi movi en obchislyuvana Napriklad visota iteraciyi movi nad a b displaystyle left a b right nbsp v yakij chislo vhodzhen a displaystyle a nbsp i b displaystyle b nbsp mozhna porivnyati za modulem 2 n displaystyle 2 n nbsp dorivnyuye n displaystyle n nbsp 1 Teorema Eggana red nbsp Priklad avtomata z ciklichnim rangom 1 Algoritm Klini en peretvoryuye jogo v regulyarnij viraz a b ba a b b a e a b b a b b sho maye visotu iteraciyi 2 Za teoremoyu Eggana maye isnuvati ekvivalentnij regulyarnij viraz iz visotoyu iteraciyi 1 Faktichno a b b a a b opisuye tu zh movu U svoyih osnovopolozhnih doslidzhennyah visoti iteraciyi regulyarnih mov Eggan 2 ustanoviv zv yazok mizh teoriyeyu regulyarnih viraziv teoriyeyu skinchennih avtomativ ta oriyentovanimi grafami Nadali cej zv yazok stav vidomim yak teorema Eggana 3 Nagadayemo deyaki ponyattya z teoriyi grafiv ta teoriyi avtomativ U teoriyi grafiv ciklichnij rang r G displaystyle r G nbsp oriyentovanogo grafa orgrafa G V E displaystyle G V E nbsp viznachayetsya induktivno tak Yaksho G displaystyle G nbsp ye aciklichnim r G 0 displaystyle r G 0 nbsp Ciklichnij rang dorivnyuye nulyu v razi porozhnogo grafa G displaystyle G nbsp Yaksho G displaystyle G nbsp silno zv yaznij i E displaystyle E nbsp ne porozhnya tor G 1 min v V r G v displaystyle r G 1 min v in V r G v nbsp de G v displaystyle G v nbsp orgraf otrimanij vidalennyam vershini v displaystyle v nbsp i vsih dug sho pochinayutsya abo zakinchuyutsya u v displaystyle v nbsp dd Yaksho G displaystyle G nbsp ne silno zv yaznij to r G displaystyle r G nbsp dorivnyuye najbilshomu ciklichnomu rangu sered usih silno zv yaznih komponent grafa G displaystyle G nbsp U teoriyi avtomativ nedeterminovanij skinchennij avtomat z e perehodami e NSA viznachayetsya yak kortezh Q S d q0 F sho skladayetsya z skinchennoyi mnozhini staniv Q skinchennoyi mnozhini vhidnih simvoliv S mnozhini pomichenih dug d zvanih perehodami Q S e Q displaystyle Q times Sigma cup varepsilon times Q nbsp tut e poznachaye porozhnij ryadok pochatkovogo stanu q0 Q mnozhini staniv F zvanih poglinalnimi F Q e NSA prijmaye slovo w S yaksho isnuye oriyentovanij lancyug iz pochatkovogo stanu q0 do deyakogo kincevogo stanu F sho vikoristovuye dugi z d tak sho konkatenaciya vsih mitok uzdovzh shlyahu utvoryuye slovo w Mnozhina vsih sliv nad S yaki prijmaye avtomat ye movoyu yaku prijmaye avtomat A Yaksho govoriti pro nedeterminovanij skinchennij avtomat A zi mnozhinoyu staniv Q yak pro oriyentovanij graf mi prirodno mayemo na uvazi graf iz mnozhinoyu vershin Q porodzhenoyu perehodami Teper mozhna sformulyuvati teoremu Teorema Eggana Visota iteraciyi regulyarnoyi movi L dorivnyuye najmenshomu ciklichnomu rangu sered usih nedeterminovanih skinchennih avtomativ z e perehodami sho prijmayut movu L Dovedennya ciyeyi teoremi dav Eggan 2 i piznishe Sakarovich 3 Uzagalnena problema visoti iteraciyi red Navedene vishe viznachennya peredbachaye sho regulyarnij viraz buduyetsya na elementah alfavitu A z vikoristannyam tilki standartnih operacij ob yednannya mnozhin konkatenaciyi ta zamikannya Klini Uzagalnenij regulyarnij viraz viznachayetsya yak regulyarnij viraz ale vklyuchaye she operaciyu dopovnennya mnozhini dopovnennya zavzhdi beretsya vidnosno vsih sliv nad A Yaksho vvazhati sho vzyattya dopovnennya ne zbilshuye visoti iteraciyi tobto h E c h E displaystyle h left E c right h E nbsp mozhna viznachiti uzagalnenu visotu iteraciyi regulyarnoyi movi L yak najmenshu visotu iteraciyi sered usih uzagalnenih regulyarnih viraziv sho predstavlyayut movu L Zauvazhimo sho u toj chas yak movi z nulovoyu zvichajnoyu visotoyu iteraciyi mistyat skinchennu kilkist sliv isnuyut neskinchenni movi z nulovoyu uzagalnenoyu visotoyu iteraciyi Priklad Regulyarnij viraz a b a displaystyle a mid b a nbsp navedenij u prikladi vishe mozhna ekvivalentno perepisati yak uzagalnenij regulyarnij viraz c a displaystyle emptyset c a nbsp oskilki dopovnennya porozhnoyi mnozhini ce tochno vsi slova nad alfavitom A Takim chinom mnozhina vsih sliv nad alfavitom A sho zakinchuyutsya bukvoyu a maye visotu iteraciyi odin todi yak uzagalnena visota iteraciyi dorivnyuye nulyu Movi z nulovoyu visotoyu iteraciyi nazivayut movami bez zirochok en Mozhna pokazati sho mova L ye movoyu bez zirochok todi j lishe todi koli yiyi sintaksichnij monoyid en ye aperiodichnim en 4 Div takozh red Zadacha visoti iteraciyi movi en Uzagalnena zadacha visoti iteraciyi movi en Primitki red Sakarovitch 2009 s 342 a b Eggan 1963 a b Sakarovitch 2009 Schutzenberger 1965 Literatura red Jean Berstel Christophe Reutenauer Noncommutative rational series with applications Cambridge Cambridge University Press 2011 T 137 Encyclopedia of Mathematics and Its Applications ISBN 978 0 521 19022 0 Rina S Cohen Techniques for establishing star height of regular sets Theory of Computing Systems 1971 T 5 vip 2 S 97 114 ISSN 1432 4350 DOI 10 1007 BF01702866 Rina S Cohen J A Brzozowski General properties of star height of regular events Journal of Computer and System Sciences 1970 T 4 vip 3 S 260 280 ISSN 0022 0000 DOI 10 1016 S0022 0000 70 80024 1 Arhivovano z dzherela 5 chervnya 2022 Procitovano 5 chervnya 2022 Lawrence C Eggan Transition graphs and the star height of regular events Michigan Mathematical Journal 1963 T 10 vip 4 S 385 397 DOI 10 1307 mmj 1028998975 Jacques Sakarovitch Elements of automata theory Cambridge Cambridge University Press 2009 ISBN 978 0 521 84425 3 Arto Salomaa Jewels of formal language theory Rockville Maryland Computer Science Press 1981 ISBN 0 914894 69 2 M P Schutzenberger On finite monoids having only trivial subgroups Information and Control 1965 T 8 vip 2 S 190 194 ISSN 0019 9958 DOI 10 1016 S0019 9958 65 90108 7 Arhivovano z dzherela 5 chervnya 2022 Procitovano 5 chervnya 2022 Otrimano z https uk wikipedia org w index php title Visota iteraciyi movi amp oldid 36118680