Задачи по курсу «Основы трансляции»

R₀: S→aSc

aS→abcc

б) L={abcda, abcaba, daabc, aabdaa, cada}.

R₁: S→ abcda | abcaba | daabc | aabdaa | cada; G₁={{a,b,c,d},{S},S,R₁}

R₂: S→ AB | Aaba | BA | aabBa | caB, A→abc, B→da; G₂={{a,b,c,d},{S,A,B},S,R₂}

8.  Вопрос: Можно ли построить дерево вывода для грамматики G из упражнения 7а ? Поясните.

8.  Ответ: Не для каждой грамматики можно построить дерево вывода. Деревом вывод можно представить в грамматиках, у которых левая часть правил состоит из одного нетерминала. Для грамматики G из упражнения 7а это условие не выполняется.

9.  Вопрос: Построить вывод в  данной грамматике следующих констант: 0.253, 0.5E35, 2E-3

9. Ответ: <константа>→<десятичное число>→<целое без знака>.<целое без знака>→<0>.<253>→0.253

<константа>→<десятичное число>E<целое>→<целое без знака>.<целое без знака>E<целое без знака>→<0>.<5>E<35>→0.5E35

<константа>→<целое>E<целое>→<целое без знака>E-<целое без знака>→<2>E-<3>→2E-3 

10.  Вопрос: Постройте  вывод в данной грамматики следующей конструкции: ((АТОМ.(АТОМ.АТОМ))(АТОМ.АТОМ)

10.  Ответ: <S>→(<S>.<S>)→((<S>.<S>).<S>)→ ((<S>.<S>)(<S>.<S>))→ ((<S>.(<S>.<S>))(<S>.<S>))→ ((АТОМ.(АТОМ.АТОМ))(АТОМ.АТОМ)) 

11.  Вопрос: Постройте в данной грамматике вывод  цепочки  (2+7)*(5-(3+1)). Покажите, каким образом для данной цепочки определяются операнды в  каждой операции.

11.  Ответ: 

 

 

 

12.  Вопрос:

а) Приведите примеры правил для каждого типа грамматик.

б) Определите типы следующих  грамматик:

1) G₁= {{a, b, c}, {A, B, S}, S, R}

R: S®AaB; A®Bbc; B®ab.

2) G= {{a, b, c}, {A, B, S}, S, R}

R: S®AaB; aAb®aBbcb; aB®ab.

3) G= {{a, b, c}, {A, B, S}, S, R}

R: S®aA; A®cB; B®e

в) Для каких из данных грамматик существует самый эффективный  алгоритм распознавания цепочек?

12.  Ответ: 

а)

0-типа:

G= (Т, N, S, R), Т= {a, b, c}, N= {S}, R: S®aFD; F®AFB; FB®bA; AF®D; D® ε 

1-типа:

G= {{a, b, c}, {A, B, S}, S, R}, R: S®AaB; aAb®aBbcb; aB®ab.

2-типа:

G₁= {{a, b, c}, {A, B, S}, S, R},  R: S®AaB; A®Bbc; B®ab. 

3-типа:

G= {{a, b, c}, {A, B, S}, S, R}, R: S®aA; A®cB; B®e

б)

1) G₁= {{a, b, c}, {A, B, S}, S, R}; R: S®AaB; A®Bbc; B®ab.

Грамматика 2типа: контекстно-свободная

2) G= {{a, b, c}, {A, B, S}, S, R}; R: S®AaB; aAb®aBbcb; aB®ab.

Грамматика 1типа: контекстно-зависимая

3) G= {{a, b, c}, {A, B, S}, S, R}; R: S®aA; A®cB; B®e

Грамматика 3типа: автоматная

в) Для 2-типа – существует алгоритм, и он более эффективен, а также для 3-типа – существует простой и эффективный алгоритм.  

 

Глава№7

1. Вопрос: С какой целью множество  входных символов обрабатывают двумя  автоматами?

1. Ответ: Множество входных символов обрабатываются двумя автоматами с целью уменьшения размера таблицы переходов.

