Бжозовский туындысы - Википедия - Brzozowski derivative

«Қатысты сөздік жолының Бзозовский туындысы (қызыл фонда)»кон"

Жылы теориялық информатика, атап айтқанда ресми тіл теориясы, Бжозовский туындысы сен−1S а орнатылды S жіптер мен а жіп сен ішіндегі жолдан алуға болатын барлық жолдардың жиыны ретінде анықталады S кесу арқылы а префикс сен, ресми түрде: сен−1S = { v ∈ Σ*: uv ∈ S }, сал. сурет 1950 жылдардың соңынан бастап әр түрлі атаулармен енгізілді.[1][2][3]Бүгінде ол информатиктің есімімен аталады Януш Бжозовский олардың қасиеттерін зерттеген және ан алгоритм жалпыланған туындысын есептеу тұрақты өрнек.[4]

Анықтама

Бастапқыда тұрақты тіркестерге арналған болса да, анықтама ерікті ресми тілдерге қолданылады ресми тіл S алфавит арқылы Σ және кез келген жол сен ∈ Σ*, туындысы S құрметпен сен ретінде анықталады:[5]

сен−1S = { v ∈ Σ*: uv ∈ S }

Мұны айтудың баламалы тәсілі - бәріне бірдей сен,v ∈ Σ*:

v ∈ сен−1S iff uv ∈ S

бұл нота үшін кейбір интуицияны қамтамасыз етеді.

Анықтамадан, барлығы үшін сен,v,w ∈ Σ*:

v ∈ (uw)−1S iff uwv ∈ S iff wv ∈ сен−1S iff v ∈ w−1(сен−1S)

сондықтан (uw)−1S = w−1(сен−1S).

Еркін жолға қатысты туынды осы жолдың шартты белгілеріне байланысты туындыларды азайтады, өйткені, үшін а∈ Σ, сен∈ Σ*:

(уа)−1S= а−1(сен−1S)     
ε−1S= S

Тіл L⊆ Σ* аталады нөлдік егер онда бос жол болса, яғни ε ∈ L. Әр тіл S оның туындыларының нөлдік қасиетімен анықталады:

w ∈ S iff ε ∈ w−1S

Тілді логикалық таңбаланған (мүмкін шексіз) ретінде қарастыруға болады ағаш (тағы қараңыз) ағаш (жиындар теориясы) және шексіз ағаш автомат ). Әрбір мүмкін жол w ∈ Σ* екілік белгісі бар ағаштағы орынды білдіреді шын қашан w ∈ S және жалған қашан w ∉ S. Бұл интерпретацияда символға қатысты туынды а шетінен өту арқылы алынған кіші ағашты есептеуге сәйкес келеді а. Ағашты тамырға және бұтақтарға ыдырату а−1S кез-келген ресми тілде қолданылатын келесі теңдікке сәйкес келеді S⊆ Σ*:

S = ({ε} ∩S) ∪ ⋃а∈Σ а(а−1S).

Жалпыланған тұрақты тіркестердің туындылары

Тіл тұрақты тіркесте берілгенде, туынды ұғымы берілген сөздің тұрақты тіркеске жататындығын шешудің алгоритміне әкеледі.

Ақырлы берілген алфавит A рәміздер,[6] а жалпыланған тұрақты өрнек -дан бастап мүмкін болатын шексіз жолдардың шексіз жиынтығын білдіреді A. Ол келесіден тұруы мүмкін:

  • ∅ (жолдардың бос жиынын білдіретін),
  • ε (бос жолдан тұратын синглтон жиынтығын белгілейді),
  • символ а бастап A (бір таңбалы жолдан тұратын синглтон жиынтығын белгілейді а),
  • R∨S (қайда R және S өз кезегінде жалпыланған тұрақты тіркестер; олардың жиынтығын білдіретін),
  • R∧S (қиылысын белгілейді R және S орнатылған),
  • ¬R (-ның толықтауышын білдіріп тұр R таңбаларының барлық жолдарының жиынтығына қатысты орнатылған A),
  • RS (-ден) мүмкін болатын жолдар тізбегінің жиынтығын белгілейді R және S орнатылған),
  • R* (жиынын білдіретін n-ден бастап жолдарды қайталау R кез келген үшін орнатылған nБос жолды қосқанда ≥0).

Қарапайым тұрақты өрнекте ∧ де, ¬ де рұқсат етілмейді, жалпыланған тұрақты өрнекпен белгіленген жолдар жиыны R оның деп аталады тілдеп белгіленді L(R).

Есептеу

Кез келген берілген жалпыланған тұрақты өрнек үшін R және кез келген жол сен, туынды сен−1R қайтадан жалпыланған тұрақты тіркес.[7]Ол келесідей рекурсивті түрде есептелуі мүмкін.[8]

(уа)−1R= а−1(сен−1R) таңба үшін а және жіп сен
ε−1R= R

Алдыңғы екі ережені пайдаланып, ерікті жолға қатысты туынды бір таңбалы жолға қатысты туындымен түсіндіріледі аСоңғысын келесідей есептеуге болады:[9]

