Задачи - Формальные грамматики и языки. Элементы теории трансляции

Задачи(Приложение к учебному пособию«Формальные грамматики и языки. Элементы теории трансляции»)I. Порождающие грамматики. Языки, порождаемые грамматиками.Классификация грамматик и языков по Хомскому1. Дана грамматика. Построить вывод заданной цепочки.a)S → T | T+S | T−ST → F | F*TF→a|bЦепочка a−b*a+bb)S → aSBC | abCCB → BCbB → bbbC → bccC → ccЦепочка aaabbbccc2. Построить все сентенциальные формы для грамматики с правилами:S → A+B | B+AA→aB→b3.

К какому типу по Хомскому относится данная грамматика? Какой язык онапорождает? Каков тип языка? Указать ммаксимаьно возможный номер типа грамматки иязыка.a) S → APAP→+|−A→a|bb) S → A | SA | SBA→aB→bc) S → 1BB → B0 | 1d) S → aQb | εQ → cSce) S → a | BaB → Bb | bf) S → AbA → Aa | bag) S → 0A1 | 010A → 00A1A → 01h) S → ABAB → BAA→aB→bi) S → A | BA → aAb | 0B → aBbb | 1j) S → 0A | 1SA → 0A | 1BB → 0B | 1B | ⊥k) S → 0S | S0 | DD → DD | 1A | εA → 0B | εB → 0A | 0l) S → 0A | 1S | εA → 1A | 0BB → 0S | 1Bm) S → SS | AA → a | bbn) S → AB⊥A → a | cAB → bAo) S → aBA | εB → bSAAA → cp) S → Ab | cA → BaB → cSr)1. S → KF2.

K → KB | CB3. C → CA | DA4. DA → aAD5. Aa → aA6. DB → bBDs)1.2.3.4.5.t)S → aAcaA → aaBbC | abBb → bb | abbbc | aDbbbccC→cD → abu)S → 0A10A → 0B1 | 0B1 → 0C11 | 01C → 0D | 00D1 | 0D → 017.8.9.10.11.12.S → DCD → aDA | bDB | aA |bBAC → aCBC → bCAa → aABb → bBAb → bADF → EBE → EbAE → EabE → b6.7.8.9.Ba → aBAb → bABb → bBC→ε4. Построить грамматику, порождающую язык :a) L = { an bm | n, m ≥ 1}b) L = { αcβcγc | α, β, γ — любые цепочки из a и b}c) L = { a1 a2 ... an an ... a2 a1 | ai = 0 или 1, n ≥ 1}d) L = { 0n 1[n/2], n≥1}e) L = { cancbmcn, n≥0, m ≥ 0 }f) L = { an bm | n ≠ m ; n, m ≥ 0}g) L = { цепочки из 0 и 1 с неравным числом 0 и 1}h) L = { αα | α ∈ {a, b}+}i) L = { ω | ω ∈ {0, 1}+ и содержит равное количество 0 и 1, причем любаяподцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}.j) L = { (a2m bm)n | m ≥ 1, n ≥ 0}nk) L = { a 3 +1 ⊥ | n ≥ 1}2l) L = { a n | n ≥ 1}3m) L = { a n +1 | n ≥ 1}Каков тип этой грамматики? Каков тип языка?5.

К какому типу по Хомскому относится данная грамматика (указать максимальновозможный номер)? Какой язык она порождает? Каков тип языка? Выписать грамматику,в состав которой входит только один нетерминал – цель грамматики, подтверждающуюответ.a)S → AB | ASBb)S → 1A0A→a1A → 11A0 | 01aB → bbB → bb6. Эквивалентны ли грамматики с правилами :а) S → ABA → a | AaB → b | BbиS → AS | SB | ABA→aB→bb) S → aSL | aLL → KccK → KcK→bиS → aSBc | abccB → BcbB → bb7. Построить КС-грамматику, эквивалентную грамматике с правилами:а) S → aAbaA → aaAbA→εb) S → AB | ABSAB → BABA → ABA→aB→b8.

