Помощь студентам дистанционного обучения: тесты, экзамены, сессия
Помощь с обучением
Оставляй заявку - сессия под ключ, тесты, практика, ВКР
Сессия под ключ!

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

Сдача тестов дистанционно
Содержание
  1. Правильно охарактеризуйте типы грамматик
  2. Для контекстно-свободных языков распознавателями являют (ет)ся
  3. В определении грамматики G(VT,VN,P,S) VN означает
  4. Изменение имен символов и подстановки цепочек вместо символов называется
  5. Для регулярных языков распознавателями являют (ет)ся
  6. Вместо «k» в названии класса грамматики «LL(k)» стоит некоторое число, которое показывает количество
  7. Для классификации самого языка среди всех его грамматик всегда выбирается грамматика с классификационным типом
  8. В основе синтаксических конструкций большинства современных языков программирования лежат языки
  9. Символ А в КС-грамматике, для которого существует цепочка вывода вида А+aAb, называется
  10. Найдите правильный результат α2 =
  11. Конфигурацию конечного автомата на каждом шаге работы можно определить в виде (q,w,n), где q
  12. Для распознавателя на основе алгоритма «сдвиг-свертка» естественным является построение дерева вывода
  13. Языки операторного предшествования являются собственным подмножеством языков
  14. Грамматики, у которых все правые части правил для всех нетерминальных символов начинаются с k различных терминальных символов, носят название «_____»
  15. Выделяют следующие виды грамматик предшествования
  16. Если в каждом состоянии конечного автомата существует функция перехода для всех возможных входных символов, то этот КА называется
  17. К регулярным относятся следующие виды грамматик
  18. Символы, которые содержат слова, понятия, конструкции языка, называются
  19. Алгоритм Эрли строит
  20. Самые эффективные (с точки зрения требуемых вычислительных ресурсов) и универсальные алгоритмы для распознавания цепочек КС-языков, – это
  21. Класс грамматик, основанный на принципе выбора одной альтернативы из множества возможных на основе нескольких очередных символов в цепочке, называется
  22. LL-языки являются собственным подмножеством языков
  23. Формальные грамматики классифицируются по
  24. Укорачивающие контекстно-свободные грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида
  25. Если α = β, то
  26. Подсчитайте длину цепочки b=аааа. |b|=___(ответ цифрой)_
  27. Если V – некоторый алфавит, то множество всех цепочек над алфавитом V, включая l, обозначается
  28. Для любого языка, заданного контекстно-зависимой грамматикой, можно построить грамматику
  29. Если в цепочке вывода вида АÞ+αАβ α =l и β=l, то рекурсия
  30. Если α = «2334» то αR =
  31. Для грамматики с фразовой структурой вида G(VT,VN,P,S), V=VNÈVT правила имеют вид
  32. Для построения вывода по алгоритму Кока–Янгера–Касами грамматика должна быть в нормальной форме
  33. Выберите свойства, которые верны для регулярных выражений:
  34. Алгоритм Кока-Янгеля-Касами относится к распознавателям
  35. Выполните обращение заданной цепочки: a=город. aR= ________
  36. Конкатенация цепочек α и β обозначается
  37. В формальной записи конечного автомата M(Q,V,d,q0,F) Q означает
  38. При построении предложений нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от контекста в грамматиках
  39. Счетное множество допустимых символов языка, – это
  40. В определении грамматики G(VT,VN,P,S) S означает
  41. При выполнении такта МП-автомата в стеке удаляется
  42. Из расширенного МП-автомата всегда можно построить
  43. Леволинейные грамматики G(VT,VN,P,S), V = VNÈVT могут иметь правила видов (где A,BÎVN, γÎVT*)
  44. Установите соответствие
  45. Символы, которые входят в алфавит языка, порождаемого грамматикой, называются
  46. Если цепочка, полученная в результате вывода, пустая или содержит только терминальные символы, то вывод называется
  47. Пустая цепочка может обозначаться
  48. Совокупность слов языка, это
  49. Цепочка u = FIRST(k,α) носит в работе автомата название
  50. Укажите выражение, тождественное данному: (αβ)γ =

