Число́ — одно из основных понятий математики, используемое для количественной характеристики, сравнения, нумерации объектов и их частей.
Коне́чный автома́т (КА) в теории алгоритмов — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.
Комбинато́рика — раздел математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого множества в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется комбинаторной конфигурацией. Простейшими примерами комбинаторных конфигураций являются перестановки, сочетания и размещения.
Регуля́рные выраже́ния — формальный язык, используемый в компьютерных программах, работающих с текстом, для поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов. Для поиска используется строка-образец, состоящая из символов и метасимволов и задающая правило поиска. Для манипуляций с текстом дополнительно задаётся строка замены, которая также может содержать в себе специальные символы.
Ноль — целое число, которое при сложении с любым числом или вычитании из него не меняет последнее, то есть даёт результат, равный этому последнему; умножение любого числа на ноль даёт ноль.
Норма́льный алгори́тм (алгори́фм) Ма́ркова — один из стандартных способов формального определения понятия алгоритма. Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.
Форма́льный язы́к в математической логике, информатике и лингвистике — множество конечных слов над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
Код — взаимно однозначное отображение конечного упорядоченного множества символов, принадлежащих некоторому конечному алфавиту, на иное, не обязательно упорядоченное, как правило более обширное множество символов для кодирования передачи, хранения или преобразования информации.
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей — и задачи, которые они могут решать.
Контекстно-свободная грамматика — частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала.
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
Форма́льная систе́ма — результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причём все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других.
Языком Дика (англ. Dyck language) над 2n буквами называется контекстно-свободный язык, который состоит из сбалансированных наборов скобок n разных видов. Формально это язык над алфавитом {a1,b1,a2,b2,…an,bn}, порождаемый грамматикой S → ε, S → a1Sb1S,. .. , S → anSbnS.
Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.
Перечисли́мое мно́жество — множество конструктивных объектов, все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню 
арифметической иерархии, а корекурсивно перечислимые — уровню 
Сло́во формального языка — произвольная последовательность символов из данного алфавита. Число символов в слове 
называют его длиной и обозначают 
. Может допускаться существование единственного слова длины 0,, не содержащее ни одного символа.
Вычисли́мые фу́нкции — множество функций то есть отображения множества натуральных чисел во множество натуральных чисел, в математических обозначениях это 
которые могут быть реализованы некоторым, алгоритмом, описание которого конечно, например, описанием переходов некоторой машиной Тьюринга.
Омега-язык (ω-язык) — это множество бесконечно длинных последовательностей символов.
Метало́гика — изучение метатеории логики. В то время, как логика представляет собой исследование способов применения логических систем для рассуждения, доказательств и опровержений, металогика исследует свойства самих логических систем.
Исчисление Ламбека — формальная логическая система, предложенная в 1958 году Иоахимом Ламбеком, которая предназначена для описания синтаксиса естественных языков. С математической точки зрения исчисление Ламбека является фрагментом линейной логики.
