Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Конечные автоматы и регулярные языки

Конечные автоматы и регулярные языки


В этом разделе мы начинаем изложение элементов теории формальных языков.


Говоря "формальный язык", мы имеем в виду то, что приведенные здесь результаты используются прежде всего при описании искусственных языков, придуманных людьми для специальных целей, например языков программирования. Но непреодолимой преграды между специально придуманными искусственными (формальными) языками и стихийно возникающими и развивающимися естественными языками не существует. Оказывается, что естественные языки характеризуются сложными грамматическими правилами, т.е. довольно жестко формализованы, а даже самый "научно разработанный" язык программирования содержит "темные места", однозначное понимание которых является проблемой.


Изучая языки, следует иметь в виду три основных аспекта.


Первый из них — синтаксис языка. Язык — это какое-то множество "слов", где "слово" есть определенная конечная последовательность "букв" — символов какого-то заранее фиксированного алфавита. Термины "буква" и "слово" могут пониматься по-разному (математическое определение этих терминов будет дано ниже). Так, "буквами" могут быть действительно буквы алфавита какого-нибудь естественного или формального языка, например русского языка или языка программирования "Паскаль". Тогда "словами" будут конечные последовательности "букв": "крокодил", "integer". Такие слова называют "лексемами". Но "буквой" может быть "слово" ("лексема") в целом. Тогда "слова" — это предложения естественного языка или программы языка программирования. Если фиксировано какое-то множество "букв", то не каждая их последовательность будет "словом", т.е. "лексемой" данного языка, а только такая последовательность, которая подчиняется определенным правилам. Слово "крыкадил" не является лексемой русского языка, а слово "iff" не является лексемой в "Паскале". Предложение "Я люблю ты" не является правильным предложением русского языка, точно так же, как и запись "x:==t" не есть правильно написанный оператор присваивания "Паскаля". Синтаксис языка и представляет собой систему правил, в соответствии с которыми можно строить "правильные" последовательности "букв". Каждое слово языка характеризуется определенной структурой, специфичной именно для данного языка. Тогда необходимо, с одной стороны, разработать механизмы перечисления, или порождения, слов с заданной структурой, а с другой — механизмы проверки того, что данное слово принадлежит данному языку. Прежде всего именно эти механизмы и изучает классическая теория формальных языков.


Слово "синтаксис" происходит от древнегреческих "syn" — "вместе" и "taxis" — "порядок, строй". Таким образом, синтаксис можно понимать как "составление".


Второй аспект — семантика языка. Семантика предполагает сопоставление словам языка некоего "смысла", "значения". Например, записывая математическую формулу, мы должны соблюдать определенные синтаксические правила (расстановка скобок, правописание символов, порядок символов и т.п.), но, кроме этого, формула имеет вполне определенный смысл, что-то обозначает.


От древнегреческих слов "sema" — "знак, знамение" и "semanticos" — " обозначающий ".


Язык — это средство общения, передачи информации. Если мы хотим, чтобы нас поняли, мы должны не только синтаксически правильно, соблюдая должный порядок букв в слове и слов в предложении, строить свою речь, но и заботиться об ее смысле, о тех идеях, которые мы выражаем в речи. Математические теории "смысла" появились сравнительно недавно, и мы очень коротко рассмотрим некоторые подходы к математическому описанию семантики языков программирования.


Наконец, третий аспект — прагматика языка. Прагматика связана с теми целями, которые ставит перед собой носитель языка: например, человек произносит речь, имея перед собой цели, связанные не с синтаксисом, не с семантикой языка, на котором он говорит или пишет, а, скажем, с получением за речь определенной суммы денег. Прагматика является уже скорее дисциплиной социально-философской, затрагивающей целеполагающую деятельность личности. Мы ни в малейшей степени не будем ее касаться.


От древнегреческих "pragma" — "дело, действие" и "pragmateia" — " деятельность ".


В этом разделе вначале будут рассмотрены основные понятия математической теории формальных языков, важнейшим среди которых является понятие порождающей грамматики, а затем — так называемые регулярные языки. Теория регулярных языков вместе с теорией конечных автоматов образует фундамент всей теории формальных языков.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved