Формален език

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

В математиката, логиката и компютърните науки, формален език е това множество от думи с крайна дължина (тоест буквени низове), извлечено от дадена крайна азбука. Научната теория, за която формалните езици са обект на изучаване, се нарича теория на формалните езици. Азбука може да бъде {c,d} и низ към/за тази азбука може да бъде cddddc. Типичен език на тази азбука, съдържащ низа cddddc, ще бъде множеството от всички низове, които съдържат същият брой c и d символи. Празната дума (низ с нулева дължина) е разрешен и често означаван като e, ε или Λ. Докато азбуката е крайно множество и всеки низ има крайна дължина, то езикът може съвсем спокойно да се състои от безкрайно много низове. Някои примери за формални езици:

  • множество на всички думи от {a,b};
  • множество { an : n е естествено число по-голямо от единица} (където an означава a повторено n пъти);
  • множество от синтактично правилни програми за даден програмен език.

Формалният език може да бъде специфициран по много начини:

Няколко операции могат да създадат нови езици от дадени такива.

Например: Да вземем L1 и L2, които са езици, имащи обща азбука.

  • Конкатенацията на L1 и L2 е всички низове от типа vw, където v е низ на L1 и w е низ на L1
  • Конюнкцията на L1 и L1 се състои от всички низове съдържащи се както в L1, така и в L1

и т.н.