А поскольку машина строится в собственной голове, вопросы «технической эффективности» такой машины никакой роли не играют. Единственный вопрос. Доберется ли машина до заключительного состояния? Пусть и через (воображаемый) миллион лет. Тогда задача разрешима!
Не будет преувеличением сказать, что нормальные алгорифмы Маркова создал А.А.Марков, член-корреспондент Академии Наук СССР из Москвы. Для восстановления единообразия, по праву автора, он назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое, как и слово ариФметика…
Смысл нормальных алгорифмов – принудительный обмен, порядок которого жестко задан.
Собственно алгоритм в нормальных алгорифмах задается НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК – очередностью правил «что на что менять». Лучше всего это показать на примере замены слов, тем более, что и сам Марков любую последовательность букв, какую ни в одном словаре не сыщешь, называл «словами». Так при наличии двух подстановок: меняющей «ха» на «ссон» и «мусс» на «сл» из «муха» можно сделать «слон».
Механизм нормальных алгоритмов настолько прост, что напоминает скорее детскую игру, чем математику. Но на самом деле это очень мощный механизм, поскольку через него можно выразить решение любой алгоритмически разрешимой задачи. И опять напомним, что это не следует воспринимать, как предложение решать любую задачу через подстановки (хотя на этих принципах работает замечательный язык программирования РЕФАЛ ). Это лишь означает, что любую алгоритмически разрешимую задачу МОЖНО представить в виде такой системы подстановок. А если нельзя (и вы это смогли доказать), то такая задача вообще не имеет алгоритма решения.
Лекция 12. ФОРМАЛЬНЫЕ ГРАММАТИКИ
Формальные грамматики – это хорошо развитый математический аппарат, позволяющий, кроме изучения «высоких материй», (математически) грамотно создавать языки программирования и писать компиляторы для этих языков.
Между естественными и формальными языками непреодолимая пропасть. Поэтому совпадение терминологии лучше считать случайным… Тем более, в рамках многогранного и разветвленного ЯЗЫКА МАТЕМАТИКИ раздел формальных грамматик и языков ориентирован прежде всего на проблемы построения компиляторов.
Формальный язык можно задать как некое множество слов. Слово, это последовательность символов. Любая компьютерная программа в этом случае тоже воспринимается как слово. Пробелы в ней – специальные символы, для которых на клавиатуре выделена самая длинная клавиша.
Словами данного языка может быть далеко не любая абракадабра, доступная клавиатуре. А только лексически и синтаксически (безупречно!) правильные программы. Безупречная с точки зрения грамматики программа может быть бесполезной, бессмысленной или даже вредной. Но за правильную работу программы формальная грамматика и компилятор не отвечают. (Повторим, математика обычно смыслом не занимается).
Поскольку и здесь, в формальных грамматиках и языках, математика за смысл не отвечает. Есть специальное направление в теоретическом программировании, когда на формальном языке (обычно на языке предикатов и его диалектах) описывается, что должна делать программа. На основании этого описания специальная система синтезирует программу. Однако, это тема совсем другого разговора. Тем более, что ошибок в описании того, что должна делать программа, человек допускает больше, чем при написании программы непосредственно.
Для того, чтобы задать грамматику, надо задать множества ТЕРМИНАЛЬНЫХ и НЕТЕРМИНАЛЬНЫХ символов. Терминальные символы это символы используемые в языке. Нетерминальные (промежуточные) символы – это символы, используемые в создании (порождении) слов языка. А создаются слова по грамматическим правилам. И каждое слово, напомним, это с точки зрения программиста – программа, записанная исключительно терминальными символами. Далее задаются ГРАММАТИЧЕСКИЕ ПРАВИЛА . Они очень напоминают подстановки в алгорифмах Маркова. Но в отличие от последних порядок применения грамматических правил произвольный. Применение правила заключается в замене в преобразуемой строке какой-то последовательности символов, совпадающей с левой частью какого-то правила, правой частью (последовательностью символов) этого правила.
Введем в оборот из чисто эстетических соображений еще один красивый термин – СЕНТЕНЦИАЛЬНАЯ ФОРМА . Дело в том, что при построении программ в формальных грамматиках всегда танцуют от одного начального нетерминального символа. Обозначим этот символ «программа». Вместо этого символа по одному из грамматических правил происходит подстановка соответствующей правой части, которая может содержать последовательность из каких-то нетерминальных и терминальных символов. Кстати, такой процесс называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ . Любой их появившихся нетерминальных символов может быть заменен по подходящему грамматическому правилу какой-то цепочкой символов. То есть начальный нетерминальный символ «программа» последовательно превращается во все более длинную цепочку символов. И так вплоть до того момента, когда в последовательности символов останутся только терминальные символы. То есть будет получено слово данного языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ ). Все последовательности символов, которые в процессе непосредственных порождений находятся между начальным нетерминальным символом и конечным предложением и называются сентенциальными формами. А нам остается радоваться, что английский язык нам неродной.
Компилятор, получив программу, выполняет обратную работу. Пред'явленное предложение он свертывает по грамматическим правилам (теперь двигаясь от правой части правила к левой) начального символа «программа».
Обычно существует огромное количество вариантов как порождения, так и свертывания. Если свертывание потерпело неудачу, то должны исследоваться другие варианты. Слово будет признано НЕ принадлежащим данному языку (грамматике), если ни один из вариантов свертывания не приведет к удаче. Поскольку такой перебор вариантов на практике как правило неприемлем, то и грамматики пытаются придумывать не случайные, а с полезными свойствами. А способы свертывания (распознавания) используют эти хорошие свойства, чтобы минимизировать или вообще исключить блуждания.
Есть достаточно грубая, но, все равно, полезная в первом приближении классификация грамматик, принадлежащая Хомскому. Он их делит на три типа, если не считать нулевого. К нулевому он относит грамматики с грамматическими правилами произвольного вида. А раз нет никаких ограничений, то там может быть все, что угодно и, следовательно, анализировать их невозможно.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Не будет преувеличением сказать, что нормальные алгорифмы Маркова создал А.А.Марков, член-корреспондент Академии Наук СССР из Москвы. Для восстановления единообразия, по праву автора, он назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое, как и слово ариФметика…
Смысл нормальных алгорифмов – принудительный обмен, порядок которого жестко задан.
Собственно алгоритм в нормальных алгорифмах задается НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК – очередностью правил «что на что менять». Лучше всего это показать на примере замены слов, тем более, что и сам Марков любую последовательность букв, какую ни в одном словаре не сыщешь, называл «словами». Так при наличии двух подстановок: меняющей «ха» на «ссон» и «мусс» на «сл» из «муха» можно сделать «слон».
Механизм нормальных алгоритмов настолько прост, что напоминает скорее детскую игру, чем математику. Но на самом деле это очень мощный механизм, поскольку через него можно выразить решение любой алгоритмически разрешимой задачи. И опять напомним, что это не следует воспринимать, как предложение решать любую задачу через подстановки (хотя на этих принципах работает замечательный язык программирования РЕФАЛ ). Это лишь означает, что любую алгоритмически разрешимую задачу МОЖНО представить в виде такой системы подстановок. А если нельзя (и вы это смогли доказать), то такая задача вообще не имеет алгоритма решения.
Лекция 12. ФОРМАЛЬНЫЕ ГРАММАТИКИ
Формальные грамматики – это хорошо развитый математический аппарат, позволяющий, кроме изучения «высоких материй», (математически) грамотно создавать языки программирования и писать компиляторы для этих языков.
Между естественными и формальными языками непреодолимая пропасть. Поэтому совпадение терминологии лучше считать случайным… Тем более, в рамках многогранного и разветвленного ЯЗЫКА МАТЕМАТИКИ раздел формальных грамматик и языков ориентирован прежде всего на проблемы построения компиляторов.
Формальный язык можно задать как некое множество слов. Слово, это последовательность символов. Любая компьютерная программа в этом случае тоже воспринимается как слово. Пробелы в ней – специальные символы, для которых на клавиатуре выделена самая длинная клавиша.
Словами данного языка может быть далеко не любая абракадабра, доступная клавиатуре. А только лексически и синтаксически (безупречно!) правильные программы. Безупречная с точки зрения грамматики программа может быть бесполезной, бессмысленной или даже вредной. Но за правильную работу программы формальная грамматика и компилятор не отвечают. (Повторим, математика обычно смыслом не занимается).
Поскольку и здесь, в формальных грамматиках и языках, математика за смысл не отвечает. Есть специальное направление в теоретическом программировании, когда на формальном языке (обычно на языке предикатов и его диалектах) описывается, что должна делать программа. На основании этого описания специальная система синтезирует программу. Однако, это тема совсем другого разговора. Тем более, что ошибок в описании того, что должна делать программа, человек допускает больше, чем при написании программы непосредственно.
Для того, чтобы задать грамматику, надо задать множества ТЕРМИНАЛЬНЫХ и НЕТЕРМИНАЛЬНЫХ символов. Терминальные символы это символы используемые в языке. Нетерминальные (промежуточные) символы – это символы, используемые в создании (порождении) слов языка. А создаются слова по грамматическим правилам. И каждое слово, напомним, это с точки зрения программиста – программа, записанная исключительно терминальными символами. Далее задаются ГРАММАТИЧЕСКИЕ ПРАВИЛА . Они очень напоминают подстановки в алгорифмах Маркова. Но в отличие от последних порядок применения грамматических правил произвольный. Применение правила заключается в замене в преобразуемой строке какой-то последовательности символов, совпадающей с левой частью какого-то правила, правой частью (последовательностью символов) этого правила.
Введем в оборот из чисто эстетических соображений еще один красивый термин – СЕНТЕНЦИАЛЬНАЯ ФОРМА . Дело в том, что при построении программ в формальных грамматиках всегда танцуют от одного начального нетерминального символа. Обозначим этот символ «программа». Вместо этого символа по одному из грамматических правил происходит подстановка соответствующей правой части, которая может содержать последовательность из каких-то нетерминальных и терминальных символов. Кстати, такой процесс называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ . Любой их появившихся нетерминальных символов может быть заменен по подходящему грамматическому правилу какой-то цепочкой символов. То есть начальный нетерминальный символ «программа» последовательно превращается во все более длинную цепочку символов. И так вплоть до того момента, когда в последовательности символов останутся только терминальные символы. То есть будет получено слово данного языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ ). Все последовательности символов, которые в процессе непосредственных порождений находятся между начальным нетерминальным символом и конечным предложением и называются сентенциальными формами. А нам остается радоваться, что английский язык нам неродной.
Компилятор, получив программу, выполняет обратную работу. Пред'явленное предложение он свертывает по грамматическим правилам (теперь двигаясь от правой части правила к левой) начального символа «программа».
Обычно существует огромное количество вариантов как порождения, так и свертывания. Если свертывание потерпело неудачу, то должны исследоваться другие варианты. Слово будет признано НЕ принадлежащим данному языку (грамматике), если ни один из вариантов свертывания не приведет к удаче. Поскольку такой перебор вариантов на практике как правило неприемлем, то и грамматики пытаются придумывать не случайные, а с полезными свойствами. А способы свертывания (распознавания) используют эти хорошие свойства, чтобы минимизировать или вообще исключить блуждания.
Есть достаточно грубая, но, все равно, полезная в первом приближении классификация грамматик, принадлежащая Хомскому. Он их делит на три типа, если не считать нулевого. К нулевому он относит грамматики с грамматическими правилами произвольного вида. А раз нет никаких ограничений, то там может быть все, что угодно и, следовательно, анализировать их невозможно.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16