2. Вопрос: Какой способ представления  состояний называют явным, а какой неявным ?

2. Ответ: Явный - это способ представления состояния, который заключается в запоминании номера, соответствующего текущему состоянию автомата, в некотором регистре или переменной.

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

3. Вопрос: Составьте таблицу переходов  данного автомата для цепочки 001101. Опишите переходы методом вектора переходов и методом списка переходов. Каким из методов это удобнее сделать? 

3. Ответ:

Таблица переходов для  цепочки 001101:

	0	1
А	B	-
B	D	B
D	-	B

 
Вектор переходов для  состояния B:

	0	1
B	-	B

 

Список переходов для  состояния B:

0	D
1	B

Переходы по неудаче - обработчик ошибок

0	B
1		B

4. Вопрос: Построить конечный процессор, имеющий входной алфавит {О, М, С, Ы, И, А, ε} для идентификации множества {САМ, СОМ, САМИ, СОМЫ, МЫС}. 

4. Ответ:

	О	М	С	Ы	И	А	ε
ε		М	С
М				МЫ
С	СО					СА
МЫ			МЫС
СО		СОМ
СА		САМ
МЫС							«МЫС»
СОМ				СОМЫ			«СОМ»
САМ					САМИ		«САМ»
СОМЫ							«СОМЫ»
САМИ							«САМИ»

 

 

 

 

 

 

 

 

 

 

 

 

 

Элементы таблицы в  кавычках означают, что автомат идентифицировал соответствующее слово. Пустые ячейки соответствуют выходам «слово Ï множеству». Сообщение об ошибке откладывается, пока слово не просмотрено полностью. Переходы не сопровождаются никакими действиями, кроме изменения состояния. 

5. Вопрос: В чем главная сложность  применения метода индексов?

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

1. Количество слов не должно быть слишком большим. Это условие, например, исключает множество переменных Си, так как содержит более миллиарда элементов.
2. Индекс должен легко вычисляться. Это условие может исключить даже небольшие множества зарезервированных слов, для которых нет хорошего способа построения индекса.
3. Объем множества слов фиксируется при построении, так как метод вычисления индекса неудобно изменять во время компиляции.

 

 6. Вопрос: Укажите достоинства  и недостатки метода линейного списка.

6. Ответ: Достоинства: Метод легко  приспособить к случаю расширяющихся множеств. Можно применять алгоритмы бинарного, логарифмического поиска, хеширования и т.п.

Недостатки: Поиск по длинному списку занимает много времени. 

 

Глава№11 

 

1. Вопрос: Что понимают под точностью  программной системы?

1. Ответ: Точность - если в программу поступают заданные данные, то на выходе должны быть получены ожидаемые результаты.

2. Вопрос: Какие группы факторов влияют на комфорт общения?

2. Ответ: Социальные - психологический климат в коллективе; его отношение к компьютерам; функции, возлагаемые вычислительной системой на человека.

1. Физическая эргономичность - читаемость дисплея, расположение клавиш на клавиатуре.
2. Психологическая эргономичность - несоответствие функций системы психологическим процессам человека, доступность и чувственность системы

3. Вопрос: Перечислите  основные критерии оценки интерфейса

3. Ответ:

1. Простота освоения и запоминания операций в системе.
2. Быстрота достижения целей задачи, решаемой с помощью системы.
3. Субъективная удовлетворенность при эксплуатации.

4. Вопрос: Назовите правила ведения  разговора.

4. Ответ: Правило 1: Участники разговора должны понимать друг друга.

Правило 2: Нельзя говорить одновременно.

Правило 3: Информация, которую  сообщает, новый оратор обычно связана с тем, что говорилось ранее.

5. Вопрос: Каковы задачи диалогового  процесса?

5. Ответ: Задачи диалогового  процесса:

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

6. Вопрос: Какие  бывают типы сообщений?

6. Ответ: Подсказка - это выходное сообщение системы, побуждающее пользователя вводить данные.

