nextupprevious

Next:6.3 Формулы и программы
Up:6 Формулировки заданий
Previous:6.1 Графы и системы
 

6.2 Грамматики, языки и автоматы


1. Слово называется слабо симметричным, если его можно преобразовать в симметричное некоторой последовательностью операций обращения, применяемых к произвольным подсловам получающихся слов. Определить, является ли слабо симметричным заданное слово.

2. Задана грамматика $G$, каждое правило которой имеет вид $A\rightarrow BC$ или $A \rightarrow a$, где $A,B,C$ -- нетерминалы, а $a$ -- терминал. Определить, выводимо ли заданное слово, составленное из терминалов, в грамматике$G$.

3. $\downarrow$ Определить, пуст ли язык $L(G)$ для заданной грамматики $G$.

4. Определить, является ли бесконечным язык $L(G)$для заданной грамматики $G$.

5. $\downarrow$ Нетерминал грамматики называется бесплодным, если из него нельзя вывести ни одного слова в алфавите терминалов. Найти все бесплодные нетерминалы заданной грамматики.

6. Правило грамматики $G$ называется бесполезным, если его нельзя применить ни в одном выводе слов грамматики $G$. Найти и удалить все бесполезные правила заданной грамматики.

7. $\downarrow$ В заданной грамматике найти все нетерминалы $A$, удовлетворяющие следующему условию: из $A$ выводимо слово длиной больше 1, содержащее нетерминал $A$.

8. $\downarrow$ Говорят, что нетерминал $A$ грамматики $G$ зависит от (терминального или нетерминального) символа $s$, если из $A$ в $G$ выводимо слово, содержащее вхождение символа $s$. В заданной грамматике для каждого нетерминала указать все символы, от которых он зависит.

9. $\downarrow$ Построить слово длиной $n$ из букв $A,B,C$ такое, чтобы всякие два его стоящих друг за другом подслова были различны. Известно, что для любого $n$ существует хотя бы одно такое слово.

10. Пусть $R$ -- множество всех восьмибуквенных слов в алфавите $\{A,B,C,D\}$, в каждое из которых каждая буква входит по два раза. Определим две операции над такими словами: обращение и циклическую замену букв, не выводящую за пределы $R$ (например, $a \rightarrow b, b \rightarrow a$ или $a\rightarrow c, c \rightarrow b, b \rightarrow a$). Найти максимальное подмножество таких слов из $R$, что ни одно из них нельзя получить из другого путем применения указанных операций конечное число раз.

11.$\downarrow$ Слова $v$ и $w$ заданного множества слов $L$ назовем взаимозаменяемыми, если для любых двух слов $x$ и $y$ (не обязательно из $L$) $xvy \in L \leftrightarrow xwy\in L$. Найти все пары взаимозаменяемых слов из $L$.

12. $\downarrow$ По заданному слову определить какое-нибудь из его подслов, которое входит в него наибольшее число раз (например, подслово "око" входит в слово "рококо" два раза).

13. $\downarrow$ Упорядочить слова заданного множества слов, располагая их в лексикографическом порядке.

14. Задано множество правил подстановки вида $v_i \rightarroww_i$, где все $v_i$ и $w_i$ -- слова одной и той же длины. Определить, можно ли перевести одно заданное слово в другое последовательным применением заданных правил подстановки. Например, если имеются правила подстановки $ba \rightarrow ab,cb \rightarrow bc, ca \rightarrow ac$, то слово $cbba$ переводится в слово $abbc$ следующим образом: $cbba\rightarrow cbab \rightarrow cabb \rightarrow acbb \rightarrowabcb \rightarrow abbc$.

15. Указать одно из кратчайших слов, составленных из терминалов и выводимых в заданной удлиняющей грамматике.

16. $\downarrow$ Пусть $w_1,\ldots, w_n$ -- $m$-буквенные слова в некотором алфавите, а $s_i$$(i=1,\ldots, m)$ обозначает ту букву, которая наиболее часто встречается в $i$-й позиции слов $w_1,\ldots, w_n$. Выбрать такое слово из заданного списка слов $w_1,\ldots, w_n$, которое отличается от слова $s_1s_2\ldots s_m$ в наименьшем числе позиций.

