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

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

Формальный язык — множество всех конечных слов над конечным алфавитом.

Определение

Алфавитом называется непустое конечное множество, а его элементы - символами.

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

Формальным языком над алфавитом называется произвольное множество цепочек, образованных из символов алфавита .

Операции над формальными языками

Примеры формальных языков

Пусть . Тогда - это множество всех строк над латиницей. И любое подмножество является формальным языком.

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

  • ;
  • Множество всех слов, состоящих только из гласных (например, );
  • Множество всех слов, состоящих только из согласных;
  • Множество всех слов-перевертышей (палиндромов);
  • Множество ;
  • Пустое множество;
  • и т.д.

Литература

  1. The handbook of computational linguistics and natural language processing / edited by Alexander Clark, Chris Fox, and Shalom Lappin., ISBN 978-1-4051-5581-6

См. также