И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 18

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

Текст из файла (страница 18)

Эквивалентны ли грамматики с правилами:а) 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. Построить регулярную грамматику, эквивалентную грамматике с правилами:а) 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  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  1RR 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 вэтой грамматике.n m 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. Метод рекурсивного спуска. КС-грамматики с действиями15. По данной грамматике G1 построить регулярную грамматику G2 для языка L1L1 (см. замечание к задаче 19 раздела I ), где L1  L(G1); по грамматике G2 построить ДС и анализатор.G1:S  S1 | A1A  A0 | 016. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например, ...

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

Список файлов книги