Построить регулярную грамматику, эквивалентную грамматике с правилами:а) S → A | ASA → a | bbb) S → A.AA → B | BAB→0|19. Привести пример грамматики, все правила которой имеют видA → Bt,либо A → t B,либо A → t,для которой не существует эквивалентной регулярной грамматики.10. Доказать, что грамматика с правилами:S → aSBC | abCCB → BCbB → bbbC → bccC → ccпорождает язык L = {an bn cn | n ≥ 1}.Для этого показать, что в данной грамматике1. выводится любая цепочка вида an bn cn (n ≥ 1) и2. не выводятся никакие другие цепочки.11. Дана грамматика с правилами:a) S → S0 | S1 | D0 | D1D → H.H → 0 | 1 | H0 | H1b) S → if B then S | B = EE→B|B+EB→a|bПостроить восходящим и нисходящим методами дерево вывода для цепочки:a) 10.1001b) if a then b = a+b+b12.

Определить тип грамматики. Описать язык, порождаемый этой грамматикой.Написать для этого языка КС-грамматику.S → P⊥P → 1P1 | 0P0 | TT → 021 | 120RR1 → 0RR0 → 1R⊥→ 1⊥13. Построить регулярную грамматику, порождающую цепочки в алфавите{a, b}, в которых символ a не встречается два раза подряд.14. Написать КС-грамматику для языка L, построить дерево вывода и левостороннийвывод для цепочки aabbbcccc.L = {a2n bm c2k | m=n+k, m>1}.15.

Построить грамматику, порождающую сбалансированные относительно круглыхскобок цепочки в алфавите { a, ( , ), ⊥ }. Сбалансированную цепочку α определимрекуррентно: цепочка α сбалансирована, еслиa) α не содержит скобок,b) α = (α1) или α= α1 α2, где α1 и α2 сбалансированы.16. Написать КС-грамматику, порождающую язык L, и вывод для цепочки aacbbbcaa вэтой грамматике.L = {an cbm can | n, m>0}.17. Написать КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 вэтой грамматике.L = {1n 0m 1p | n+p>m; n, p, m>0}.18.

Дан язык L = {13n+2 0n | n ≥ 0}. Определить его тип, написать грамматику,порождающую L. Построить левосторонний и правосторонний выводы, дерево разборадля цепочки 1111111100.19. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2,порождающим языки L1 и L2, КС-грамматики дляa) L1∪L2b) L1 * L2c) L1*Замечание: L = L1 * L2 — это конкатенация языков L1 и L2, т.е.L = { αβ | α ∈ L1, β ∈L2}; L = L1* — это итерация языка L1, т.е. объединение {ε} ∪ L1 ∪ L1*L1 ∪ L1*L1*L1∪ ...20. Написать КС-грамматику для L={ωi 2 ωi+1R | i ∈ N, ωi=(i)2 — двоичное представлениечисла i, ωR — обращение цепочки ω}. Написать КС-грамматику для языка L* (см.

задачу19 раздела I).21. Показать, что грамматикаE → E+E | E∗E | (E) | iнеоднозначна. Как описать этот же язык с помощью однозначной грамматики?22. Показать, что наличие в КС-грамматике правил видаa) A → AA | αb) A → AαA | βc) A → αA | Aβ | γгде α, β, γ ∈ (VT∪VN)*, A ∈ VN, делает ее неоднозначной. Можно ли преобразовать этиправила таким образом, чтобы полученная эквивалентная грамматика была однозначной?23.

Показать, что грамматика G неоднозначна. Какой язык она порождает? Является лиэтот язык однозначным?G: S → aAc | aBB → bcA→b24. Дана КС-грамматика G={VT, VN, P, S}. Предложить алгоритм построения множестваX={A ∈ VN | A ⇒ ε}.25. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст лиязык L(G).26. Написать приведенную грамматику, эквивалентную данной.a) S → aABS | bCACdA → bAB | cSA | cCCB → bAB | cSBb) S → aAB | EA → dDA | εB → bE | fC → cS | cC → cAB | dSD | aD → eAE → fA | g27.

Язык называется распознаваемым, если существует алгоритм, который за конечноечисло шагов позволяет получить ответ о принадлежности любой цепочки языку. Есличисло шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма,язык называется легко распознаваемым. Доказать, что язык, порождаемыйнеукорачивающей грамматикой, легко распознаваем.28. Доказать, что любой конечный язык, в который не входит пустая цепочка, являетсярегулярным языком.29. Доказать, что нециклическая КС-грамматика порождает конечный язык.Замечание: Нетерминальный символ A ∈ VN — циклический, если в грамматикесуществует вывод A ⇒ ξ1Aξ2. КС-грамматика называется циклической, если в нейимеется хотя бы один циклический символ.30.

