Формальный язык: различия между версиями

В [[математическая логика|математической логике]] и [[информатика|информатике]] '''формальный язык''' — это [[множество]] конечных [[Слово (математика)|слов]] (''[[синоним|син]].''строк, [[строкаКортеж|строкцепочек]], цепочек) над конечным [[Алфавит (информатика)#В математике|алфавитом]]. Понятие языка чаще всего используется в теории [[АбстрактныйТеория автоматавтоматов|теории автоматов]], [[теория вычислимости|теории вычислимости]] и [[теория алгоритмов|теории алгоритмов]]. Научная теория, которая имеет дело с этимиэтим объектамиобъектом, называется ''[[теория формальных языков|теорией формальных языков]]''.

В [[теория моделей|теории моделей]] '''язык''' соответствует не языку в информатике, а скорее алфавиту. Язык состоит из множеств символов, [[Функция (математика)|функций]] и [[отношениеОтношение (математика)|отношений]] вместе с их [[арность]]ю, а также множество [[переменная|переменных]]. Каждое из этих множеств может быть бесконечным. Из языка вместе с [[Исчисление высказываний|универсальными логическими символами]] составляются логические высказывания.

* Словами, порождёнными некоторой [[формальная грамматика|формальной грамматикой]] (см. [[иерархия Хомского]]).

* Словами, порождёнными [[регулярные выражения|регулярным выражением]].

* Словами, распознаваемыми некоторым [[конечный автомат|конечным автоматом]].

* Словами, порождёнными [[Форма Бэкуса — Наура|БНФ-конструкцией]].