Формальный язык

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

Например, если алфавит задан как {a, b}, а язык L включает в себя все слова над ним, то слово ababba принадлежит L.

Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, ε или Λ.

Некоторые примеры формальных языков:

Формальный язык может быть определен по-разному, например:

Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что L1 и L2 являются языками, определёнными над некоторым общим алфавитом.

  • Связь L1L2 содержит все слова, удовлетворяющие форме vw, где v - это слово из L1, а w - слово из L2.
  • Пересечение L_1 \cap L_2 содержит все слова, содержащихся и в L1, и в L2.
  • Объединение L_1 \cup L_2 содержит все слова, содержащиеся или в L1, или в L2.
  • Дополнение языка L1 содержит все слова алфавита, которые не содержатся в L1.
  • Правое отношение L1 / L2 содержит все слова v, для которых существует слово w в L2 такое, что vw находидось в L1.
  • Замыкание Клини L_{1}^{*} содержит все слова, которые могут быть записаны в форме w1w2...wn, где wi содержится в L1 и n \ge 0. Следует помнить, что это включает и пустое слово ε, т.к. n = 0 допустимо по условию.
  • Обращение L_{1}^{R} содержит обращенные слова из L1.
  • Смешение L1 и L2 содержит все слова, которые могут быть записаны в форме v1w1v2w2...vnwn, где n \ge 1 и v1,...,vn являются такими словами, что связь v1...vn находится в L1, а w1,...,wn являются такими словами, что w1...wn находятся в L2.

Другие значения

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

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

Список литературы

  • Хопкрофт, Дж., Мотвани, Р., Дж. Ульман (2002). Введение в теорию автоматов, языков и вычислений. Addison Wesley. ISBN 5-8459-0261-4
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home