17. Грамматика называется праволинейной, если все ее правила имеют вид $A \rightarrow aB$ или $C \rightarrow b$, где $A,B,C$ -- нетерминалы, $a,b$ -- терминалы. По двум заданным праволинейным грамматикам определить их эквивалентность.

18. Задана грамматика, в которой все правила имеют вид $A\rightarrow B$ или $C \rightarrow a$, где $A,B,C$ -- нетерминалы, $a$ -- терминалы. По заданному подмножеству $M$ терминальных символов определить минимальное множество нетерминалов, из которых можно вывести все терминалы из $M$.

19. Активной емкостью некоторого вывода в грамматике назовем максимум числа нетерминалов, встречающихся в каждом из промежуточных слов этого вывода. По заданным удлиняющей грамматике и слову найти вывод этого слова с минимальной активной емкостью.

20. По заданной грамматике построить такую, которая эквивалентна исходной, а каждое правило имеет вид $A\rightarrow BC$ или $A \rightarrow a$, где $A,B,C$ -- нетерминалы, $a$ -- терминал.

21. Заданы удлиняющая грамматика $G$ и число $n$. Перечислить все слова длиной $m$, $m\leq n$, выводимые в $G$.

22. $\downarrow$ По заданной грамматике построить эквивалентную ей и не содержащую правил вида$A\rightarrow B$, где $A,B$ -- нетерминалы.

23. $\downarrow$ Грамматика называется последовательной, если ее нетерминалы можно упорядочить так (скажем, $A_1,A_2,\ldots, A_n$), что правила с левой частью $A_i$ в правой части не содержат нетерминалов $A_{i+1},A_{i+2},\ldots, A_n$$(i=1,\ldots, n)$. Определить, является ли последовательной заданная грамматика.

24. Правило вывода в грамматике называется заключительным, если в его правую часть входят только терминалы. Построить такой вывод заданного терминального слова в удлиняющей грамматике, в котором заключительные правила применяются только после всех незаключительных.

25. По заданной автоматной диаграмме $D$ построить эквивалентную ей $D'$ так, что в $D'$ было не более одной вершины такой, что все выходящие из нее дуги ведут к этой же вершине.

26. Две вершины в автоматной диаграмме называются близнецами, если выходящие из них дуги с одинаковыми пометками ведут к одной и той же вершине. По диаграмме $D$ построить эквивалентную ей диаграмму $D'$ так, чтобы в $D'$ не было ни одной пары вершин-близнецов.

27. $\uparrow$ По двум заданным автоматным диаграммам над алфавитом $X$ определить, эквивалентны ли они. У к а з а н и е. Удалить вершины, недостижимые от начальной, и склеить все склеиваемые вершины в каждой из диаграмм. Если полученные диаграммы совпадают, то исходные были эквивалентны, иначе -- нет.

28. По заданной автоматной диаграмме $D$ определить, пуст ли ее язык $L(D)$.

29. По заданной автоматной диаграмме $D$ определить, является ли ее язык $L(D)$ бесконечным.

30. Задана автоматная диаграмма $D$ с непустым языком $L(D)$. Найти кратчайшее слово из $L(D)$.

31. $\uparrow$ По двум заданным автоматным диаграммам $D_1$ и $D_2$ определить, имеется ли в пересечении их языков $L(D_1) \cap L(D_2)$ хотя бы одно слово заданной длины.

32. $\uparrow$ По двум заданным автоматным диаграммам $D_1$ и $D_2$ с непустым пересечением их языков найти кратчайшее слово из $L(D_1) \cap L(D_2)$.

33. $\uparrow$ По заданной автоматной диаграмме определить, есть ли в ней хотя бы одна пара склеиваемых вершин.

34. $\uparrow$ По заданной автоматной диаграмме построить такую эквивалентную автоматную диаграмму, в которой нет ни одной пары различных склеиваемых вершин.

35. $\downarrow$ Построить синтаксический анализатор для понятия правильного скобочного выражения (ПСВ):

ПСВ ::=({любой-символ-отличный-от-скобки}*)|(ПСВ{ПСВ}*)
 

36. $\downarrow$ Для встречающихся в заданном тексте пар рядом расположенных символов указать, сколько раз встречается в тексте каждое из таких двухбуквенных сочетаний.

