А.А. Вылиток - Операции над формальными языками (1115014)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

А. А. ВылитокОперации над формальными языкамиФормальный язык L над алфавитом Σ — это подмножество множествавсех цепочек в алфавите Σ, L ⊆ Σ*.Над языками можно выполнять обычные теоретико-множественныеоперации(объединение,пересечение,разность).Крометеоретикомножественных, введем еще несколько специальных операций над языками.)Пусть L, L1, L2 — языки над алфавитом Σ. Определим операции1 :1) L1 ∪ L22) L1 ∩ L23) L1 − L2— объединение L1 и L2;— пересечение L1 и L2;— разность L1 и L2;4) L = Σ* − L — дополнение L (до Σ*);)5) L1·L2 = {ϕψ | ϕ ∈ L1, ψ ∈ L2} — сцепление2 L1 и L2;⎧ {ε }, i = 0,6) Li = ⎨— i-я степень L;i −1⎩ L = L ⋅ L, i ≥ 1*7) L =8) L+ =∞n— итерация L;n— усеченная итерация L;ULn =0∞ULn =19) Подстановка L1, ..., Ln в L вместо a1, ..., an ∈ Σ, где Li ⊆ Σi* есть операцияSubst(L; a1, ..., an | L1, ..., Ln) = { χi1, ..., χik | ai1 ...

aik ∈L, χij ∈ Lj} ∪ L′, гдеL′ = {ε}, если ε ∈ L, и L′ = ∅, если ε ∉ L.Операции позволяют конструировать новые языки из набора заданных.Пусть, например, L1 = {a, ab, bb}, L2 = {aa, ba, ab, b}, L3 = {abab, aa}. Тогдавыражение (L1 ∩ L2)* − L3 задает язык L = {(ab)n | n ≥ 0, n ≠ 2}.Множество языков называют классом. Например, класс контекстносвободных (КС) языков состоит из всех языков, порождаемых КС-грамматиками.Говорят, что класс языков C замкнут относительно операции θ, если для любыхязыков из C результат операции θ также принадлежит C.Покажем, что класс КС-языков замкнут относительно операцийобъединения, сцепления и итерации.

Для каждой из этих операций достаточноуказать способ — как из КС-грамматик, порождающих исходные языки,построить КС-грамматику, порождающую язык, являющийся результатомоперации. Будем считать, что множества нетерминалов исходных грамматик непересекаются. Этого всегда можно добиться переименованием нетерминальныхсимволов (имена нетерминалов на порождаемый грамматикой язык не влияют).Пусть G1 = (T1, N1, P1, S1), G2 = (T2, N2, P2, S2) — КС-грамматики,N1 ∩ N2 = ∅. Построим грамматику G, такую что:1)2)Знаки равенства во всех пунктах этого определения следует читать как «равно поопределению».Эту операцию называют также конкатенацией, иногда — (прямым) произведениемязыков.

Знак операции «·» может быть опущен.а) L(G) = L(G1) ∪ L(G2):G = (T1 ∪ T2, N1 ∪ N2 ∪ {S}, P1 ∪ P2 ∪ {S → S1 | S2}, S), S ∉ N1 ∪ N2;б) L(G) = L(G1)L(G2):G = (T1 ∪ T2, N1 ∪ N2 ∪ {S}, P1 ∪ P2 ∪ {S → S1S2}, S), S ∉ N1 ∪ N2;в) L(G) = L(G1)*:G = (T1, N1 ∪ {S}, P1 ∪ {S → S1S | ε}, S), S ∉ N1.Класс КС-языков не замкнут относительно операции пересечения.Например, язык {an bn cn | n ≥ 0}, не являющийся контекстно-свободным, можетбыть получен пересечением двух КС-языков: {ak bk ci | i, k ≥ 0 } и {am bj cj |j, m ≥ 0}. Класс КС-языков не замкнут относительно операции вычитания(разности).

Это нетрудно доказать, учитывая, что пересечение выражается черезобъединение и разность.Задача. Показать, что класс КС-языков замкнут относительно операцииподстановки.Пример. С помощью операций над языками построим КС-грамматику G,порождающую все непустые цепочки в алфавите {a, b}, кроме цепочки bb.Заданный язык можно представить так: L = {a, b}+ − {bb}.вспомогательные языки, и КС-грамматики, их порождающие.L1 = {a, b}+L2 = {a, b}L3 = {aa, ab, ba, bb}L4 = L3L1L5 = {aa, ab, ba}G1:G2:G3:G4:G5:S1 → aS1 | bS1 | a | bS2 → a | bS3 → aa | ab | ba | bbS4 → S3S1S5 → aa | ab | baРассмотримL (G1) = L1L (G2) = L2L (G3) = L3L (G4) = L4L (G5) = L5Язык L1 представляет собой множество всех непустых цепочек в алфавите {a, b},L2 — множество всех однобуквенных цепочек, L3 — множество всехдвухбуквенных цепочек, L4 — множество всех цепочек длины не меньшей трех,L5 — множество всех двухбуквенных цепочек, кроме bb.

Язык L являетсяобъединением языков L2, L5,L4: L = L2 ∪ L5 ∪ L4. Построим грамматику G для L,используя уже построенные грамматики для вспомогательных языков.G:S → S2 | S5 | S4S2 → a | bS5 → aa | ab | baS4 → S3S1S3 → aa | ab | ba | bbS1 → aS1 | bS1 | a | bДля языка L можно построить и регулярную грамматику:SS1S2S3S4→ a | b | aS1 | bS2 | aS3 | bS3→a|b→a→ aS4 | bS4→ aS4 | bS4 | a | b.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы