Экзамен_вопр

Теория языков программирования и методы трансляции

###THEMES###

Формальные языки и грамматики

1 В классификации грамматик по Хомскому выделяется … типа (ов) грамматик

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

3 Выбрать правильное определение формальной грамматики.

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

B формальная грамматика – это система правил, определяющих принадлежность фраз языку.

C формальная грамматика – это система правил, определяющих правильность расстановки знаков препинания в фразах языка.

D формальная грамматика – это математическая система, позволяющая определить правильность построения фраз языка.

4 Выбрать правильное определение семантики языка.

-семантика языка определяет смысл фраз.

-семантика языка определяет принадлежность фраз языку.

- семантика языка это правила, определяющие множество текстов.

- семантика языка это наука о естественных языках и их классификации.

5 Выбрать правильное определение синтаксиса языка.

-Синтаксис языка определяет принадлежность фраз языку

-Синтаксис языка определяет правила, которые определяют предложения языка.

-Синтаксис языка определяет смысл фраз языка.

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

6 Какое понятие является более общим?

-Сентенциальная форма.

-Строка языка

-Терминальная сентенциальная форма

-Предложение языка.

7 Какую роль в грамматике играет аксиома ?

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

-Аксиома- это префикс строки.

-Аксиома - это правило грамматики.

-Аксиома- это пустая цепочка.

8 Какую задачу решает распознаватель?

-Задачу проверки правильности имеющихся строк

-Задачу генерации правильных строк языка.

-Задачу порождения лексических единиц.

- Задачу построения графа распознавателя.

9 Какой тип грамматики из классификации Хомского является наиболее общим?

+Тип 0.

-Тип 3

-Тип 1

-Тип 2

10 Распознаватель допускает (принимает) входную цепочку ,если

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

-он может переместить считывающую головку на шаг влево.

-он обрабатывает последовательность входных символов, принадлежащих некоторому конечному множеству

-он может переместить считывающую головку на шаг вправо.

11 Укажите правильный вариант соответствия классов формальных грамматик и распознавателей.

-Кл.0- машины Тьюринга, кл.1- линейные ограниченные автоматы, кл. 2- автоматы с магазинной памятью, кл.3- конечные автоматы.

-Кл.0- машины Тьюринга, кл.1- линейные ограниченные автоматы, кл. 2-конечные автоматы, кл.3- конечные автоматы с магазинной памятью.

- Кл.0- линейные ограниченные автоматы, кл.1- машины Тьюринга, кл. 2-конечные автоматы, кл.3- конечные автоматы с магазинной памятью.

- Кл.0- линейные ограниченные автоматы, кл.1- машины Тьюринга, кл. 2-конечные автоматы, кл.3- конечные автоматы с магазинной памятью.

12 Каким методом описания синтаксиса языков программирования дано определение понятия «идентификатор» ?

<идентификатор> ::= <буква> | <идентификатор> <буква>

| <идентификатор> <цифра>

<буква> :: = a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

<цифра> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

-С использованием формы Бэкуса-Наура

- С использованием диаграмм Вирта.

- С использованием грамматики

- С использованием диаграммы переходов.

13 Практического применения не имеют грамматики, относящиеся только к типу

-с фразовой структурой

- контекстно- зависимых

- контекстно-свободных

- регулярных

14 К какому типу по классификации Хомского относится грамматика , если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении формальной грамматики.

-типа 0

-типа 3

-типа 1

-типа 2

15 Грамматика называется … грамматикой, если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики.

-С фразовой структурой

-Контекстно-зависимой

-Контекстно-свободной

-Регулярной

16. При построении дерева вывода сверху вниз в корень дерева помещается

-аксиома грамматики

-терминальный символ

-нетерминальный символ

-знак операции

17 Грамматика называется … грамматикой, если каждое правило вывода из множества Р имеет вид A , где A V_N , , (V_T V_N)^* и (V_T V_N)⁺.

-Контекстно-зависимой

-Тип 0

-Контекстно-свободной

-Регулярной

18 Грамматика называется … , если ее правила вывода имеют вид , где , или , где .

-Тип 0

-Регулярной

-Контекстно-зависимой

-Контекстно-свободной

19 Грамматика называется … грамматикой, если ее правила вывода имеют вид: , где и

-Тип 0

-Контекстно-свободной

-Контекстно-зависимой

-Регулярной

20 Алфавитом V называется …

-конечное множество символов

-любая конечная последовательность символов

-упорядоченное множество символов

-количество нетерминальных символов

21 Цепочкой в алфавите V называется …

-любая конечная последовательность символов этого алфавита

