Формален јазик
Од Википедија, слободна енциклопедија
Во математиката, логиката и компјутерската наука, формален јазик е јазик кој е дефиниран по прецизни математички формули. Формалниот јазик 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, 3rd ed., PWN. , chapter 6 Algebra of formalized languages.
- Rozemberg, G. & Salomaa, A. (eds.) (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-3-540-61486-9.
| Теорија на автомати: формални јазици и формални граматики | |||
|---|---|---|---|
| Хиерархија на Чомски |
Граматики | Јазици | автомати |
| Тип-0 | Нерестриктирани | Рекурзивно преброиви | Тјурингова машина |
| n/a | (нема вообичаено име) | Рекурзивни | Одлучувач |
| Тип-1 | Контексно осетливи | Контексно осетливи | Линеарни |
| n/a | Индексирани | Индексирани | Nested stack |
| Тип-2 | Контексно слободни | Контексно слободни | Недетерминистички Pushdown |
| n/a | Детерминистички контексно слободни | Детерминистички контексно слободни | Детерминистички Pushdown |
| Тип-3 | Регуларни | Регуларни | Конечен |
| Секоја категорија на јазици или граматики е соодветно подмножество на категоријата над неа. | |||
