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

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

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

Формалниот јазик 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}}
  • Множество на синтаксички точни програми дадени во некој програмски јазик или
  • Множество на влезови за конкретна Турингова машина.

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

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

Операции

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

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

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

Наводи

  • 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 Регуларни Регуларни Конечен
Секоја категорија на јазици или граматики е соодветно подмножество на категоријата над неа.

Tags:

ИнформатикаЛогикаМатематика

🔥 Trending searches on Wiki Македонски:

Старецот и моретоКрушевоГостиварЈуда (син на Јаков)Збогум Румелија (ТВ-серија)Кристофер КолумбоДојранско ЕзероЦирозаРак на белите дробовиСолунВештачка интелигенцијаИнтернетАли АхметиНационален парк ГаличицаРобинзон КрусоХипофизаПлатен прометОткривање на АмерикаСловенска митологијаМРСААнтарктикСтарогрчка митологијаИлузијаСолиЗбунети годиниТрајче КрстескиХидроксидВалентностТрапезСписок на политички партии во МакедонијаБели мугриПрометејПетар Поп АрсовПертусисСончев СистемЛарингитисСписок на главни градови во ЕвропаКоличникБелградМагнетИзборна единица 1Список на планини во МакедонијаАрбен ТаравариБаба (планина)Биполарно растројствоБолоњски универзитетПрочкаВладимир ПутинСипанициДиносаурусЧовечки скелетРак на желудникТамара (снаа на Јуда)Водно растениеВикиОлимписки боговиМакедонски парламентарни избори (2020)ИшијасБалкански ПолуостровМорфологија на македонскиот јазикЕрусалимМакедонски хумористични народни приказни (книга)Судска властЦрвена лисицаАлександар III МакедонскиДемократски сојузРопство (Коле Неделковски)Алберт АјнштајнАнтибиотикРакометБедија БеговскаОпштина СарајМилиноРомео и ЈулијаДаме ГруевАцо ШоповМали сипанициОрхидеи🡆 More