Теория формальных грамматик и языков

Язык - это система правил описания явлений природы, общества или сознания человека. Выделяют синтаксис и семантику описания явлений с помощью конкретного языка.

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

Грамматика - это правила построения сообщений на каком-то языке. Грамматика основана на синтаксисе.

Формальные и формализованные языки. Формальный язык - это язык, для которого синтаксис (форма описания) однозначно определяет семантику (смысл описания), т. е. это язык, обладающий свойством однозначности смысла описания. Вот пример, демонстрирующий, что естественный русский язык формальным не является. Предложение: "Я встретил ее на поляне с цветами" с точки зрения формальных правил построения предложений в русском языке (синтаксиса) верное предложение, а с точки зрения его содержания (семантики) предложение может пониматься не однозначно:

1. цветы были у меня;

2. цветы были у нее;

3. цветы были на поляне.

Все языки общения человека и компьютера - формальные языки. Компьютер должен однозначно "понимать", что от него хотят. В частности, все языки программирования являются формальными, например, Fortran, Basic, Pascal, C, Java.

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

Синтаксическая ошибка - это нарушение каких-либо формальных правил языка при записи сообщений, программ, команд и т. п. Предложение "Карова гуляет па лугу" с точки зрения правил русского языка содержит 2 синтаксические ошибки, они подчеркнуты. Если бы в процессе программирования было бы написано, например, Rait вместо Write или Fankshion вместо Function, то это были бы синтаксические ошибки.

Выявление синтаксических ошибок трудностей не представляет, поскольку это делается компьютером автоматически в процессе программирования. Формальные правила языка компьютер "знает" и автоматически выделяет области текста программы, где есть синтаксические ошибки, облегчая для программиста процесс их устранения. Выполнение программы невозможно пока в ней есть есть хоть одна синтаксическая ошибка!

Семантическая ошибка - это нарушение смысла при синтаксически верном описании каких-либо явлений, программ, команд и т. п. Предложение "Корова громко лает" верное предложение с точки зрения синтаксиса русского языка, а с точки зрения семантики нет. Примером семантической ошибки при программировании на языке Basic может служить, например, написание команды P = F + S вместо P = F + 5. Букву S легко перепутать с цифрой 5. Из-за семантических ошибок формально верная программа работает, но делает не совсем то, что от нее требуется.

Естественно, семантические ошибки автоматически обнаружить компьютер не в состоянии, их обнаружить может только человек в результате изучения работы программы в разных режимах. В очень сложных системах (например, в MS Windows) семантические ошибки устраняются годами в процессе эксплуатации, а тысячи их так и остаются невыявленными. Именно из-за семантических ошибок в управляющих программах могут разоряться банки, сталкиваться поезда, сбиваться с курса ракеты, самолеты и т. п.

Математическая логика

Математическая логика, как и алгебра, занимается вычислением значения выражений. Пример: требуется определить значение алгебраического выражения x² + y² + 5 при x=2, y=3. Решение: 2² + 3² + 5 = 4 + 9 + 5 = 18.

Логические выражения или условия могут иметь только два значения: True (Истина) или False (Ложь). Пример: требуется определить значение логического выражения x² + y² > 5 при x=0, y=2 и при x=3, y=4. Решение: При x=0, y=2 имеем 0² + 2² > 5, т. е. 4 > 5 - это ложь. При x=3, y=4 имеем 3² + 4² > 5, 9 + 16 > 5, т. е. 25 > 5 - это истина. Логические выражения иногда называют высказываниями, а вычисление их значений - исчислением высказываний. Например, высказывание "Коровы умеют мяукать" имеет значение False (Ложь).

Сравнение текстовых величин и операции над ними. Тексты равны, если они содержат одинаковое количество символов и соответственно равны все эти символы. Например, равны тексты A и B, где A = "Роман" и B = "Роман". Тексты же "Роман", "РОМАН", "Романы" не равные тексты.

