Формальный язык: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Нет описания правки |
4th-otaku (обсуждение | вклад) смысловая последовательность, краткость, оформление |
||
Строка 1:
{{не путать|Функциональные стили речи|формальным стилем речи}}
В [[математическая логика|математической логике]] и [[информатика|информатике]] '''формальный язык''' — это [[множество]] конечных [[Слово (математика)|слов]] (''[[синоним|син]].'' [[строка|строк]], цепочек) над конечным [[Алфавит (информатика)#В математике|алфавитом]]. Понятие языка чаще всего используется в теории [[Абстрактный автомат|автоматов]], [[теория вычислимости|теории вычислимости]] и [[теория алгоритмов|теории алгоритмов]]. Научная теория, которая имеет дело с этими объектами, называется ''[[теория формальных языков|теорией формальных языков]]''.
В
Например, если алфавит задан как {''a'', ''b''}, а язык ''L'' включает в себя все слова над ним, то слово ''ababba'' принадлежит ''L''.▼
Некоторые примеры формальных языков:▼
* множество всех слов над {''a'', ''b''}▼
* множество <math>\{ a^n\}</math>, где ''n'' — [[простое число]], а <math>a^{n}</math> означает, что ''a'' повторяется ''n'' раз▼
* множество [[синтаксис|синтаксически]] корректных [[Компьютерная программа|программ]] в данном [[язык программирования|языке программирования]]▼
== Определение ==
Формальный язык может быть определен по-разному, например:
Строка 19 ⟶ 13 :
* Словами, порождёнными [[Форма Бэкуса — Наура|БНФ-конструкцией]]
▲
▲Некоторые примеры формальных языков:
▲* множество всех слов над {''a'', ''b''}
▲* множество <math>\{ a^n\}</math>, где ''n'' — [[простое число]], а <math>a^{n}</math> означает, что ''a'' повторяется ''n'' раз
▲* множество [[синтаксис|синтаксически]] корректных [[Компьютерная программа|программ]] в данном [[язык программирования|языке программирования]]
== Операции ==
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что <math>L_{1}</math> и <math>L_{2}</math> являются языками, определёнными над некоторым общим алфавитом.
Строка 29 ⟶ 32 :
* ''Обращение'' <math>L_{1}^{R}</math> содержит обращенные слова из <math>L_{1}</math>.
* ''Смешение'' <math>L_{1}</math> и <math>L_{2}</math> содержит все слова, которые могут быть записаны в форме <math>v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}</math>, где <math>n \ge 1</math> и <math>v_{1},...,v_{n}</math> являются такими словами, что связь <math>v_{1}...v_{n}</math> находится в <math>L_{1}</math>, а <math>w_{1},...,w_{n}</math> являются такими словами, что <math>w_{1}...w_{n}</math> находятся в <math>L_{2}</math>.
▲В терминологии [[теория моделей|теории моделей]], '''язык''' соответствует не языку в информатике, а скорее алфавиту. Язык состоит из множеств символов, [[Функция (математика)|функций]] и [[отношение|отношений]] вместе с их [[арность]]ю, а также множество [[переменная|переменных]]. Каждое из этих множеств может быть бесконечным. Из языка вместе с [[Исчисление высказываний|универсальными логическими символами]] составляются логические высказывания.
== Список литературы ==
* [[Хопкрофт, Джон|Хопкрофт, Дж.]], Мотвани, Р., Дж. Ульман (2002). ''Введение в теорию автоматов, языков и вычислений.'' Addison Wesley. ISBN 5-8459-0261-4
* ''Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.'' [http://trpl.narod.ru/TRYAP_BOOK_Details.htm Теория и реализация языков программирования] //М.: МЗ-Пресс, 2006 г., 2-е изд. ISBN 94073-094-9.
* [http://trpl.narod.ru/printed_guides.htm Избранные книги по курсам «Теория и реализация языков программирования» и «Формальные языки трансляций»]
[[Категория:Формальные языки|*]]
| |||