И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 17
Текст из файла (страница 17)
Грамматики и языки. Классификация по Хомскому4. Построить грамматику, порождающую заданный язык L. Каков тип построенной грамматики? Каков тип языка?n ma) L = { a b | n, m ≥ 1};*b) L = { αcβcγc | α, β, γ ∈ {a,b} (т.е. α, β, γ — любые цепочки из a и b)};c) L = { a1 a2 ... an an ... a2 a1 | ai ∈{ 0, 1}, n ≥ 1};nd) L = { 0 1[n/2]n| n≥1};m ne) L = { ca cb c | n≥0, m≥0 };n mf) L = { a b | n ≠ m ; n, m ≥ 0};*g) L = { ω | ω ∈ {0,1} , |ω|0 ≠|ω|1 } (т.е.
все цепочки из 0 и 1 с неравным числом 0 и 1);h) L = { αα | α ∈ {a,b}+};*i) L = { ω | ω ∈ {0,1}+, |ω|0 = |ω|1, ∀ x,y∈ {0,1} : ω = xy ⇒(т.е. все непустые цепочки,| x |1 ≤ | x |0}содержащие равное количество 0 и 1, причем любая подцепочка,взятая с левого конца, содержит единиц не больше, чем нулей) ;j) L = { ω1ω2…ωn | n ≥ 0, ωi ∈{ a 2m b m | m ≥ 1} для 1≤ i≤ n };na 3 +1 ⊥ | n ≥ 1};n2L = { a | n ≥ 1};k) L = {l)m) L = {3a n +1 | n ≥ 1}.5.
К какому типу по Хомскому относится данная грамматика (указать максимально возможный номер)? Какой язык она порождает? Каков тип языка? Выписать подтверждающую ответ грамматику, в состав которой входит только один нетерминал — цель грамматики.a)S → AB | ASBA→aaB → bbB → bbb)S → 1A01A → 11A0 | 016. Эквивалентны ли грамматики с правилами:а) S → ABA → a | AaB → b | BbиS → AS | SB | ABA→aB→bb) S → aSL | aLL → KccK → KcK→bиS → aSBc | abccB → BcbB → bb95Задачи / I. Грамматики и языки. Классификация по Хомскому7. Построить КС-грамматику, эквивалентную грамматике с правилами:а) S → aAbaA → aaAbA→εb) S → AB | ABSAB → BABA → ABA→aB→b8.
Построить регулярную грамматику, эквивалентную грамматике с правилами:b) S → A.AA → B | BAB→0|1а) S → A | ASA → a | bb9. Привести пример грамматики, каждое правило которой относится к одному из трех вилибо A → t, для которой не существуетдовA → Bt,либо A → t B,эквивалентной регулярной грамматики.10. Доказать, что грамматика с правилами:S → aSBC | abCCB → BCbB → bbbC → bccC → ccn n nпорождает язык L = {a b c | n ≥ 1}.Для этого показать, что в данной грамматике:n n nI ) выводится любая цепочка вида a b c (n ≥ 1) иII ) не выводятся никакие другие цепочки.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⊥96Задачи / I. Грамматики и языки. Классификация по Хомскому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 вэтой грамматике.nmnL = {a cb ca | n,m > 0}.17. Построить КС-грамматику, порождающую язык L, и вывод для цепочки 110000111 вэтой грамматике.nm pL = {1 0 1 | n + p >m; n, p, m > 0}.18. Дан язык L = {13n+2 0 n | n ≥ 0}. Определить его тип, построить грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки1111111100.19. Найти общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики дляa) L1∪L2 ;b) L1 ⋅ L2 ;c) 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).21. Показать, что грамматикаE → E+E | E∗E | (E) | iнеоднозначна. Как описать этот же язык с помощью однозначной грамматики?97Задачи / I.
Грамматики и языки. Классификация по Хомскому22. Показать, что наличие в приведенной КС-грамматике правил видаa) A → AA | αb) A → AαA | βc) A → αA | Aβ | γ,где α, β, γ ∈ (T∪N)∗, A ∈ N, делает ее неоднозначной. Можно ли преобразовать эти правилатаким образом, чтобы полученная эквивалентная грамматика была однозначной?23. Показать, что грамматика G неоднозначна. Какой язык она порождает? Является ли этотязык однозначным?G: S → aAc | aBB → bcA→b24. Дана КС-грамматика G = 〈T, N, P, S 〉.
Предложить алгоритм построения множестваX = {A ∈ N | A ⇒ ε}.25. Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст лиязык L(G).26. Построить приведенную грамматику, эквивалентную данной КС-грамматике.a) S → aABS | bCACdA → bAB | cSA | cCCB → bAB | cSBC → cS | cb) S → aAB | EA → dDA | εB → bE | fC → cAB | dSD | aD → eAE → fA | g27. Построить неукорачивающую КС-грамматику, эквивалентную данной, применив алгоритм устранения правил с пустой правой частью.S → aS | Sa | CC → CC | bA | εA → aB | εB → aA | a28. Язык называется распознаваемым, если существует алгоритм, который за конечное число шагов позволяет получить ответ о принадлежности любой цепочки этому языку.
Есличисло шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма,язык называется легко распознаваемым. Доказать, что язык, порождаемый неукорачивающей грамматикой, легко распознаваем.29. Доказать, что любой конечный язык является регулярным языком.30. Доказать, что нециклическая КС-грамматика порождает конечный язык.ЗамечаниеНетерминальный символ A ∈ N — циклический, если в грамматике существует вывод A ⇒ξ1Aξ2. КС-грамматика называется циклической, если в ней имеется хотя бы один циклическийсимвол.98Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС31. Показать, что условие цикличности грамматики (см.
задачу 29) не является достаточнымусловием бесконечности порождаемого ею языка.32. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содержащей хотя бы один эффективный циклический символ, бесконечен.ЗамечаниеЦиклический символ называется эффективным, если 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,1HAS0,1+,−ER⊥B3. Пусть имеется переменная c и функция gc(), считывающая в с очередной символ анализируемой цепочки. Дана ДС с действиями:printf(”%d”,b);gc( );HS0,1b=c−’0’;gc( );gc( );a)0,1b=2*b+c−’0’;gc( );Определить, что будет выдано1+101/ /p11+++1000 /5 ⊥ .напечатьприразборецепочки99Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДСb) Написать на Си ++ анализатор по этой ДС.4. Построить регулярную (автоматную) леволинейную грамматику для заданного языка, поней построить ДС, а по ДС — написать программу анализатора:a) L = { xαy ⊥ | α ∈ {x, y}∗} ;nb) L = { (xy 3) ⊥ | n ≥ 1 } ;kс) L = {(abb) ⊥| 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 | 1CПустьдля:L1 = L(G1),G2: S → 0D | 1BB → 0C | 1CC → 0D | 1D | εD → 0D | 1DL2 = L(G2). Построить регулярную (автоматную) грамматикуa) L1∪L2b) L1∩L2*c) L1 \{ε}*d) L2 \ {ε}e) L1⋅L2Если разбор по ней оказался недетерминированным, построить эквивалентную ей грамматику, допускающую детерминированный разбор.100Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДС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. Построить ДС, соответствующую заданной леволинейной автоматной грамматике. ЕслиДС задает НКА, то построить эквивалентный ему ДКА, используя алгоритм.
Для полученного ДКА построить анализатор. Построить соотвествующую ДКА грамматику.a)S → Sa | Ab | bA → Ab | Sa | ab)S → Sb | Aa | aA → Sb | a | bc)S → C⊥C → A1 | B1 | 1A → A1 | C0 | 0B → C0 | 0d)S → A⊥A → Bb | aB → Bb | be)S → B0 | C0B → B0 | 0C → C1 | A1A→0f)S → Bb | CcB → Bb | AbC → Cc | AbA→ag)S → S1 | A0A → B1 | C1B → A0C → C0 | 0h)S → Sa | Cc | aC → BbB → Sa | a101Задачи / II. Регулярные грамматики, конечные автоматы, разбор по ДСi)S → C⊥C → A1 | B1 | 1A → A1 | C0 | 0B → C0 | 0j)S → A⊥A → Bb | aB → Bb | bk)S → C⊥B → B1 | 0 | D0C → B1 | C1D → D0 | 0l)S → C⊥C → B1B → 0 | D0D → B1m)S → A0A → A0 | S1 | 0n)S → B0 | 0B → B0 | C1 | 0 | 1C → B0o)S → A0 | A1 | B1 | 0 | 1A → A1 | B1 | 1B →A0p)S → S0 | A1 | 0 | 1A → A1 | B0 | 0 | 1B → A0r)S → Sb | Aa | a | bA → Aa | Sb | a13. Грамматика G определяет язык L =L1∪L2, причем L1∩ L2 =∅.
Построить регулярную (автоматную) грамматику G1, которая порождает язык L1⋅L2 (см. замечание к задаче 19 раздела I). Длянее построить ДС и анализатор.S → A⊥A → A0 | A1 | B1B → B0 | C0 | 0C → C1 | 114. Даны две грамматики G1 и G2, порождающие языки L1 и L2.G1: S → S1 | A0A → A1 | 0G2: S → A1 | B0 | E1A → S1B → C1 | D1C→0D → B1E → E0 | 1Построить регулярные (автоматные) грамматики для языковa) L1 ∪ L2 ;b) L1 ∩ L2 ;c) L1 ⋅ L2(см. замечание к задаче 19 раздела I) .Для полученной грамматики построить ДС и анализатор.102Задачи / III.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
