Язык Дика

Языком Дика (англ. Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом

{a1,b1,a2,b2,…an,bn},

порождаемый грамматикой S → ε, S → a1Sb1S, . . . , S → anSbnS.

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

Язык назван в честь немецкого алгебраиста Вальтера фон Дика.

Источник: Википедия

Связанные понятия

Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С её помощью можно явно пронумеровать следующие объекты языка: переменные, предметные константы, функциональные символы, предикатные символы и формулы, построенные из них. Построение нумерации Гёделя для объектов теории называется арифметизацией теории — оно позволяет переводить высказывания, аксиомы, теоремы, теории в объекты арифметики. При этом требуется, чтобы нумерация g была эффективно вычислимой...

Направленное множество в математике — непустое множество A с заданным на нем рефлексивным транзитивным отношением ≤ (то есть предпорядком), обладающее дополнительным свойством: у любой пары элементов из A есть верхняя грань в A.

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям...

Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста (то есть её рост быстрее полиномиального, но медленнее экспоненциального).

Признаковое описание объекта (англ. feature vector) — это вектор, который составлен из значений, соответствующих некоторому набору признаков для данного объекта. Значения признаков могут быть различного, не обязательно числового, типа. Является одним из самых распространённых в машинном обучении способов ввода данных.

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

Функция принадлежности нечёткого множества — обобщение индикаторной (или характеристической) функции классического множества. В нечёткой логике она представляет степень принадлежности каждого члена пространства рассуждения к данному нечёткому множеству.

Веду́щие нули́ в записи числа при помощи позиционной системы счисления — последовательность из одного или более нулей, занимающая старшие разряды. Понятие ведущих нулей возникает при использовании представлений чисел, имеющих фиксированное количество разрядов. В остальных случаях, как правило, ведущие нули не пишутся.

Модель системы аксиом — какой-либо математический объект, который отвечает данной системе аксиом. Истинность системы аксиом можно доказать, только построив модель в рамках другой системы аксиом, которая считается «истинной». Кроме того, модель позволяет наглядно продемонстрировать некоторые особенности данной аксиоматической теории.

Матрица расстояний — это квадратная матрица типа «объект-объект» (порядка n), содержащая в качестве элементов расстояния между объектами в метрическом пространстве.

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

Синглетон — множество с единственным элементом. Например, множество {0} является синглетоном.

Лемма о накачке (лемма о разрастании, лемма-насос; англ. pumping lemma) — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.

Универсальная тригонометрическая подстановка, в англоязычной литературе называемая в честь Карла Вейерштрасса подстановкой Вейерштрасса, применяется в интегрировании для нахождения первообразных, определённых и неопределённых интегралов от рациональных функций от тригонометрических функций. Без потери общности можно считать в данном случае такие функции рациональными функциями от синуса и косинуса. Подстановка использует тангенс половинного угла.

Моноидальная категория (или тензорная категория) — категория C, снабженная бифунктором...

Антецедент (лат. antecedens — «предшествующее») — на языке старых философов, особенно у логиков Кантовской школы, в их учении о суждениях, заключениях и доказательствах антецедент означает, отчасти — логическое подлежащее в его отношении к сказуемому, отчасти — причину в отношении к следствию.

Семантика Крипке является распространенной семантикой для неклассических логик, таких как интуиционистская логика и модальная логика. Она была создана Солом Крипке в конце 1950-х — начале 1960-х годов. Это было большим достижением для развития теории моделей для неклассических логик.

В лингвистике, катена (англ. catena «вереница, череда»; от лат. catena «цепь») — синтаксическая и морфологическая единица, тесно связанная с грамматиками зависимостей. Она является более гибким и объемлющим понятием, чем составляющая, и поэтому, вероятно, может лучше составляющей служить в качестве фундаментальной единицы синтактического и морфосинтактического анализа.

Знак деления — математический символ в виде двоеточия (∶), обелюса (÷) или косой черты (∕), используемый для обозначения оператора деления.

В математике, норма́льная фо́рма — простейший либо канонический вид, к которому объект приводится эквивалентными преобразованиями.

Анализ формальных понятий (АФП) (англ. Formal Concept Analysis, FCA) — ветвь прикладной алгебраической теории решёток. Традиционно АФП относят к области концептуальных структур в искусственном интеллекте.

Лемма о змее — это инструмент, используемый в математике, особенно в гомологической алгебре, для построения длинных точных последовательностей. Лемма о змее верна в любой абелевой категории и играет ключевую роль в гомологической алгебре и её приложениях, например в алгебраической топологии. Гомоморфизмы, построенные с её помощью, обычно называют связывающими гомоморфизмами.

В теории категорий, представимый функтор — функтор специального типа из произвольной категории в категорию множеств. В некотором смысле, такие функторы задают представление категории в терминах множеств и функций.

Хорновский дизъюнкт — дизъюнктивный одночлен с не более чем одним положительным литералом. Изучены Альфредом Хорном (англ. Alfred Horn) в 1951 году в связи с их важной ролью в теории моделей и универсальной алгебре. Впоследствии стали основой для языка логического программирования Пролог, в котором программа являются непосредственно набором хорновских дизъюнктов, а также нашли важные приложения в конструктивной логике и теории сложности вычислений.

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

В общей алгебре, поле k называется совершенным если выполняется одно из следующих эквивалентных условий...

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

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

Категория абелевых групп (обозначается Ab) — категория, объекты которой — абелевы группы, а морфизмы — гомоморфизмы групп. Является прототипом абелевой категории., в действительности, любая малая абелева категория может быть вложена в Ab.

Надстрочный знак, ве́рхний и́ндекс, суперскри́пт (англ. super script) (типографика) — знак, записанный выше основной строки. Применяется, например, при записи математических и химических формул.

Подробнее: Верхний индекс

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

Перенос и заём в арифметике — приёмы, применяемые в арифметических алгоритмах позиционных систем счисления при выполнении операций сложения и вычитания соответственно, а также (в составе тех же сложения и вычитания) и иных арифметичких операций. Перенос можно понимать как выделение умножения на основание системы счисления в отдельное слагаемое, с последующей перегруппировкой слагаемых.

Вариа́нтность (лат. varians, род. variantis — «изменяющийся») — в языкознании: фундаментальное свойство способа существования и функционирования единиц языка и языковой системы в целом. Характеризуется с помощью понятий варианта, инварианта, варьирования.

Промежуточная сумма — это сумма последовательности чисел, которая обновляется каждый раз, когда новое число добавляется к последовательности, увеличивая предыдущую промежуточную сумму на величину нового значения. Другое название термина — частичная сумма.

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

При́знак Паска́ля — математический метод, позволяющий получить признаки делимости на любое число. Своего рода «универсальный признак делимости».

В математике степень простого числа — это простое число, возведённое в целую положительную степень.

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

Теория топосов — раздел теории категорий, изучающий топосы — категории с определёнными дополнительными структурами, и математические (категорные) методы, связанные с топосами.

Область главных идеалов — это область целостности, в которой любой идеал является главным. Более общее понятие — кольцо главных идеалов, от которого не требуется целостности (однако некоторые авторы, например Бурбаки, ссылаются на кольцо главных идеалов как на целостное кольцо).

Дифференциа́л (от лат. differentia — разность, различие) в математике — линейная часть приращения дифференцируемой функции или отображения.

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

О́белюс, обел (÷) (лат. obelus — от греч. ὀβελός, тот же корень, что и обелиск) — небуквенный символ, внешне напоминающий объединение знаков минуса и двоеточия.

Равноме́рная непреры́вность в математическом и функциональном анализе — это свойство функции быть одинаково непрерывной во всех точках области определения.

Теорема о монотонной сходимости (теорема Беппо́ Ле́ви) — это теорема из теории интегрирования Лебега, имеющая фундаментальное значение для функционального анализа и теории вероятностей, где служит инструментом для доказательства многих положений. Даёт одно из условий при которых можно переходить к пределу под знаком интеграла Лебега, теорема позволяет доказать существование суммируемого предела у некоторых ограниченных функциональных последовательностей.

В теории представлений групп Ли и алгебр Ли, фундаментальное представление — это неприводимое конечномерное представление полупростой группы Ли или алгебры Ли, старший вес которого является фундаментальным весом. Например, определяющий модуль классической группы Ли является фундаментальным представлением. Любое конечномерное неприводимое представление полупростой группы Ли или алгебры Ли полностью определяется своим старшим весом (теорема Картана) и может быть построено из фундаментальных представлений...

Подробнее: Фундаментальное представление

Машинопи́сный апостро́ф (apostrophe, apostrophe-quote) — условное название знака, встречающегося на клавиатуре большинства пишущих машин с латинским шрифтом и компьютерных дисплеев. По историческим причинам лишь машинописный апостроф имеется на компьютерных клавиатурах и в 7-битовой кодировке ASCII. В качестве типографского символа он является суррогатом апострофа, кавычек, знака ударения, штриха (знака производной в математике, знака угловых минут и т. п.) и др. Часто смешивается с машинописным...

В теории категорий множества Hom (то есть множества морфизмов между двумя объектами) позволяют определить важные функторы в категорию множеств. Эти функторы называются функторами Hom и имеют многочисленные приложения в теории категорий и других областях математики.

Подробнее: Функтор Hom

Перебор делителей (пробное деление) — алгоритм факторизации или тестирования простоты числа путём полного перебора всех возможных потенциальных делителей.

Паде́жная грамма́тика, «ролева́я грамматика» — метод описания семантики предложения (за исключением модальных и перформативных элементов) как системы семантических валентностей, в которой значение вершинного глагола диктует роли («падежи»), исполняемые именными составляющими. Иногда рассматривается как одна из разновидностей порождающей семантики:114 (наряду с направлением, представленным Дж. Мак-Коли, Дж. Лакоффом и другими учёными).

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я