-упорядоченное множество символов этого алфавита

-конечное множество символов

-нет правильного ответа

22 Задать язык L в алфавите V можно … способами

-3

-2

-4

-5

23 Формальным языком L в алфавите V называют …

- -множество, содержащее все цепочки в алфавите V, исключая пустую цепочку .

-произвольное подмножество множества V^*

-множество, содержащее все цепочки в алфавите V, включая пустую цепочку

-произвольное подмножество множества V⁺

24 Язык L(G)={(ac)ⁿ(cb)ⁿ | n>0 }, определяемый грамматикой с правилами вывода: 1) S aQb | accb; 2) Q cSc, является …

-Контекстно-свободным

-Тип 0

-Контекстно-зависимым

-Регулярным

25 Язык L(G)={aⁿbⁿcⁿ | n1}, определяемый грамматикой с правилами вывода: 1) S aSBC | abc; 2) bC bc; 3) CB BC; 4) cC cc; 5) BB bb, является …

-Тип 0

-Контекстно-зависимым

-Контекстно-свободным

-Регулярным

26 Язык L(G)={ | {a, b}⁺, где нет двух рядом стоящих а, определяемый грамматикой с правилами вывода: 1) S A | B; 2) A a | Ba; 3) B b | Bb | Ab, является …

-Контекстно-зависимым

-Тип 0

-Регулярным

-Контекстно-свободным

27 В классификации распознавателей выделяется … типа (ов) распознавателей

-3

-4

-5

-2

28 Регулярные грамматики делятся на … типа (ов)

-3

-4

-2

-5

29 Грамматика G, определяемая правилами: SAB; ABCBb; CBABB; Aa; aBa, является…

-Контекстно-зависимой

-Тип 0

-Контекстно-свободной

-Регулярной

30 Грамматика G, определяемая правилами: SaAbB; AbBaAbB; bBbbb; Aе, является…

-Контекстно-зависимой

-Тип 0

-Контекстно-свободной

-Регулярной

31 Грамматика G, определяемая правилами: SAaB; AaBaAaBb; aBbabb; Aе, является…

-Контекстно-зависимой

-Контекстно-свободной

-Тип 0

-Регулярной

32 Грамматика G, определяемая правилами: SAB; ABaDB; DBABB; Bb; Abb, является…

-Контекстно-зависимой

-Тип 0

-Контекстно-свободной

-Регулярной

33 Грамматика G, определяемая правилами: SAS|е; Aa|b, является…

-Тип 0

-Контекстно-свободной

-Контекстно-зависимой

-Регулярной

34 Грамматика G, определяемая правилами: SAB; ABaABB; Bb; Aa, является…

-Тип 0

-Контекстно-свободной

-Контекстно-зависимой

-Регулярной

35 Грамматика G, определяемая правилами: SASB|BSA; Aa; Bb|е; Sbе, является…

-Тип 0

-Контекстно-зависимой

-Контекстно-свободной

-Регулярной

36 Грамматика G, определяемая правилами: SAcBs; AAcA|B; Ba|b, является…

-Тип 0

-Контекстно-свободной

-Контекстно-зависимой

-Регулярной

37 Из перечисленного регулярные языки могут быть заданы с помощью: 1) регулярных грамматик; 2) нерегулярных грамматик; 3) конечных автоматов; 4) нерегулярных множеств; 5) регулярных множеств.

- 2,4

- 1,4

-1, 3, 5

-1,2,3

38 Из перечисленного: 1) круглые скобки; 2) угловые скобки; 3) квадратные скобки; 4) запятая; 5) точка - в качестве метасимволов для задания грамматик используются

-2,4,5

-1,4,5

-1,2, 3

-3,4,5

39 Из перечисленного: 1) ленты; 2) устройства управления; 3) внешняя память; 4) внутренняя память; 5) решающее устройство - распознаватель состоит из компонентов

-3,4,5

-1,4,5

-1, 2, 3

-2,3,4

40 Когда символ определяется сам через себя в одном правиле, рекурсия называется

-косвенной

-явной

-левосторонней

-правосторонней

41 Конфигурация распознавателя определяется параметрами: 1) содержимое выходной цепочки символов; 2) содержимое входной цепочки символов; 3) состояние УУ; 4) содержимое внешней памяти; 5) содержимое внутренней памяти -из перечисленного

-1, 5

-1,2,3

-2, 3, 4

-3,4,5

42 По видам устройства управления распознаватели подразделяются на: 1) стохастические; 2) алгоритмизированные; 3) детерминированные; 4) недетерминированные; 5) аналитические - из перечисленного

