Формален език: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Редакция без резюме |
кор.; форматиране: 3x нов ред, 4 интервала (ползвайки Advisor) |
||
Ред 1:
{{без източници}}
[[Файл:Formal languages-ru.svg|thumb|
В [[математика]]та, [[логика]]та и компютърните науки, '''формален език''' е това множество от думи с крайна дължина (тоест буквени низове), извлечено от дадена крайна [[азбука]]. Научната теория, за която формалните езици са обект на изучаване, се нарича ''теория на формалните езици''.
▲В [[математика]]та, [[логика]]та и компютърните науки, '''формален език''' е това множество от думи с крайна дължина (тоест буквени низове), извлечено от дадена крайна [[азбука]]. Научната теория, за която формалните езици са обект на изучаване, се нарича ''теория на формалните езици''.
Азбука може да бъде {c,d} и низ към/за тази азбука може да бъде cddddc. Типичен език на тази азбука, съдържащ низа cddddc, ще бъде множеството от всички [[низ]]ове, които съдържат същият брой c и d символи.
Празната дума (низ с нулева дължина) е разрешен и често означаван като ''e'', ε или Λ. Докато азбуката е крайно множество и всеки низ има крайна дължина, то езикът може съвсем спокойно да се състои от безкрайно много низове.
Някои примери за формални езици:
* множество на всички думи от {a,b};
* множество { ''a''<sup>''n''</sup> : ''n'' е естествено число по-голямо от единица} (където ''a''<sup>''n''</sup> означава ''a'' повторено ''n'' пъти);
* множество от синтактично правилни програми
Формалният език може да бъде специфициран по много начини:
Line 16 ⟶ 19:
* Низ, приет от някаква автоматизация, например [[Машина на Тюринг]].
Няколко операции могат да създадат нови езици от дадени такива.
Например: Да вземем ''L''<sub>1</sub> и ''L''<sub>2</sub>, които са езици, имащи обща азбука.
* Конкатенацията на ''L''<sub>1</sub> и ''L''<sub>2</sub> са всички низове от типа vw, където v е низ от ''L''<sub>1</sub> и w е низ от ''L''<sub>2</sub>
* Конюнкцията на ''L''<sub>1</sub> и ''L''<sub>2</sub> се състои от всички низове съдържащи се както в ''L''<sub>1</sub>, така и в ''L''<sub>2</sub>
| |||