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

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

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

Определение

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

Произвольную конечную последовательность элементов множества \Sigma будем называть цепочкой (словом, или строкой) над алфавитом \Sigma. Слово может быть пустым (т.е. не содержать в себе ни одного символа. Непустая цепочка записывается в виде  \omega = a_1 \ldots a_n (где  a_1, \ldots, a_n \in \Sigma ) . Пустая цепочка обозначается символом  \varepsilon . Длина цепочки (т.е. количество символов, обращующих цепочку)  \omega = a_1 \ldots a_n обозначается  | \omega | .

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

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

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

Пусть \Sigma = \{ a,b,c, \ldots, ,y,z \}. Тогда \Sigma^{*} - это множество всех строк над латиницей. И любое подмножество \Sigma^{*} является формальным языком.

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

  • \Sigma^{*};
  • Множество всех слов, состоящих только из гласных (например,  \{ a, e, i, o, u \} );
  • Множество всех слов, состоящих только из согласных;
  • Множество всех слов-перевертышей (палиндромов);
  • Множество  \{ I, he, she, it, you, we, they \};
  • Пустое множество;
  • и т.д.

Литература

  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

См. также