Показать, что условие цикличности грамматики (см. задачу 29) не являетсядостаточным условием бесконечности порождаемого ею языка.31. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой,содержащей хотя бы один эффективный циклический символ, бесконечен.Замечание: Циклический символ называется эффективным, если A ⇒ αAβ, где |αAβ| >1; иначе циклический символ называется фиктивным.II.

Регулярные грамматики, ДС, анализаторы по ДС.Преобразование НКА к ДКА1. Дана регулярная грамматика с правилами:S → S0 | S1 | P0 | P1P → N.N → 0 | 1 | N0 | N1.Построить по ней диаграмму состояний и использовать ДС для разбора цепочек: 11.010 ,0.1 , 01. , 100 . Какой язык порождает эта грамматика ?2. Дана ДС.a) Осуществить разбор цепочек 1011⊥ , 10+011⊥ и 0−101+1⊥ .b) Восстановить регулярную грамматику, по которой была построена данная ДС.c) Какой язык порождает полученная грамматика ?0,10,1H⊥AS0,1+, ?BER3. Пусть имеется переменная c и функция gc(), считывающая в с очередной символанализируемой цепочки.

Дана ДС с действиями:выходвходprintf(“%d”,b)⊥gc()Hgc()0,1b=c? ’0’; gc()N0,1b=2*b+c? ’0’; gc();a) Определить, что будет выдано на1+101//p11+++1000/5⊥?b) Написать на Си анализатор по этой ДС.печатьприразборецепочки4. Написать регулярную леволинейную грамматику для заданного языка, по ней построитьДС, а по ДС — программу анализатора.a) L = { x α y ⊥ | α ∈ {x, y}*}b) L = { (x y3)n ⊥ | n ≥ 1 }с) L = {(abb)k⊥| k ≥ 1}d) L = {ω⊥ | ω ∈ {0,1}* , где за каждой 1 непосредственно следует 0}e) L = {1ω1⊥ | ω ∈ {0,1}+ , где все подряд идущие 0 – подцепочки нечетной длины}5. Дана регулярная грамматика:S → A⊥A → Ab | Bb | bB → AaОпределить язык, который она порождает; построить ДС; написать на Си анализатор.6.

Построить ДС, по которой в заданном тексте, оканчивающемся на ⊥, выявляются всепарные комбинации <>, <= и >= и подсчитывается их общее количество.7. Написать на Си анализатор, выделяющий из текста вещественные числа без знака (ониопределены как в Паскале) и преобразующий их из символьного представления вчисловое.8. Написать на Си анализатор, выделяющий из текста вещественные числа без знака (ониопределены как в Паскале) и преобразующий их из символьного представления вчисловое.9. Даны две грамматики G1 и G2.G1: S → 0C | 1BB → 0B | 1C | εC → 0C | 1CL1 = L(G1);G2: S → 0D | 1BB → 0C | 1CC → 0D | 1D | εD → 0D | 1DL2 = L(G2).Построить регулярную грамматику для:a) L1∪L2b) L1∩L2c) L1* \ {ε}d) L2* \ {ε}e) L1∗L2Если разбор по ней оказался недетерминированным, построить эквивалентную ейграмматику, допускающую детерминированный разбор.10.

Написать леволинейную регулярную грамматику,праволинейной, допускающую детерминированный разбор.a) S → 0S | 0BB → 1B | 1CC → 1C | ⊥эквивалентнуюданнойb) S → 0BB → 1C | 1SC→⊥c) S → aBB → aC | aD | dBC → aBD→⊥11. Для данной грамматикиa) определить ее тип;b) какой язык она порождает;c) написать Р-грамматику, почти эквивалентную данной;d) построить ДС и анализатор на Си.S → 0S | S0 | DD → DD | 1A | εA → 0B | εB → 0A | 012. Построить ДС, соответствующую заданной леволинейной регулярной грамматике.Если ДС задает НКА, то преобразовать НКА к ДКА, используя алгоритм преобразования.По получившемуся ДКА написать анализатор.