Правильно охарактеризуйте типы грамматик

  • тип 2: контекстно-свободные грамматики
  • имеют правила вида: 1) А®Вg или А®g 2) А®gВ или А®g
  • тип 1: контекстно-зависимые и неукорачивающие грамматики
  • на правила грамматики не накладывается никаких ограничений: a®b
  • тип 0: грамматики с фразовой структурой
  • имеют правила вида a1Аa2®a1ba2 и a®b, где |b| ³ |a|
  • тип 3: регулярные грамматики
  • имеют правила вида: А®b

Для контекстно-свободных языков распознавателями являют (ет)ся

  • двусторонние недетерминированные автоматы
  • конечные автоматы
  • односторонние недетерминированные автоматы
  • машина Тьюринга

В определении грамматики G(VT,VN,P,S) VN означает

  • множество нетерминальных символов
  • множество правил грамматики
  • множество терминальных символов
  • целевой символ грамматики

Изменение имен символов и подстановки цепочек вместо символов называется

  • гомоморфизмом
  • конкатенациями
  • гетероморфизмом
  • дополнениями

Для регулярных языков распознавателями являют (ет)ся

  • двусторонние недетерминированные автоматы
  • конечные автоматы
  • односторонние недетерминированные автоматы
  • машина Тьюринга

Вместо «k» в названии класса грамматики «LL(k)» стоит некоторое число, которое показывает количество

  • символов алфавита соответствующего языка
  • нетерминальных символов
  • рассматриваемых символов для однозначного выбора альтернативы
  • правил грамматики

Для классификации самого языка среди всех его грамматик всегда выбирается грамматика с классификационным типом

  • наиболее удобным для описания
  • минимально возможным
  • максимально возможным
  • любым возможным

В основе синтаксических конструкций большинства современных языков программирования лежат языки

  • квазирегулярные
  • с фразовой структурой
  • КС
  • регулярные

Символ А в КС-грамматике, для которого существует цепочка вывода вида А+aAb, называется

  • рекурсивным
  • бесплодным
  • цепным
  • недостижимым

Найдите правильный результат α2 =

  • αα
  • αRαR
  • α+α
  • α*α

Конфигурацию конечного автомата на каждом шаге работы можно определить в виде (q,w,n), где q

  • текущее состояние автомата
  • конечное состояние автомата
  • цепочка входных символов
  • положение указателя в цепочке символов

Для распознавателя на основе алгоритма «сдвиг-свертка» естественным является построение дерева вывода

  • слева направо
  • сверху вниз
  • справа налево
  • снизу вверх

Языки операторного предшествования являются собственным подмножеством языков

  • простого предшествования
  • недетерминированных КС
  • регулярных
  • LR

Грамматики, у которых все правые части правил для всех нетерминальных символов начинаются с k различных терминальных символов, носят название «_____»

  • LL(k)-нетерминальные
  • сильно LL(k)-грамматики
  • LL(k)-терминальные
  • правосторонние LL(k)-грамматики

Выделяют следующие виды грамматик предшествования

  • расширенного
  • составного
  • слабого
  • простого

Если в каждом состоянии конечного автомата существует функция перехода для всех возможных входных символов, то этот КА называется

  • детерминированным
  • полностью определенным
  • однозначным
  • недетерминированным

К регулярным относятся следующие виды грамматик

  • контекстно-зависимые
  • автоматные
  • праволинейные
  • леволинейные

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

  • целевыми
  • терминальными
  • нетерминальными
  • метасимволами

Алгоритм Эрли строит

  • совокупность правил
  • последовательность списков ситуаций
  • таблицу
  • множество объектов

Самые эффективные (с точки зрения требуемых вычислительных ресурсов) и универсальные алгоритмы для распознавания цепочек КС-языков, – это

  • МП-автомат
  • табличные распознаватели
  • сдвиг-свертка
  • нисходящий распознаватель с возвратом

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

  • L(kr)
  • LL(k)
  • RR(k)
  • LLR

LL-языки являются собственным подмножеством языков

  • LR
  • простого предшествования
  • недетерминированных КС
  • регулярных

Формальные грамматики классифицируются по

  • степени контекстной зависимости
  • степени сложности
  • структуре их языков
  • структуре их правил

Укорачивающие контекстно-свободные грамматики G(VT,VN,P,S), V = VNÈVT имеют правила вида

  • А®β, где AÎVN, βÎV*
  • А®β, где AÎVN, βÎV+
  • А®Аβ, где AÎVN, βÎV+
  • А®β, где AÎV+, βÎVN