Входные управляющие  сообщения - это данные, вводимые пользователем, которые могут вызвать процесс выполнения данного задания

Сообщение об ошибке - это  сигнал диалогового процесса  о том, что невозможно дальнейшее выполнение обработки.

Сообщение о  состоянии системы - это информация для пользователя о том, что произошло или происходит в системе.

7. Вопрос: Чем отличается  подсказка от справочной информации?

7. Ответ: Подсказка - это выходное сообщение системы, побуждающее пользователя вводить данные.

Справочная  информация - эта информация может выводиться процессом для пояснения пользователю, что дальше делать и почему.

8. Вопрос: Какие бывают типы диалоговых процессов?

8. Ответ: Диалоговые процессы делятся на два класса:

1 - диалог, управляемый системой;

2 - диалог, управляемый пользователем.

9. Вопрос: Приведите примеры  всех вариантов подсказок.

9. Ответ: а) Меню: любое меню программы

б) Вопрос: элемент ввода  Combo Box

в) Форма: элемент ввода Edit Box

г) Запрос на ввод команды: командная  строка MS-DOS

10. Вопрос: Перечислите основные законы диалога.

10. Ответ: Законы диалога:

• диалог не вынуждает существенно подменять свои традиционные способы работы;
• стиль сообщения должен быть разговорным, а не письменным;
• избегать фамильярности;
• добавление имени пользователя в запросе быстро надоедает;
• фразы не должны требовать дополнительных пояснений;
• допустимо использовать жаргонизмы при условии использования их в среде пользователя;
• важен порядок запроса системой информации, необходимо придерживаться порядка, в каком пользователь обычно обрабатывает информацию;
• не следует заставлять человека вручную обрабатывать информацию перед вводом или после вывода;
• при размещении данных на экране необходимо соблюдать последовательность и место вывода сообщения на экран;
• в диалоге пользователь не должен вводить незначащие цифры или символы;
• не нужно запрашивать информацию, которая была введена ранее или которая может быть сформирована автоматически;
• объекты следует вводить в уникальной форме;
• не требовать от пользователя информации, которая не используется в системе;
• ввод по умолчанию;
• сокращения не должны быть двусмысленными и неестественными;
• по возможности использовать идентификаторы из одной буквы или цифры;
• выходные сообщения должны содержать только ту информацию, которая запрашивалась.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Решение задач  по курсу «Основы трансляции».  

 

1. Дана грамматика. Построить вывод заданной цепочки.

 

 a) S → T | T+S | T-S                                                b) S → aSBC | abC

        T → F | F*T                                                               CB → BC

        F → a | b                                                                     bB → bb

Цепочка   a-b*a+b                                                             bC → bc

                                                                                            cC → cc

                                                                                Цепочка   aaabbbccc

Решение:

а)

S→T-S→F-S→F-T+S→F-F*T+S→a-b*T+S→a-b*a+b   

 1        2        3             4                5                6 

Правила, которые  использовали:

1) S → T-S

2) T → F

3) S → T+S

4) T → F*T

5) F → a | b

6) S → T; T → F; F → a | b

 

б)  S → aSBC→aaSBCBC →aaSBBCC →aaabCBBCC →aaabBCBCC   

      1            2                    3                   4                       5

→aaabBBCCC →aaabbbCCC →aaabbbcCC→aaabbbccc

6                        7                       8                    9

Правила, которые использовали:

1) S → aSBC 

2) S → aSBC

3) CB → BC

4) S → abC

5) CB → BC

6) CB → BC

7) bB → bb

8) bC → bc

9) cC → cc 

 

2. Построить все сентенциальные формы для грамматики с правилами:

S → A+B | B+A

A → a

B → b

Решение:

Сентенциальные формы:

A+B→a+B

A+B→A+b

B+A→b+A

B+A→B+a  

 

3.  К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

a) S → APA 

P → + | -  

A → a | b

Решение:

Данная грамматика относиться ко 2-типу (контекстно-свободный)