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

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

В математиката, логиката и компютърните науки, формален език е това множество от думи с крайна дължина (тоест буквени стрингове) извлечено от дадена крайна азбука. Научната теория, за която формалните езици са обект на изучаване се нарича теория на формалните езици. Азбука може да бъде {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₁

и т.н.

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

Gourt Home::Gourt :: Формален език