Инструменты, алгоритмы и структуры данных

Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какая грамматика корректно описывающая понятие "поезд" является рекурсивной?

(Отметьте один правильный вариант ответа.)

Варианты ответа

$\text{Поезд }\triangleq\text{ Локомотив Вагоны}\\ \text{Вагоны }\triangleq\text{ Вагон }\{\text{Вагон}\}^+$

$\text{Поезд }\triangleq\text{ Локомотив }\text{Вагоны}\\ \text{Вагоны }\triangleq\text{ Вагон | Вагоны Вагон}$ (Верный ответ)

$\text{Поезд }\triangleq\text{ Локомотив Вагоны}\\ \text{Вагоны }\triangleq\text{ Вагон }\{\text{Вагон}\}^*$

$\text{Поезд }\triangleq\text{ Локомотив }\{\text{ Вагон }\}^*$

$\text{Поезд }\triangleq\text{ Локомотив }\{\text{ Вагон }\}^+$

Похожие вопросы

Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какая грамматика, корректно описывающая понятие "поезд" является регулярной и использует одно регулярное выражение?

Будем полагать, что поезд - это локомотив, за которым следует один или несколько вагонов. Какие грамматики корректно описывают понятие "поезд"?

Сколько времени понадобится вашему персональному компьютеру для решения задачи о "ханойской башне" в ее оригинальном варианте с 64 дисками (для корректности постановки будем полагать, что ваш ПК хотя и не является суперкомпьютером, но способен выполнить за секунду 1 миллиард переносов дисков)?

Укажите причины, по которым грамматика языка не использует правила БНФ для определения синтаксиса построения лексем?

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

Алгоритм перебора с возвратами, реализованный рекурсивной процедурой find(path) исключает зацикливание (каждый город на пути встречается только один раз), что позволяет исходный граф рассматривать как дерево. Какие утверждения справедливы для графов, перебора с возвратом, и связанных с ними деревьев вариантов?

Пусть членами семьи являются муж, жена, их родители и их дети. Определим рекурсивно понятие родственника. Члены семьи являются родственниками - родственниками уровня 0. Это не рекурсивная ветвь определения. Определим теперь рекурсивно понятие родственника - родственника некоторого уровня. Некто N является родственником уровня k + 1

, если он не является родственником уровня k или более низкого уровня, но является родственником уровня 0 любого из родственников уровня k. К какому уровню по отношению к Вам относится внук брата дедушки?

Укажите некорректные варианты определения рекурсивной версии программы fibonacci:

Креативное понятие - это творческое понятие, несущее новую информацию, которая не может быть выведена из уже известных понятий. Укажите, какие понятия относятся к креативным понятиям?

Чем отличается регулярная грамматика от грамматики БНФ?