-1,2,5

-1,3,5

-3, 4

-4,5

43 Существует … способ(а) представления функции переходов в конечном автомате.

-1

-3

-2

-4

44 Язык L(G)={a^mbⁿ | m,n0} определяется грамматикой с правилами вывода:

-1) S AB ; 2) A aA| ; 3) B bB|;

-1) S A|B ; 2) A aA| ; 3) B bB|;

-1)S A|B|АВ ; 2) A aA ; 3) B bB;

-1) S AB ; 2) A aA|а ; 3) B bB|b;

Регулярные языки и грамматики

45 Конечный автомат – это простейший распознаватель

- с магазинной памятью.

- без вспомогательной памяти.

- без вспомогательной памяти и устройства управления

- без устройства управления

46 Конечный автомат создается

- для конкретного контекстно-свободного языка.

- для конкретного регулярного языка.

- для конкретного контекстно-зависимого языка.

- для конкретного языка с фразовой структурой.

47 Недетерминированным конечным автоматом (НКА) называется конечный автомат, в котором

- функция переходов задана графом переходов.

- функция переходов однозначна

- функция переходов неоднозначна.

- не задана функция переходов

48 Функция переходов конечного автомата по заданному текущему состоянию и текущему входному символу…

- следующий символ входной строки.

-указывает все возможные следующие состояния.

-указывает символ, на который перемещать считывающую головку

-указывает номер символа, на который перемещать считывающую головку

49 При табличном способе задания функции переходов конечного автомата, если в позиции таблицы указано более одного состояния, то..

- конечный автомат- детерминированный.

-считывающая головка не перемещается

- конечный автомат- недетерминированный.

-такой автомат существовать не может

50 Возможно ли преобразование недетерминированного конечного автомата в детерминированный, принимающий тот же регулярный язык?

- да

- нет

-да, при введении вспомогательной памяти

-да, если оставить в грамматике только заключительные правила

51 Конечный автомат может содержать лишние состояния двух типов:

- недостижимые и эквивалентные состояния.

- эквивалентные и заключительные состояния.

- эквивалентные и начальные состояния

- недостижимые и заключительные состояния

52 Минимальный конечный автомат, не содержит

- недостижимых и эквивалентных состояний.

- эквивалентных и начальных состояний.

- эквивалентных и заключительных состояний.

- недостижимых и заключительных состояний.

53 Построить конечный автомат по заданной регулярной грамматике с правилами

-M=({S,A,B,N},{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aN 3)AaA|b|bN; Функция F переходов автомата : F(a,S)=A; F(a,S)=B; F(b,S)= F(a,A)=A; F(b,A)=N; F(a,B)=N; F(b,B)=B; F(a,N)=; F(b,N)=;

-M=({S,A,B },{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aN 3)AaA|b|bN; Функция F переходов автомата : F(a,S)=A; F(b,S)= F(a,A)=A; F(b,A)=N; F(a,B)=N; F(b,B)=B; F(a,N)=; F(b,N)=;

- M=({S,A,B},{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aВ 3)AaA|b|bВ; Функция F переходов автомата : F(a,S)=A; F(a,S)=B; F(b,S)= F(a,A)=A; F(b,A)=В; F(a,B)=В; F(b,B)=B; F(a,N)=; F(b,N)=;

- M=({S,A,B },{a,b},F,{S},{N}), 1) SaB|aA 2) BbB|a|aN 3)AaA|b|bN; Функция F переходов автомата : F(a,S)=В; F(b,S)= F(a,A)=A; F(b,A)=N; F(a,B)=N; F(b,B)=B; F(a,N)=; F(b,N)=;

Контекстно-свободные языки и грамматики

54 КС-грамматика называется приведенной, если она

-не имеет циклов и -правил.

- не имеет циклов, -правил и бесполезных символов.

- не имеет -правил и бесполезных символов.

-не имеет циклов и бесполезных символов.

55 Грамматику с правилами преобразовать в эквивалентную грамматику удалением недостижимых символов.

- с правилом

-=({a,b,с},{S},Р,S) с правилом

- с правилами

- с правилами

56 Грамматику с правилами преобразовать в эквивалентную грамматику без -правил для всех нетерминальных символов, кроме начального, который не должен встречаться в правых частях правил грамматики. Результирующая грамматика будет иметь вид:

- с правилами .

-=({0,1},{S,А,B,C},Р, S) с правилами .

- с правилами .

-=({0,1},{S,А,B,C},Р, S) с правилами .

57 Грамматику с правилами преобразовать в эквивалентную грамматику ,устранив цепные правила. Результирующая грамматика будет иметь вид:

