Формален език: Разлика между версии
м меп, по-малко категории |
м warnfile Adding:sk,it |
||
Ред 24: | Ред 24: | ||
[[Категория:Формални езици|!]] |
[[Категория:Формални езици|!]] |
||
[[de:Formale Sprache]] |
[[de:Formale Sprache]] |
||
Ред 30: | Ред 29: | ||
[[es:Lenguaje formal]] |
[[es:Lenguaje formal]] |
||
[[fr:Langage formel]] |
[[fr:Langage formel]] |
||
[[it:Linguaggio formale]] |
|||
[[ja:形式言語]] |
|||
[[ja:形式言語]] |
|||
[[nl:Formele taal]] |
[[nl:Formele taal]] |
||
[[pl: |
[[pl:Język formalny]] |
||
[[sk:Formálny jazyk]] |
|||
[[zh:形式语言]] |
|||
[[zh:形式语言]] |
Версия от 15:36, 16 юни 2005
В обикновената ежедневна употреба говорим за формален език като за начин на говорене обусловен от нормираност, стегнатост, строгост, терминологичност и неемотивност на изказа. Една внимателна, акуратна речевост.
В математиката, логиката и компютърните науки, формален език е това множество от думи с крайна дължина (тоест буквени стрингове) извлечено от дадена крайна азбука. Научната теория, за която формалните изици са обект на изучаване се нарича теория на формалните езици.
Азбука може да бъде {c,d} и низ към/за тази азбука може да бъде cddddc. Типичен език на тази азбука, съдържащ стринга cddddc, ще бъде множеството от всички стрингове, които съдържат същият брой c и d символи.
Празната дума (низ с нулева дължина) е разрешен и често означаван като e, ε или Λ. Докато азбуката е крайно множество и всеки стринг има крайна дължина, то езикът може съвсем спокойно да се състои от безкрайно много срингове.
Някои примери за формални езици:
- множество на всички думи от {a,b}
- множество { an : n е естествено число по-голямо от единица} (където an означава a повторено n пъти)
- множество от синтактично правилни програми за даден програмен език
Формалният език може да бъде спицифизиран по много начини:
- Низ изведен от формална граматика (виж Йерархия на Чомски)
- Низ произведен от регулярен израз
- Низ приет от някаква автоматизация, например Машина на Тюринг
Няколко операции могат да създадат нови езици от дадени такива.
Например. Да вземем L1 и L2, които са езици имащи обща езбука.
- Конкатенацията на L1 и L2 е всички стрингове от типа vw, където v е стринг на L1 и w е стринг на L1
- Конюнкцията на L1 и L1 се състои от всички стрингове съдържащи се както в L1, така и в L1
и т.н.