язык программирования FORTAN

[Veronca]

1. Построить вывод данной цепочки  в грамматике:
а) S T | T+S | T  S
T F | F*T
F a | b
  a  b*a+b
б) S aSBC | abC
CBBC
bB bb
bC bc
cC cc
  aaabbbccc
2. Построить все сентенциальные формы для грамматики:
S A+B | B+A
A a
B b
20
3. К какому типу по Хомскому относится данная грамматика? Ка-
кой язык она порождает? Каков тип языка?
а) SAPA
P + | 
A a | b
б) S aQb | 
Q cSc
в) S 1B
B B0 | 1
г) SA | SA | SB
A a
B b
д) S a | Ba
B Bb | b
е) S Ab
A Aa | ba
ж) S 0A1 | 01
0A 00A1
A 01
з) SAB
AB BA
A a
B b
и) S A | B
A aAb | 0
B aBbb | 1
к) S 0A | 1S
A 0A | 1B
B 0B | 1B | 
л) S 0S | S0 | D
D DD | 1A |
A 0B | 
B 0A | 0
м) S 0A | 1S | 
A 1A | 0B
B 0S | 1B
н) S SS | A
A a | bb
о) SAB
A a | cA
B bA
21
п) S aBA | 
B bSA
AA c
р) S Ab | c
A Ba
B cS
с) S 0A1
0A 00A1
A 
4. Построить грамматику, порождающую язык:
а) L  anbm | n,m 1
б) L  ac c c | , ,  ëþ áû å öåï î ÷êè èç a è b
в)   1 2 1 1 2 1 ... ... | 0 èëè 1, 1 n n n i L aa a aa aa a n     
г) L  anbm | n  m;n,m  0
д) L = {цепочки из 0 и 1 с неравным количеством 0 и 1}
е) L  | a, b    
ж) L  | 0,1     , причем количество 0 и 1 одинаково, а
любая подцепочка, взятая с левого конца содержит единиц
не меньше, чем нулей
з) a2 b  | 1, 0 L  m m n m  n 
и)  3 1 | 1 n L  a  n 
к)   2L  an | n 1
л)   L  an3 1 | n 1
5. Эквивалентны ли грамматики с правилами:
а) SAB
A a | Aa
B b | Bb
и
SAS | SB | AB
A a
B b
22
б) S aSL | aL
L Kc
cK Kc
K b
и
S aSBc | abc
cB Bc
bB bb
6. Построить КС-грамматику, эквивалентную данной:
а) S aAb
aA aaAb
A 
б) S AB | ABS
AB BA
BA AB
A a
B b
7. Построить регулярную грамматику, эквивалентную данной:
а) S A | AS
A a | bb
б) S A.A
A B | BA
B 0 | 1
8. Построить приведенную грамматику, эквивалентную данной:
а) S aABS | bCACd
A bAB | cSA | cCC
B bAB | cSB
C cS | c
б) S aAB | E
A dDA | 
B bE | f
CcAB | dSD | a
D eA
E fA | g
9. Докажите, что грамматика G порождает язык L. Для этого пока-
жите, что в данной грамматике (а) выводятся соответствующие це-
почки и (б) не выводятся другие цепочки.
G: S aSBC | abC
CBBC
23
bB bb
bC bc
cC cc
L  anbncn | n 1
10. Построить восходящим и нисходящим методами дерево вывода
для цепочки  в данной грамматике:
а) SS0 | S1 | D0 | D1
D H.
H 0 | 1 | H0 | H1
 = 10.1001
б) S if B then S | B = E
E B | B+E
B a | b
 = if a then b = a+b+b
11. Определить тип грамматики, описать язык, который она поро-
ждает и построить КС-грамматику, эквивалентную ей:
SP 
P 1P1 | 0P0 | T
T 021 | 120R
R1 0R
R0 1
R  1 
12. Построить регулярную грамматику, порождающую цепочки в
алфавите {a, b}, в которых символ а не встречается два раза под-
ряд.
13. Написать КС-грамматику для данного языка, построить вывод
цепочки  в этой грамматике:
а) L  a2nbmc2k | m  n  k,m 1;   aabbbcccc
б) L  ancbmcan | n,m  0;   aacbbbcaa
в) L  1n0m1p | n  p  m; n, p,m  0;  110000111
24
14. Построить грамматику, которая порождает сбалансированные
относительно скобок цепочки в алфавите a, (, ), . Цепочка 
называется сбалансированной, если (а)  не содержит скобок; (б)
1   ( ) или 1 2    , где 1 2  , – сбалансированные цепочки.
15. Определить тип языка, написать грамматику, которая его по-
рождает. Построить левосторонний и правосторонний выводы для
цепочки 1111111100:
L  13n20n | n  0
16. Привести пример грамматики, все правила которой имеют вид
ABt , или AtB, или At , для которой не существует эк-
вивалентной регулярной грамматики.
17. Конкатенацией языков L1 и L2 называется такой язык 1 2 L  L L ,
что   1 2 L   | L , L . Итерацией языка L называется такой
язык L*, что L*   LLLLLL... . Написать общие алго-
ритмы построения по данным КС-грамматикам, порождающим
языки L1 и L2, грамматик для языков:
а) 1 2 L L ;
б) 1 2 L L
в) L*
18. Показать, что данная грамматика неоднозначна. Опишите язык,
который она порождает, с помощью однозначной грамматики:
E E+E | E*E | (E) | i
25
19. Показать, что данная грамматика неоднозначна. Какой язык
она порождает? Является ли он однозначным?
S aAc | aB
B bc
A b
20. Показать, что наличие в КС-грамматике данного правила
(AVN ;  *  , ,  VN VT ) делает ее неоднозначной. Можно ли
преобразовать эти правила таким образом, чтобы грамматика стала
однозначной?
а) AAA|
б) AAA|
в) AA| A |
г) AA|A A|
21. Построить алгоритм, определяющий, пуст ли язык, который
порождает данная КС-грамматика.
22. Язык называется распознаваемым, если существует алгоритм,
который за конечное число шагов позволяет получить ответ о при-
надлежности любой цепочки языку. Если число шагов зависит от
длины цепочки и может быть оценено до выполнения алгоритма,
язык называется легко распознаваемым. Доказать, что язык, поро-
ждаемый неукорачивающей грамматикой, легко распознаваем.
23. Доказать, что любой конечный язык, в который не входит пус-
тая цепочка, является регулярным языком.
24. Нетерминальный символ А называется циклическим в грамма-
тике G  (VT,VN, P,S) , если в грамматике существует вывод
1 2 A A . Циклический символ А называется эффективным, ес-
26
ли длина цепочки1A2 больше 1. КС-грамматика называется цик-
лической, если в ней есть хотя бы один циклический нетерминал.
Доказать, что:
а) нециклическая КС-грамматика порождает конечный язык;
б) условие цикличности грамматики не является достаточным
условием бесконечности порождаемого ей языка;
в) язык, порождаемый циклической приведенной КС-грамма-
тикой, содержащей хотя бы один эффективный цикличе-
ский символ, бесконечен.

[Toucan]

Дубли удалены, тема перемещена в Карантин.

1. Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

2. Приведите свои попытки решения всех задач и объясните, что конкретно вызывает затруднения.

После того как исправите сообщение, сообщите об этом в теме Сообщение в карантине исправлено.

________________
Всякий, кто поступил в университет, но не хочет сам учиться - враг своей страны, подрывающий ее научно-технический, интеллектуальный и оборонный потенциалы.
(c) по мотивам сообщения Yuri Gendelman.