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

В обикновената ежедневна употреба говорим за формален език като за начин на говорене обусловен от нормираност, стегнатост, строгост, терминологичност и неемотивност на изказа. Една внимателна, акуратна речевост.

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

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

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

• Низ изведен от формална граматика (виж Йерархия на Чомски)
• Низ произведен от регулярен израз
• Низ приет от някаква автоматизация, например Машина на Тюринг

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

Например. Да вземем L₁ и L₂, които са езици имащи обща азбука.

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

и т.н.