Карпов. СодержаниеПредислови Конечные автоматы
 Скачать 1.07 Mb.
|
|
3.4. Автоматные грамматики 3.4.1. а) Справедливо ли утверждение, что любое подмножество регулярного языка регулярно? б) Справедливо ли утверждение, что у любого контекстно-свободного языка существует подмножество, которое является регулярным языком? Приведите примеры, подтверждающие вашу точку зрения. 3.4.2. Cледующая КС-грамматика: S ABC A aA | a B Bb | C Cc |c порождает язык {a n b m c k | n, k > 0, m 0}. Постройте автоматную грамматику, порождающую тот же язык. 3.4.3. Постройте автоматную грамматику, порождающую язык, задаваемый регулярным выражением 1*10(0+1)*. По этой грамматике постройте недетерминированный конечный автомат, по нему постройте детерминированный конечный автомат, распознающие тот же самый язык. 3.4.4. Грамматика Хомского называется праволинейной, если ее правила имеют вид: A A A где - произвольная (в том числе и пустая) цепочка терминальных символов. Докажите, что по любой праволинейной грамматике может быть построена эквивалентная автоматная грамматика Хомского. Покажите, как преобразовать праволинейную грамматику: S abcA | c A acB | a B bcbaB | к автоматной грамматике. 3.4.5. Постройте детерминированный конечный автомат, распознающий тот же язык, который порождается следующей грамматикой Хомского: S a | aT T a | b | aT | bT Порождается ли слово abab в этой грамматике? 30 3.4.6. Идентификаторы в языке Фортран представляются от одного до шести символов, первый из которых – буква, а остальные – буквы или цифры. Постройте автоматную грамматику и конечный автомат, задающие язык идентификаторов Фортрана. 31 4. Иерархия распознающих автоматов для порождающих грамматик Хомского 4.1. Автоматные грамматики и конечные автоматы 4.1.1. По заданной грамматике G типа 3 постройте конечный автомат, распознающий тот же язык, который порождает грамматика G. Постройте регулярное выражение, описывающее все цепочки этого языка. 4.1.2. По регулярному выражению R=10*1*(0+1)* постройте конечный автомат- распознаватель A(R) соответствующего регулярного языка, по автомату A(R) постройте грамматику типа 3, которая порождает тот же язык. 4.1.3. По регулярному выражению R=0*(0+1)*0*11* постройте детерминированный конечный автомат-распознаватель соответствующего регулярного языка, по этому автомату постройте грамматику типа 3, которая порождает тот же язык. Постройте регулярное выражение, описывающее все цепочки этого языка. Совпадает ли оно с R? 4.1.4. Постройте грамматику типа 3, порождающую все такие цепочки из 0 и 1, которые содержат хотя бы один символ. 4.1.5. Дано регулярное выражение в стандартной нотации, описывающее все действительные числа: (\+|-|)digit* digit+([eE](\+|-|) digit+), где digit = [0-9] По этому регулярному выражению постройте грамматику типа 3, порождающую такие числа. Постройте также детерминированный конечный автомат, распознающий все такие цепочки. 4.1.6. Постройте регулярное выражение, определяющее тот же автоматный язык, который порождается следующей грамматикой типа 3: G = { S aS, S A, S , A bA, A S} 4.1.7. Постройте грамматику Хомского типа 3, которая порождает тот же автоматный язык, который задается следующим регулярным выражением: R = (a + c + ba + bc)* (b+ ) 4.1.8. Над алфавитом {a, b, c} задана следующая автоматная порождающая грамматика: S aS | aB | cS | c B bB | aB | a Постройте детерминированный конечный автомат, распознающий язык, порождаемый этой грамматикой. 32 4.2. Контекстно-свободные грамматики и МП-автоматы 4.2.1. Постройте МП-автомат, распознающий цепочки языка {a n b n | n 0}. 4.2.2. Постройте МП-автомат, распознающий цепочки языка {a n b 2n | n 0}. 4.2.3. Постройте МП-автомат, распознающий такие цепочки над словарем {a, , b}, в которых количество вхождений символов а вдвое больше числа вхождений символа b. 4.2.4. Постройте КС-грамматику и МП-автомат, распознающий такие цепочки над словарем {a, , b}, в которых число вхождений символа a не превышает числа вхождений символа b. 4.2.5. Постройте МП-автомат, распознающий язык правильных скобочных выражений. Например, цепочка “(( ) ( ( ) ) ( )” принадлежит этому языку, а цепочка “) ( ) ) )” –нет. 4.2.6. Язык Дика (Dyck language) порядка n – это язык правильных скобочных выражений с n типами различных скобок. Например, при n=2 цепочкой такого языка может быть „[ ( ) ( [ ( ) ( ) ] )]. Постройте порождающую грамматику Хомского для языка Дика порядка 3 и МП- автомат, его распознающий. 4.2.7. Постройте порождающую грамматику Хомского для языка правильных скобочных выражений глубины не более 3, в которых в квадратных скобках стоит выражение только из круглых скобок, а в фигурных скобках обязательно стоят квадратные скобки. 4.2.8. Постройте МП-автомат, переводящий арифметическое выражение, заданное в инфиксной форме, в эквивалентное выражение в префиксной форме. 4.3. Машины Тьюринга как распознаватели языков 4.3.1. Постройте машину Тьюринга, распознающую язык {a n^2 | n>0}, содержащий цепочки из символов a длиной 1, 4, 9, 16, ... . Примеры цепочек языка: а, aaaa, aaaaaaaaa, ... . Указание. Воспользуйтесь соотношением (n+1) 2 = n 2 + 2n + 1. 4.3.2.Постройте машину Тьюринга, распознающую цепочки языка {a n b 2n c n | n 0}. 4.3.3. Постройте машину Тьюринга, распознающую все такие цепочки над словарем {a, , b}, в которых количества вхождений символов а и b равны. 4.3.4. Постройте машину Тьюринга, распознающую такие цепочки над словарем {a, , b}, в которых количества вхождений символов а и b не равны. 33 4.3.5. Постройте машину Тьюринга, распознающую язык правильных скобочных выражений. Например, цепочка „(( ) ( ( ) ) ( )‟ принадлежит этому языку, а цепочка „) ( ) ) )‟ –нет. 4.3.6. Постройте машину Тьюринга, распознающую все цепочки языка {ww | w {a,b}*}, т.е. цепочки, состоящие из двух произвольных повторяющихся слов. 4.3.7. Постройте машину Тьюринга, распознающую все цепочки языка {ww R | w {a,b}*}. 4.3.8. Постройте машину Тьюринга, упорядочивающую любую цепочку из нулей и единиц так, что сначала идут все нули, а затем все единицы исходной цепочки. Пример: по цепочке 011010110 должна быть выдана в качестве результата цепочка 000011111. 34 5. Другие модели задания формальных языков 5.1. БНФ-нотация и грамматики Хомского 5.1.1. В БНФ нотации определен язык формул: <формула>::=<цифра>[<цифра>] | (<формула><знак> <формула>) <знак>::=+ | - <цифра>::= 0|1|2|3|4|5|6|7|8|9 Постройте грамматику Хомского этого языка и приведите примеры его цепочек. 5.1.2. Иногда при записи грамматики в БНФ нетерминальные символы записываются словами c заглавной буквы, а терминальные выделяются апострофами „ и ‟. Запишите следующую грамматику, представленную в БНФ нотации, в стандартной записи Хомского: Program ::= Statement { „;‟ Statement } „.‟ Statement ::= Name „:=‟ Expression Expression ::= Expression Operator Expression | Name | „{‟ Elements „}‟ | „(‟ Expression „)‟ Operator ::= „ ‟ | „ ‟ Name ::= „A‟ | „B‟ | …| „X‟ | „Y‟ | „Z‟ Elements ::= Element { „,‟ Element } Element ::= „a‟ | „b‟ | … | „x‟ | „y‟ | „z‟ Постройте вывод трех цепочек, порождаемых этой грамматикой. 5.1.3. Иногда при записи грамматики в БНФ нетерминальные символы записываются словами c заглавной буквы, а терминальные выделяются апострофами „ и ‟. Запишите следующую грамматику, представленную в БНФ нотации, в стандартной записи Хомского: Prog ::= „begin‟ Stmnt { „;‟ Stmnt } „end‟ Stmnt ::= „if‟ ( Expr Rel Expr) „{‟ Stmnt { „;‟ Stmnt } „}‟ | „s‟ Rel ::= „==‟ | „!=‟ | „>‟ | „<‟ | „>=‟ | „<=‟ Exp ::= Term {AddOp Term} Term ::= Primary {MulOp Primary} Primary ::= „i‟ | „c‟ | „(„ Exp „)‟ AddOp ::= „+‟ | „-‟ MulOp ::= „*‟ | „/‟ 5.2. Сеть Петри как модель абстрактного языка 5.2.1. Какой язык порождает следующая сеть Петри? 35 5.2.2. Какой язык порождает следующая сеть Петри? 5.2.3. Постройте сеть Петри, порождающую язык, состоящий из цепочек с одинаковым числом вхождений символов a и b. 5.2.4. Постройте сеть Петри, порождающую язык, в цепочках которого число вхождений символа a больше числа вхождений символа b. 5.2.5. Постройте сеть Петри, порождающую язык, в цепочках которого число вхождений символа a вдвое больше числа вхождений символа b. 5.3. Синтаксические диаграммы и грамматики Хомского 5.3.1. Постройте КС-грамматику, порождающую тот же язык, что и следующие синтаксические диаграммы с начальным символом А: 5.4. Грамматики с рассеянным контекстом 36 5.4.1. Постройте грамматику с рассеянным контекстом, порождающую язык {ww | w {a,b}*}. Приведите вывод цепочки aabaabaa этого языка в построенной грамматике. 5.4.2. Постройте грамматику с рассеянным контекстом, порождающую язык {w R ww R | w {a,b}*}. Приведите вывод цепочки aababbabaaaabab этого языка в построенной грамматике. 37 6. Язык Милан и стековая машина 6.1. Стековая машина 6.1.1. Постройте программу стековой машины для вычисления значения арифметического выражения: a+(b-2)*(x+3) при заданном распределении памяти для констант и переменных. 6.1.2. Постройте программу стековой машины для вычисления условного оператора присваивания: a := x>y+2 ? 32 –у15 : 3+x – y1*z +v; 6.1.2. Постройте программу стековой машины, которая выполняет следующую программу языка Милан: begin m:=read; n:=read; while m≠n do if m>n then m:=m-n else n:=n-m fi od; write(m) end 6.1.3. Условное выражение состоит из отношений, связанных знаками конъюнкции и дизъюнкции. Отношение строится из двух переменных и знака отношения {=, < >, >, <, =>,<=}. Примеры цепочек языка условных выражений: x>y x<=z, x = = a x >b x 6.1.4. Оператор for языка Java имеет следующую структуру: for (<инициализация>; <условие> ; <итерация> ) <оператор>; Постройте программу стековой машины для вычисления следующей программыr: begin N := read; y:= 2; z2:= 5; for ( i := 0; i 38 6.2. Язык Милан 6.2.1. На языке Милан с грамматикой: Prog → begin L end L → S | S ; L S → i:=E | if B then L | if B then L else L | while B do L | output(E) B → E q E E → (E) | E ots E | E otm E | i | c | read построена программа вычисления факториала: begin z:=1; i:=1; while (i y) do z:=z*x; i=i+1; output(z); end Постройте все возможные деревья вывода этой программы в указанной грамматике. 6.2.2. На языке Милан с грамматикой: Prog → begin L end L → S | S ; L S → i:=E | if B then L | if B then L else L | while B do L | output(E) B → E q E E → (E) | E ots E | E otm E | i | c | read построена программа: begin m:=read; n:=read; while m>0 do if m n then if m=n then m:=m-n else n:=n-m; output(m) end Постройте все возможные деревья вывода этой программы в указанной грамматике. 6.2.3. Постройте все возможные деревья вывода для цепочки a+(b*c-d) в грамматике: E E+E | E-E | E*E | (E) | i 6.2.4. В 70-е годы прошлого века в России была построена мини-ЭВМ «Наири», на которой использовался язык АП (автоматическое программирование), использующий русские ключевые слова. Пример программы на языке АП: 1. допустим a=1 b=-3 c=2 2. введем х у 3. вычислим d= (b^2-4ac) 4. если d<0 идти к 7 5. вычислим x=(-b-d)/(2a) 6. вычислим y=(-b+d)/(2a) 7. печатаем x y 39 8. кончаем Постройте грамматику языка АП и разработайте транслятор этого языка в язык стековой машины методом рекурсивного спуска. 6.2.5. Постройте грамматику языка Милан++, пример программы на котором приведен ниже: begin read x, y; /* ввод операндов */ loop x != y -> /* выполнять до равенства аргументов */ case x > y -> x := x - y or y > x -> y := y - x esac endloop; write (x) /* полученный НОД */ end 6.2.6. На языке Милан++ построена программа: begin i,s := 0,0; n := read; loop i < n -> s,i := s+read,i+1 endloop; write (s) end постройте для этой программы соответствующую программу на языке стековой машины. Постройте синтаксические диаграммы и семантические операции для трансляции языка Милан++ методом рекурсивного спуска. 6.2.7. Постройте грамматику языка Э.Дейкстры из его книги “Дисциплина программирования”. Примеры программ на этом языке: begin q1,q2,q3,q4:=Q1,Q2,Q3,Q4; do q1>q2 q1,q2:=q2,q1; [] q2>q3 q2,q3:=q3,q2; [] q3>q4 q3,q4:=q4,q3 od end begin k,j = 0,1; do j n if f g j := j+1; [] f g k,j := j,j+1 fi; [] j = n j := j-1 od end 40 7. Неоднозначные КС - грамматики и атрибутные трансляции 7.1. Двусмысленные КС-грамматики 7.1.1. В грамматике: G1:: S if b then S | if b then S else S | s постройте несколько деревьев вывода для цепочки: if b then if b then if b then s else if b then if b then s else s Постройте несколько деревьев вывода для этой цепочки также в грамматике: G2:: S if b then S | if b then S1 else S | s S1 if b then S1 else S | s 7.1.2. Является ли следующая грамматика условных операторов однозначной: G:: S if b then S B | s B else S | Постройте в этой грамматике возможные деревья вывода для цепочек: if b then if b then s else if b then s else s, if b then if b then if b then s else if b then s else if b then s else s 7.1.3*. Следующая грамматика порождает язык условных операторов языка Паскаль: S → AX | s A → if b then s A | X → if b then s X else S | Однозначная ли эта грамматика? Постройте дерево вывода в этой грамматике цепочки: if b then if b then if b then if b then s else if b then s else s 7.1.4. В порождающей КС-грамматике c начальным нетерминалом L: L S | L; S S while b do L | s постройте все возможные деревья вывода цепочки: while b do s; while b do while b do s; s 7.1.5. Постройте несколько деревьев вывода в этой грамматике для цепочки: s; s; s; s в грамматике G:: S s | S;S Эта грамматика, порождающая последовательности операторов, разделенных точками с запятой, является двусмысленной. Неоднозначность дерева вывода в этой грамматике объясняется возможностью по-разному структурировать группу рядом стоящих операторов (правило S S;S). Постройте две недвусмысленные грамматики, порождающие последовательности операторов, которые выделяют по одному оператору из такой группы либо слева, либо справа. Постройте деревья вывода этой цепочки в построенных грамматиках. 41 7.1.6. В двусмысленной грамматике правильных скобочных выражений: S (S) | S S | неоднозначность дерева вывода объясняется возможностью по-разному структурировать группу рядом стоящих скобок (правило S S S). Постройте несколько деревьев вывода в этой грамматике для цепочки: ( ( ) ) ( ) ( ( ) ( ) ( ) ) Постройте две однозначные грамматики правильных скобочных выражений, которые выделяют по одной вложенной скобке из такой группы либо слева, либо справа. Постройте деревья вывода этой цепочки в построенных грамматиках. 7.1.7. Пусть задана грамматика упрощенного английского языка с начальным нетерминалом | and | or | but | ... < Pronoun > me | you | I | it | she | ... < Verb > is | see | sees | love | loves | feel | go | carry | went | kill | ... < Name > John | Mary | James | ... а) Постройте вывод цепочки “I like Mary and she loves me” в этой грамматике. б) Является ли эта грамматика двусмысленной? в) Если да, то приведите пример предложения с двумя различными деревьями вывода в этой грамматике. г) Постройте недвусмысленную грамматику, порождающую тот же язык. 7.1.8. Все формулы логики высказываний могут быть выражены в базисе { , 0}. Постройте недвусмысленную КС-грамматику, в которой бинарная операция импликации вычисляется справа налево. Формула A1 A2 An B понимается как (A1 (A2 (... (An B))...)). 7.1.8. КС-грамматику, задающую все формулы линейной темпоральной логики LTL часто записывают так: p | | | |