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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

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

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

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

Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что <math>L_{1}</math> и <math>L_{2}</math> являются языками, определёнными над некоторым общим алфавитом.

  • Конкатенация (сцепление) <math>L_{1}L_{2}</math> содержит все слова, удовлетворяющие форме <math>vw</math>, где <math>v</math> — это слово из <math>L_{1}</math>, а <math>w</math> — слово из <math>L_{2}</math>.
  • Пересечение <math>L_1 \cap L_2</math> содержит все слова, содержащихся и в <math>L_1</math>, и в <math>L_{2}</math>.
  • Объединение <math>L_1 \cup L_2</math> содержит все слова, содержащиеся или в <math>L_{1}</math>, или в <math>L_{2}</math>.
  • Дополнение языка <math>L_{1}</math> содержит все слова алфавита, которые не содержатся в <math>L_{1}</math>.
  • Правое отношение <math>L_{1}/L_{2}</math> содержит все слова <math>v</math>, для которых существует слово <math>w</math> в <math>L_{2}</math> такое, что <math>vw</math> находидось в <math>L_{1}</math>.
  • Замыкание Клини <math>L_{1}^{*}</math> содержит все слова, которые могут быть записаны в форме <math>w_{1}w_{2}...w_{n}</math>, где <math>w_{i}</math> содержится в <math>L_{1}</math> и <math>n \ge 0</math>. Следует помнить, что это включает и пустое слово <math>\epsilon</math>, так как <math>n = 0</math> допустимо по условию.
  • Обращение <math>L_{1}^{R}</math> содержит обращенные слова из <math>L_{1}</math>.
  • Смешение <math>L_{1}</math> и <math>L_{2}</math> содержит все слова, которые могут быть записаны в форме <math>v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}</math>, где <math>n \ge 1</math> и <math>v_{1},...,v_{n}</math> являются такими словами, что связь <math>v_{1}...v_{n}</math> находится в <math>L_{1}</math>, а <math>w_{1},...,w_{n}</math> являются такими словами, что <math>w_{1}...w_{n}</math> находятся в <math>L_{2}</math>.

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

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

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

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

Личные инструменты

Served in 0.049 secs.