Текст "cat" меньше, чем "dog", поскольку символ "c" меньше символа "d". Дело в том, что и в кодировке ASCII, и в кодировке UNICODE символ "c" имеет код 99, а символ "d" - 100. Текст "cat" меньше, чем "cut". При равенстве первых символов проверяются вторые и т. д. В данном случае код "a" - 97, код "u" - 117. Текст "Роман" меньше, чем "Романы", так как отсутствие соответствующего символа для проверки считается как бы нулевым кодом.

И в кодировке ASCII, и в кодировке UNICODE наименьшие коды имеют невидимые спецсимволы (конец строки, конец страницы, пробел и т. п.), затем идут цифры и вспомогательные символы (точка, запятая, плюс, минус и т. п.), затем - большие английские буквы по алфавиту (A-Z), затем - малые английские буквы по алфавиту (a-z). Затем русские буквы, причем тут все зависит от кодировки и кодовой страницы. В кодировках UNICODE и ASCII (Windows-1256, MS-DOS-866) сначала - большие буквы по алфавиту (А-Я), затем - малые буквы по алфавиту (а-я). В кодировке ASCII (КОИ-8) русские буквы, совпадающие по написанию с английскими, имеют те же коды, переменными символами являются лишь русские буквы, не совпадающие по написанию с английскими, причем последовательность их кодов никак не соответствует русскому алфавиту.

Над текстами определена лишь операция конкатенации - склеивания двух текстов в один. Для нее можно использовать знаки как "+", так и "&". Вот примеры.

"Замяукал" & " кот-" & "Васька!" = "Замяукал кот-Васька!"

"5" + "3" = "53"

Последний пример демонстрирует разницу между числовыми и символьными величинами. В языке Basic существуют специальные функции перевода числовых величин в текстовые и наоборот. Val переводит текст в число. Например, Val("53.87")=53.87, Val("75")=75, Val("dog")=0. В тексте "dog" нет числа. Str переводит число в текст. Например, Str(-75.3)="-75.3"

Простые условия - это условия, получаемые на основе специального шаблона. Формула 1.2 дает нам этот шаблон.

Формула 1.2. Шаблон простого условия

A s B

Здесь: A и B - произвольные алгебраические выражения;
s - произвольная операция сравнения больше(>), меньше(<), равно (=), больше или равно(>=), меньше или равно(<=),
не равно(<>)

Таким образом, все приведенные выше условия являются простыми.

Составные условия - это условия, которые получаются из простых путем использования логических операций (Not - Отрицание, And - И, Or - Или) и круглых скобок для группировки.

Примеры: (Not 5>3) = False - отрицание того, что 5>3 есть Ложь. (5>3 And 3<1) = False - Истина И Ложь есть Ложь. (5>3 Or 3<1) = True - Истина Или Ложь есть Истина.

Правила вычисления выражений, содержащих операции Not, And, Or определяются приведенными ниже таблицами истинности.

Таблица 1.4. Таблица истинности для Not

Таблица 1.5. Таблица истинности для And

Таблица 1.6. Таблица истинности для Or

Операции имеют следующие приоритеты:

- самый высший - возведение в степень, знаки функций Sin, Cos и т. п.;

- ниже - операции умножения и деления;

- еще ниже - операции сложения, конкатенации и вычитания;

- еще ниже - операции сравнения;

- еще ниже - операция Отрицания (Not);

- еще ниже - операция И (And);

- еще ниже - операция Или (Or).

Пример. Как понять следующее выражение?

3 * Sin (X) > 2 And Not X=Y

Его следует понимать как указано ниже.

((3 * (Sin (X))) > 2) And (Not (X=Y))

Численные методы

При решении математических задач выделяют две большие группы методов: аналитические и численные.

Рисунок 1.6. Пример применения численных методов

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

Задача: вычислить площадь треугольника, у которого высота h проведена к стороне a, причем h = 6.5 см, a = 5.6 см.

Аналитическое решение: вспомним формулу площади треугольника: S = a * h / 2, где высота h проведена к стороне a. В нашем случае имеем S = 5.6 * 6.5 / 2 = 18.2 см².

