Задачи - Формальные грамматики и языки. Элементы теории трансляции (1115026)
Текст из файла
Задачи(Приложение к учебному пособию«Формальные грамматики и языки. Элементы теории трансляции»)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. Построить ДС, соответствующую заданной леволинейной регулярной грамматике.Если ДС задает НКА, то преобразовать НКА к ДКА, используя алгоритм преобразования.По получившемуся ДКА написать анализатор.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
