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

Во математиката, логиката и информатиката, формален јазик е јазик кој е дефиниран по прецизни математички формули.

Овој дијаграм ги покажува синтаксичките поделби во формалниот систем. Стринговите на симболи можат да бидат во голема мера поделени во бесмислени и добро формирани формули. Множеството добро формирани формули е поделено на теореми и не-теореми

Формалниот јазик L е карактеризиран како множество од F конечен број на елементи изградени од множество на симболи A. Математички, формалниот јазик е неподредениот пар L={A,F}. Постојат и други алтернативни опции на начини на кои може да се гледа на формалните јазици:

• Збир на зборови
• Збир на реченици

Во првиот случај множеството А се нарекува азбука L, а елементите на F се нарекуваат зборови. Во вториот случај множеството А се нарекува лексикон на вокабуларот F, додека елементите на F се нарекуваат реченици.

Математичката теорија на формалните јазици се нарекува теорија на формални јазици.

Иако вообичаено е да се слуша терминот формални јазици надвор од математиката, логиката и компјутерските науки кога се мисли на начин на изразување кое е стилизирано и прецизно во секојкдневниот говор, но смислата на формалните јазици е строго дефинирана според теоријата за формални јазици.

Како пример за формални јазици може да биде, азбука од типот на {a,b} и еден од стринговите на азбуката може да биде abbaababa.

Еден типичен јазик над таа азбука може да биде множество од стрингови кои имаат ист број на a и b.

Примери

• Множество на сите зборови составени од a,b;
• Множество {a^n}, каде што n е природен број и a^n е стринг за кој се мисли дека a се повторува n пати;
• Конечен јазик, како на пример {{a,b}{a,aa,bba}}
• Множество на синтаксички точни програми дадени во некој програмски јазик или
• Множество на влезови за конкретна Турингова машина.

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

• Стрингови создадени само од одредена формална граматика (хиерархија на Чомски);
• Стрингови опишани со регуларни изрази;
• Стрингови прифатливи од некои автомати, како Тјуринговата машина или конечните автомати;
• Стрингови одредени од да/не одговори.

Операции

• Конкатенација- L₁ L₂ ги содржи сите стрингови во форма vw каде што v е стринг од L₁ a w е стринг од L₂;
• Пресек- L₁∩ L₂ резултантниот јазик е оној јазик кој ги содржи сите ониe стрингови што ги има во L₁ и L₂;
• Унија- L₁ U L₂, резултантниот јазик ги содржи сите стрингови кои ги има и во L₁ и во L₂;
• Комплемент-С L₁ ги содржи сите стрингови од азбуката кои не се во L₁;
• Клини оператор- L₁* ги содржи сите стрингови кои можат да бидат напишани во формата w₁ w_(2….) w_n каде што w_{i U L1 и n ≥ 0.}

Се вклучува и празниот стринг ε.

• L₁^R- ги содржи сите обратни стрингови од L₁.

Наводи

• Hopcroft, J. & Ullman, J. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.
• Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics, III изд., PWN. , chapter 6 Algebra of formalized languages.
• Rozemberg, G. & Salomaa, A. (уред.) (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-3-540-61486-9.

Теорија на автоматите: формални јазици и формални граматики
Хиерархија на Чомски	Граматики	Јазици	Автомати
Тип-0	Неограничени	Рекурзивно преброиви	Тјурингова машина
—	(нема вообичаено име)	Рекурзивни	Одлучувач
Тип-1	Контексно-осетливи	Контексно-осетливи	Линеарни
—	Индексирани	Индексирани	Вгнезден склад
Тип-2	Контексно-слободни	Контексно-слободни	Недетерминистички потисни
—	Детерминистички конт.-слоб.	Детерминистички конт.-слоб.	Детерминистички потисни
Тип-3	Регуларни	Регуларни	Конечен
Секоја категорија на јазици или граматики е соодветно подмножество на категоријата над неа.