Таким образом, практически все методы, которым обучают в средней школе, являются аналитическими.

Преимущества аналитических методов: мы получаем точное решение задачи; для решения не требуется компьютер, нужна лишь ручка, бумага и, возможно, калькулятор.

Недостаток аналитических методов: большинство задач, которые ставит нам практика (в том числе практика следователя-криминалиста, эксперта) аналитически решить в принципе невозможно, аналитически решаемые задачи практически встречаются лишь в учебниках и задачниках.

Численные методы - это методы приближенного решения широкого класса математических задач. При этом для повышения точности решения необходимо произвести больший объем вычислений.

Задача: вычислить площадь фигуры, ограниченной кривой линией. Рисунок 1.6 представляет нам эту фигуру, ограниченную жирной кривой линией.

Численное решение: представим фигуру в виде семейства треугольников. Они показаны на рисунке тонкими прямыми линиями. Вычислим площадь каждого треугольника и возьмем их сумму в качестве решения нашей задачи.

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

Преимущество численных методов: мы можем решать широкий класс математических задач, решение которых необходимо для практических целей.

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

Микроэлектроника

Микроэлектроника - это наука, изучающая физические методы с целью разработки более эффективных технологий производства сверхбольших интегральных схем (СБИС).

СБИС - это электронные схемы, содержащие более 1000 элементов на одном чипе, т. е. на одной кремниевой пластинке. Элементами могут быть сопротивления, индуктивности, емкости, диоды и, самое главное, транзисторы. СБИС - это основа элементной базы современной компьютерной техники.

Например, современная технология производства микропроцессоров основана на 0.13 микронном (мкн) техпроцессе. Это значит, что 0.13 мкн - это среднее расстояние между двумя элементами схемы на чипе. Приблизительно 2 года назад наиболее распространенным был 0.18 мкн техпроцесс. По-видимому, через 2 года наиболее распространенным будет 0.09 мкн техпроцесс. Новые техпроцессы вызывают снижение стоимости чипов, рост скорости их работы, меньшую степень нагревания, а значит, более высокую надежность чипов.

После изготовления чипов начинается их тестирование. При этом определяется, на какой максимальной скорости они могут работать устойчиво и без сбоев. Этой скоростью и маркируется чип. При внедрении нового техпроцесса, как правило, процент чипов высокого качества очень мал, велик процент низкокачественных чипов и брака. При освоении техпроцесса процент чипов высокого качества растет, а процент низкокачественных чипов и брака уменьшается.

Чем отличается процессор Pentium 4 Northwood 2800 от процессора Pentium 4 Northwood 2400? Их "пекли" вместе, но по случайному стечению обстоятельств первый получился более качественным, чем второй. В настоящее время Pentium 4 Northwood 2400 рассматривается как main-strim процессор, т. е. наиболее распространенный и покупаемый, он относительно дешев, наибольший процент выхода при производстве сейчас приходится именно на чип такого качества. Вероятно, через полгода main-strim процессором станет Pentium 4 Northwood 2800, процент выхода которого в настоящее время мал.

Системотехника

Системотехника - это наука, изучающая методы проектирования электронных схем для СБИС. Например, электронная схема современного микропроцессора содержит десятки миллионов электрических элементов: сопротивления, индуктивности, емкости, диоды и, самое главное, транзисторы.

А как рассчитать такую схему и при этом учесть взаимодействие всех составляющих ее элементов? Естественно, человек для этого использует специальные компьютерные программы - системы автоматизированного проектирования СБИС. Несмотря на это, здесь требуется огромный интеллектуальный труд человека, он и составляет основную долю стоимости нового микропроцессора.

Поэтому, когда в продаже только-только появляется новый микропроцессор, то в этот момент его цена крайне высока. Нужно окупить интеллектуальные затраты, научные исследования в том числе. Однако через год-полтора они окупаются, и цена падает в несколько раз.