а−1а= ε
а−1б= ∅әр белгі үшін б≠а
а−1ε= ∅
а−1∅= ∅
а−1(R*)= (а−1R) R*
а−1(RS)= (а−1R)S ∨ ν (R)а−1S
а−1(R∧S)= (а−1R) ∧ (а−1S)
а−1(R∨S)= (а−1R) ∨ (а−1S)
а−1(¬R)= ¬(а−1R)

Міне, ν (R) - бұл егер. бос жолына бағалайтын жалпыланған тұрақты өрнек беретін көмекші функция R тілінде ε болады, ал басқаша жағдайда ∅ деп бағаланады. Бұл функцияны келесі ережелермен есептеуге болады:[10]

ν (а)= ∅кез келген белгі үшін а
ν (ε)= ε
ν (∅)= ∅
ν (R*)= ε
ν (RS)= ν (R) ∧ ν (S)
ν (R ∧ S)= ν (R) ∧ ν (S)
ν (R ∨ S)= ν (R) ∨ ν (S)
ν (¬R)= εегер ν (R) = ∅
ν (¬R)= ∅егер ν (R) = ε

Қасиеттері

Жіп сен - жалпыланған тұрақты өрнекпен белгіленген жолдар жиынтығының мүшесі R егер және ε туындымен белгіленген жолдар жиынтығының мүшесі болса ғана сен−1R.[11]

Бекітілген жалпыланған тұрақты тіркестің барлық туындыларын ескере отырып R тек әр түрлі тілдерде нәтиже береді. Егер олардың саны арқылы белгіленсе г.R, барлық осы тілдерді туынды ретінде алуға болады R төмендегі ұзындыққа қатысты г.R.[12] Сонымен бірге толық детерминирленген ақырлы автоматы бар г.R арқылы берілген тұрақты тілді мойындайтын мемлекеттер R, белгілегендей Myhill – Nerode теоремасы.

Контекстсіз тілдердің туындылары

Сондай-ақ, туындылар эквивалентті тұрақты өрнек операторлары бар рекурсивті анықталған теңдеулер үшін тиімді есептеледі контекстсіз грамматика. Бұл түсінік контекстсіз тілдерге арналған алгоритмдерді талдау үшін пайдаланылды.[13]Осындай алгоритмдерді жүзеге асыру текше күрделілікке ие болды,[14]күрделілігіне сәйкес келеді Эрли талдаушысы жалпы контекстсіз грамматика туралы.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Джордж Н. Рэни (1958 ж. Сәуір). «Тізбектелген функциялар». ACM журналы. 5 (2): 177–180.
  2. ^ Дана Скотт пен Майкл Рабин (1959 ж. Сәуір). «Шекті автоматтар және оларды шешуге арналған мәселелер» (PDF). IBM Journal of Research and Development. 3 (2): 114–125.
  3. ^ C.C. Элгот пен Дж.Д.Рутледж (1961 ж. Қазан). «Ақырлы автоматтардағы операциялар». Роберт С. Ледлиде (ред.) Proc. AIEE 2 анн. Симптом. коммутация, тізбек теориясы және логикалық дизайн (SWCT), Детройт. 129-132 бет. дои:10.1109 / FOCS.1961.26.
  4. ^ Януш А.Бжозовский (1964). «Тұрақты өрнектердің туындылары». J ACM. 11 (4): 481–494. дои:10.1145/321239.321249.
  5. ^ Януш А.Бжозовский (1964). «Тұрақты өрнектердің туындылары». J ACM. 11 (4): 481–494. дои:10.1145/321239.321249.
  6. ^ Бжозовский (1964), 488 бет, қажет A 2-ден тұрадыn комбинациялары n биттер, кейбіреулер үшін n.
  7. ^ Бжозовский (1964), 488 бет, Теорема 4.1
  8. ^ Бжозовский (1964), 488 бет, 3.2 теорема
  9. ^ Бжозовский (1964), 488 бет, Теорема 3.1
  10. ^ Бжозовский (1964), 488-бет, Анықтама 3.2
  11. ^ Бжозовский (1964), 488 бет, Теорема 4.2
  12. ^ Бжозовский (1964), 484 бет, 4.3 теорема
  13. ^ Мэтью Майт; Дэвид Дарайс; Даниэль Спивак (2011). Туындылармен талдау: функционалды меруерт. 16-шы ACM SIGPLAN функционалды бағдарламалау жөніндегі халықаралық конференцияның материалдары (ICFP). 189–195 бб. дои:10.1145/2034773.2034801.
  14. ^ Майкл Д. Адамс; Селесте Холленбек; Мэттью Майт (2016). Туындылармен талдаудың күрделілігі мен өнімділігі туралы. Бағдарламалау тілін жобалау және енгізу бойынша 37-ші ACM SIGPLAN конференциясының материалдары (PLDI). 224–236 бб. дои:10.1145/2908080.2908128.