37. $\downarrow$ Для заданного текста определить длину содержащейся в нем максимальной серии символов, отличных от букв.

38. $\downarrow$ В заданной последовательности целых чисел найти самую длинную последовательность, которая является арифметической или геометрической прогрессией.

39. $\downarrow$ По заданной последовательности целых чисел $A$ построить последовательность $B$ такую, что $B(i)$ -- это количество элементов из $A$, превосходящих $A(i)$, в начальном отрезке $A$ длиной $i-1$.

40. $\downarrow$ Найти максимум длины таких начальных отрезков заданного слова, которые имеют вид $vv$, где $v$ -- симметричное слово.

41. $\downarrow$ Перечислить все слова заданного предложения, которые состоят из тех же букв, что и первое слово предложения.

42. $\downarrow$ Найти максимальную по длине монотонную (т.е. либо неубывающую, либо невозрастающую) подпоследовательность заданной последовательности целых чисел.

43. $\downarrow$ Для заданной последовательности целых чисел $A=a_1a_2\ldots a_n$ определим $T(i,j)$ как $\sum^j_{k=i}a_k$. Найти $i,j$ такие, что $T(i,j)$ максимально.

44. $\downarrow$Характеристикой слова назовем длину содержащейся в нем максимальной серии. Упорядочить слова заданного предложения в соответствии с ростом их характеристик.

45. $\downarrow$ В заданном предложении найти пару слов, из которых одно является обращением другого.

46. $\downarrow$ Для каждого из слов заданного предложения указать, сколько раз оно встречается в предложении.

47. $\downarrow$ Найти самое длинное симметричное слово заданного предложения.

48. $\downarrow$Расстояние между двумя словами равной длины -- это количество позиций, в которых различаются эти слова. В заданном предложении найти пару наиболее далеко удаленных слов заданной длины.

49. $\downarrow$ Отредактировать заданное предложение, удаляя из него слова-серии, а также те слова, которые уже встречались в предложении раньше.

50. $\downarrow$ Найти множество всех слов, которые встречаются только в одном из двух заданных предложений.

51. $\downarrow$ В предложении все слова начинаются с различных букв. Напечатать (если можно) слова предложения в таком порядке, чтобы последняя буква каждого слова совпадала с первой буквой следующего слова.

52. $\downarrow$ Найти множество всех слов, которые встречаются в каждом из двух заданных предложений.

53. $\downarrow$ Отредактировать заданное предложение, удаляя из него все слова с нечетными номерами и переворачивая слова с четными номерами.

П р и м е р: HOW DO YOU DO$\rightarrow$OD OD.

54. $\downarrow$ Заданы два текста; каждый текст составлен из попарно различных слов. Определить, можно ли получить второй текст из первого удалением некоторых его символов.

55. $\downarrow$ Найти самое длинное общее слово двух заданных предложений.

56. $\downarrow$ Даны два предложения. Найти самое короткое из слов первого предложения, которого нет во втором предложении.

57. $\downarrow$ Среди слов заданного предложения, которые не являются сериями, найти такое, которое имеет наибольшее число вхождений в предложение.

58. $\downarrow$ Проверить, верно ли, что в данном предложении всякое несимметричное слово имеет четную длину.

59. $\downarrow$ Отредактировать заданное предложение, удаляя из него слова, которые встречаются в предложении заданное число раз.

60. $\downarrow$ Определить, содержится ли в заданной последовательности целых чисел хотя бы одно число Фибоначчи.

61. $\downarrow$ Найти наименьшее общее кратное всех чисел, содержащихся в заданной последовательности натуральных чисел.

62. $\downarrow$ Проверить, является ли заданная последовательность целых чисел перестановкой начального отрезка последовательности натуральных чисел.

63. $\downarrow$ Напечатать заданное предложение таким образом, чтобы каждое его слово целиком находилось в одной строке распечатки (т.е. избавиться от переносов).

64. $\downarrow$ Указать длину такого начального отрезка заданной последовательности целых чисел, для которого максимально отношение числа встречающихся в нем степеней двойки к количеству чисел Фибоначчи.

65. $\downarrow$ В заданном предложении указать слово, в котором доля гласных (A,E,I,O,U) максимальна.