- с правилами .

- с правилами

- с правилами .

- с правилами .

58 Грамматику с правилами . преобразовать в эквивалентную грамматику , устранив прямую левую рекурсию. Результирующая грамматика будет иметь вид:

- с правилами

-=({a, b, с, d, z},{S,А,B,C}, P^’, S) с правилами

- с правилами

- с правилами

59 Контекстно-свободные языки можно распознавать с помощью

- автомата с магазинной памятью (МП-автомата).

- конечного автомата.

- машины Тьюринга с конечным объемом ленты.

-машины Тьюринга.

60 Шаг работы МП-автомата называется -шагом, который может выполняться даже после завершения чтения входной строки, если

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

- входной символ t не принимается во внимание, и входная головка не сдвигается.

- входной символ t копируется в стек, и входная головка не сдвигается.

- входной символ t копируется в стек, и входная головка сдвигается на одну позицию вправо.

61 МП-автомат принимает строку языка опустошением магазина, если

-имеет в вершине стека символ S (аксиому грамматики).

-cчитывающая головка устройства управления сошла с входной ленты.

- после завершения ее чтения стек автомата будет пуст.

- cчитывающая головка устройства управления стоит на первом символе входной ленты.

62МП-автомат называют детерминированным (ДМП-автоматом), если, находясь в любой конфигурации

- он может выбрать более одной следующей конфигурации.

- он может считать не более одного символа входной ленты.

- он может выбрать не более одной следующей конфигурации.

- он может выбрать две следующие конфигурации.

63 Дана грамматика с правилами . Требуется выполнить анализ строки cabca.

Левосторонний вывод цепочки имеет вид:

-.

-

-

-

64 МП-автомат называется расширенным автоматом c магазинной памятью, т.е. автоматом, который может заменять

- каждый раз только один символ в вершине стека.

- цепочку символов конечной длины в верхушке стека на другую цепочку символов конечной длины.

- символ в вершине стека на пустую строку.

-несколько символов в вершине стека на пустую строку.

65. КС-грамматика обладает свойством LL(k) для некоторого k>0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и

- рассмотреть первые k символов от текущего положения считывающей головки во входной строке.

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

- рассмотреть первые k-1 символов от текущего положения считывающей головки во входной строке.

- рассмотреть первые k+1 символов от текущего положения считывающей головки во входной строке.

66 КС-грамматику называют LL(1) грамматикой, если

- не пересекаются множества направляющих символов для правил, определяющих один и тот же нетерминал грамматики.

- в правилах присутствует левая рекурсия.

-не пересекаются множества символов предшественников для правил, определяющих один и тот же нетерминал грамматики.

-в правилах присутствует правая рекурсия.

67 КС-грамматика не является LL(1) грамматикой, если

- в альтернативных правых частях правил для нетерминала присутствуют одинаковые головные символы или левая рекурсия.

- не пересекаются множества направляющих символов для правил, определяющих один и тот же нетерминал грамматики.

- в альтернативных правых частях правил для нетерминала присутствует правая рекурсия.

- в альтернативных правых частях правил для нетерминала присутствует правая рекурсия.

- в альтернативных правых частях правил для нетерминала присутствует правая рекурсия и цепные правила.

68 Что является главной проблемой восходящего анализа ?

-Процесс выполнения операций «перенос» и «свертка».

-Получение очередной правовыводимой сентенциальной формы.

-Обеспечение однозначности определения строки в вершине стека для свертки к нетерминалу.

-Определение исходной сентициальной формы

69 В основе распознавателя для грамматик простого предшествования лежит

- правосторонний разбор строки языка.

- левосторонний разбор строки языка.

-нисходящая стратегия разбора строки языка

-разбор строки языка без использования стека

70 Отношения простого предшествования Вирта-Вебера позволяют

- выделить основу правовыводимой сентенциальной формы.

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

-выделить основу левовыводимой сентенциальной формы.

- выполнить эквивалентные преобразования по устранению -правил и циклов.

71 В строке b₁< b₂= b₃< b₄= b₅> b₆ c указанными отношениями предшествования между символами основой является подстрока

- b₄b₅

- b₃b₄

- b₁b₂

- b₅b₆

72 Пустые клетки матрицы предшествования указывают на то, что

- данные символы не связаны отношением предшествования.

- данные символы связаны отношением предшествования.

- допущена ошибка в построении матрицы

- данные символы не могут попасть в основу сентенциальной формы

73 Приведенное отношение предшествования между двумя соседними символами распознаваемой строки B_i < B_i+1, существует