Если α = β, то

  • |α| = β
  • |α| = |β|
  • α =|α +β|
  • α = |β|

Подсчитайте длину цепочки b=аааа. |b|=___(ответ цифрой)_

Если V – некоторый алфавит, то множество всех цепочек над алфавитом V, включая l, обозначается

  • V*
  • V+
  • V+l
  • V*l

Для любого языка, заданного контекстно-зависимой грамматикой, можно построить грамматику

  • регулярную
  • постоянную
  • неукорачивающую
  • ограниченную

Если в цепочке вывода вида АÞ+αАβ α =l и β=l, то рекурсия

  • представляет собой цикл
  • является правой
  • является левой
  • представляет собой рекурсию

Если α = «2334» то αR =

  • «4»
  • «4332»
  • «2334»
  • «23342334»

Для грамматики с фразовой структурой вида G(VT,VN,P,S), V=VNÈVT правила имеют вид

Для построения вывода по алгоритму Кока–Янгера–Касами грамматика должна быть в нормальной форме

  • Кока–Янгера–Касами
  • Кока–Янгера
  • Янгера–Касами
  • Хомского

Выберите свойства, которые верны для регулярных выражений:

Алгоритм Кока-Янгеля-Касами относится к распознавателям

  • с возвратом
  • нисходящим
  • на основе сдвиг-свертка
  • табличным

Выполните обращение заданной цепочки: a=город. aR= ________

Конкатенация цепочек α и β обозначается

  • |αβ|
  • αβ
  • α+β
  • α*β

В формальной записи конечного автомата M(Q,V,d,q0,F) Q означает

  • конечное множество допустимых входных символов
  • функцию переходов
  • начальное состояние автомата
  • конечное множество состояний автомата

При построении предложений нетерминальный символ может быть заменен на ту или иную цепочку символов в зависимости от контекста в грамматиках

  • НКС
  • КЗ
  • УКС
  • КС

Счетное множество допустимых символов языка, – это

  • цепочка
  • грамматика
  • слово
  • алфавит

В определении грамматики G(VT,VN,P,S) S означает

  • множество терминальных символов
  • целевой символ грамматики
  • множество нетерминальных символов
  • множество правил грамматики

При выполнении такта МП-автомата в стеке удаляется

  • верхний символ
  • цепочка, соответствующая правилу перехода
  • нижний символ
  • цепочка метасимволов

Из расширенного МП-автомата всегда можно построить

  • эквивалентный ему ДМП-автомат
  • МП-грамматику
  • эквивалентный ему обычный МП-автомат
  • МП-язык

Леволинейные грамматики G(VT,VN,P,S), V = VNÈVT могут иметь правила видов (где A,BÎVN, γÎVT*)

  • А®Вγ или А®АВγ
  • А®γВ или А®γ
  • А®Вγ или А®γ
  • А®Вγ или А®В

Установите соответствие

  • для контекстно-свободных языков распознавателями являются
  • конечные автоматы
  • для языков с фразовой структурой распознавателем является
  • двусторонние недетерминированные автоматы
  • для контекстно-зависимых языков распознавателями являются
  • машина Тьюринга
  • для регулярных языков распознавателями являются
  • односторонние недетерминированные автоматы

Символы, которые входят в алфавит языка, порождаемого грамматикой, называются

  • метасимволами
  • нетерминальными
  • терминальными
  • целевыми

Если цепочка, полученная в результате вывода, пустая или содержит только терминальные символы, то вывод называется

  • законченным
  • сентенциальным
  • последовательным
  • рекурсивным

Пустая цепочка может обозначаться

  • 0

Совокупность слов языка, это

  • синтаксис языка
  • лексика языка
  • семантика языка
  • грамматика языка

Цепочка u = FIRST(k,α) носит в работе автомата название

  • начальная
  • первичная
  • базовая
  • аванцепочка

Укажите выражение, тождественное данному: (αβ)γ =

  • α|βγ|
  • γ(αβ)
  • α(βγ)
  • (βα)γ

или напишите нам прямо сейчас

Написать в WhatsApp Написать в Telegram
Сдача тестов дистанционно
Оцените статью
Тесты для Вас
Добавить комментарий

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

или напишите нам прямо сейчас

Написать в WhatsApp
Написать в Telegram