66. $\downarrow$ Переставить и перепечатать слова заданного предложения в соответствии с ростом доли согласных$(B,C,D,F,G,H,K,L,M,N,P,$$Q,R,S,T,V,$$W,$$X,$$Z)$ в этих словах.

67. $\downarrow$ Для каждого символа заданного текста указать, сколько раз он встречается в тексте. Сообщение об одном символе должно печататься не более одного раза и иметь вид: "Символ A встретился сто пять раз. Символ 0 встретился двадцать два раза.".

68. $\downarrow$ Заменить окончание ING каждого слова, встречающегося в заданном предложении, на ED.

69. $\downarrow$ Отредактировать заданное предложение, удаляя из него все слова, целиком составленные из вхождений не более чем двух букв

П р и м е р: AKKA KNOBIKAISE$\rightarrow$KNOBIKAISE.

70. $\downarrow$ Задан текст, в котором нет вхождений символов '(' и')'. Выполнить его сжатие, т.е. заменить всякую максимальную подпоследовательность, составленную из более чем трех вхождений одного и того же символа, на $(k)s$, где $s$ -- повторяемый символ, а $k>3$ -- количество его повторений.

71. Решить предыдущее задание, заменяя в тексте любую подцепочку $\beta$ вида $\alpha\alpha\ldots\alpha$ на цепочку $K(\alpha)$, где $\alpha$ -- непустая цепочка, а $K$ -- десятичная запись кратности ее повторений в цепочке $\beta$.

П р и м е р: AAA2B2BAAA2B2B$\rightarrow$2(3(A)2(2B))
 

72. $\downarrow$ Задано предложение, в котором есть вхождения каждой из букв латинского алфавита. Пусть$C_{\alpha}$ для буквы $\alpha$ означает первое из слов предложения, содержащих $\alpha$. Проверить, верно ли, что длины слов $C_{\alpha}$ упорядочены в соответствии с порядком букв алфавита (т.е. слово $C_A$ не длиннее слова $C_B$ и т.д.).

73. $\downarrow$ Построить последовательность длиной 100, образованную цифрами пятеричного представления последовательности натуральных чисел, начинающейся с заданного $n$.
 

74. $\downarrow$ Построить синтаксический анализатор для понятия простое-выражение.
простое-выражение::=
простой-идентификатор|( простое-выражение знак-операции простое-выражение)

простой-идентификатор::=буква

знак-операции ::= - | + | *

75. $\downarrow$ Построить синтаксический анализатор для понятия простой-оператор-присваивания.
простой-оператор-присваивания::=
идентификатор:= цифра {цифра}*| идентификатор {- | + } идентификатор

76. $\downarrow$ Построить синтаксический анализатор для понятия вещественное-число.
вещественное-число ::=
целое-число . целое-без-знака | целое-число . целое-без-знака  E целое-число| целое-число E целое-число

целое-без-знака ::=  цифра {цифра}*

целое-число ::=  целое-без-знака| { - | + } целое-без-знака

77. $\downarrow$ Построить синтаксический анализатор для понятия простое-логическое.

простое-логическое ::=
TRUE | FALSE | простой-идентификатор | NOT простое-логическое |(простое-логическое знак простое-логическое)

простой-идентификатор ::=  буква

знак::= AND | OR
 

78. Написать программу, которая по заданному простому-логическому выражению (определение понятия содержится в формулировке предыдущего задания), не содержащему вхождений простых идентификаторов, вычисляет и печатает значение этого выражения.

79. $\downarrow$ Построить синтаксический анализатор для понятия выражение.
выражение : := цифра {цифра}* | (выражение { - | + | * } выражение}

80. Написать программу, которая по заданному выражению (определение понятия содержится в формулировке предыдущего задания) вычисляет и печатает либо значение этого выражения, либо сообщение "при вычислении константного выражения получен промежуточный результат, превосходящий по модулю миллион". 81. $\downarrow$ Построить синтаксический анализатор для понятия скобки.

скобки :: = квадратные | круглые

квадратные ::= [ круглые круглые] | +

круглые ::= (квадратные квадратные) | -
 

82. $\downarrow$ Построить синтаксический анализатор для понятия список-списков.

список-списков ::= список {; список}*

список ::= элемент {, элемент}*

элемент ::= буква

83. $\downarrow$ Построить синтаксический анализатор для понятия список-параметров.
список-параметров ::= параметр {, параметр}*

параметр ::=
имя = цифра {цифра}* | имя = ( список-параметров)

имя::=буква буква буква

84. $\downarrow$ Построить синтаксический анализатор для понятия скобки.
скобки ::= кругл | квадр

кругл ::= А | ((кругл) [квадр])

квадр ::= В | [[квадр] (кругл)]

85. $\downarrow$ Построить синтаксический анализатор для понятия сумма.

сумма ::= целое  { знак-операции целое}*

целое ::=  цифра {цифра}*

знак-операции ::= - | +

Например, 021+16 и 22  -  суммы, а +1  -  не сумма.

86. Написать программу, которая по заданной сумме (определение понятия содержится в формулировке предыдущего задания) вычисляет и печатает либо значение этой суммы, либо сообщение "при вычислении суммы получен промежуточный результат, превосходящий по модулю миллион".

87. По заданному слову длины $n$ построить множество всех слов заданной длины каждое из которых является перестановкой $k$ букв исходного слова.

88. $S$-терм определяется рекурсивно по следующим двум правилам: символ $S$ является $S$-термом, если $A$ и $B$ - некоторые $S$-термы, то формула также является $S$-термом. Переход от $S$-терма к $S$-терму называется $S$-редукцией, если получен из заменой в нем некоторого $S$-подтерма вида  ((S A)B)C) на подтерм ((A C)(A B)). Заданы два $S$-терма. Проверить, можно ли перейти от одного из них к другому с помощью $S$-редукций.

89. Размером некоторого $S$-терма (см. предыдущее упражнение) назовем количество в нем символов $S$. Сгенерировать множество всех $S$-термов заданного размера.

90. Задана цепочка в алфавите, состоящим из круглых скобок и знака вопроса. Определить, сколькими способами можно заменить знаки вопроса цепочками, состоящими из круглых скобок, так, чтобы получилось правильное скобочное выражение (см. задание 35), длина которого не превышает заданного числа.

91. Заданы десятичные записи четырех целых чисел, в которых некоторые цифры заменены знаком вопроса. Найти такие подстановки цифр вместо знаков вопроса, чтобы совпали суммы двух первых и двух последних чисел.

92. Заданы десятичные записи четырех целых чисел, в которых некоторые цифры заменены буквами. Найти такие подстановки цифр вместо букв, чтобы разные буквы заменялись разными цифрами, одинаковые буквы заменялись одинаковыми цифрами, числа не начинались с нулей и совпали суммы двух первых и двух последних чисел.

93. Образец -- это цепочка, состоящая из букв и символов ? и *. Некоторая цепочка букв $x$удовлетворяет образцу $\alpha$, если $x$ можно получить из $\alpha$ заменами вхождений символов ? на отдельные буквы и вхождений символа * на произвольные цепочки букв. Определить длину минимальной цепочки букв, удовлетворяющей заданным двум образцам.

94. Построить множество всех двоичных последовательностей заданной длины, в которых никакие две единицы не стоят рядом.

95. Написать программу, которая по заданной -машине печатает результат работы машины на заданном допустимом ее аргументе.

96. Найти номер наиболее часто исполняемой команды заданной -машины на заданном допустимом ее аргументе.

97. Задана -машина и некоторый ее аргумент. Определить его (аргумента) допустимость для заданной -машины. Предусмотреть печать следующих сообщений: "зацикливание", "выход за границы памяти", "недопустимое присваивание".

98. Задана -машина. Определить все ее избыточные команды. Команда считается избыточной, если нет такого аргумента, при котором она выполнялась хотя бы один раз.

99. Решить предыдущее упражнение, предполагая, что $K$ достаточно велико, но в любой момент выполнения KM-машины имеется не более 100 ячеек, хранящих ненулевые значения.

100. Выполнить синтаксический контроль логических выражений языка Паскаль, в которых используются только однобуквенные имена простых логических переменных, константы и true и false, круглые скобки и операции not, and, or.
 

Next:6.3 Формулы и программы
Up:6 Формулировки заданий
Previous:6.1 Графы и системы

© В.Н. Касьянов, Е.В.Касьянова,2004