Билет 23

1. Метод наименьших квадратов при нелинейной параметризации модели.

Модель объекта задана в виде линейной комбинации известных (базисных) функций

Вектор-столбец значений выхода модели (в моменты времени ) имеет вид

.

Параметры находим по критерию наименьших квадратов:

Необходимое условие минимума (где - градиент от по ) приводит к системе линейных алгебраических уравнений

которая имеет единственное решение, если матрица невырождена.

Решение системы:

Когда помеха некоррелированна и измерения равноточные, система уравнений приобретает вид:

Этому уравнению можно придать другой вид, основанный на понятии скалярного произведения функций:

Теперь система уравнений запишется в форме:

(1)

Если измерения выхода объекта некоррелированны, но неравноточны, то система сохраняет свой вид. Меняется лишь понятие скалярного произведения (в него вводятся веса ):

При коррелированных измерениях система также эквивалентна (1) со следующим скалярным произведением:

,

2. Лексический анализ. Регулярные грамматики и выражения, конечные автоматы.

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

Кроме того, на фазе лексического анализа обрабатываются пробелы, удаляются комментарии и другие символы, не имеющие смысла для следующих фаз.

Лексический анализатор – это часть транслятора, получающая на вход исходный текст программы и выделяет в нем лексемы. Лексический анализатор работает с объектами, подобными идентификаторам или константам. ЛА является достаточно простым процессом и похож на то, как человек читает текст программы. Благодаря этому, символы языка (лексемы) почти всегда можно представить с помощью РГ или РВ. На основе РГ или РВ нетрудно построить необходимое устройство распознавания. Инструменты для их создания доступны и легки в использовании. Помимо распознавания лексем лексический анализатор также может выполнять удаление комментариев, введение номеров строк, вычисление констант и др.

Абстрактное устройство распознавания (распознаватель) состоит из 3 частей: Входная лента бесконечной длины, Устройство управления Вспомогательная память.

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

Доступ - f , Преобразование - g

В информатике, регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.

Регулярная грамматика может быть задана набором правил как левая или правая регулярная грамматика.

правая регулярная грамматика - все правила могут быть в одной из следующих форм:

1. A → a

2. A → aB

3. A → ε

левая регулярная грамматика - все правила могут быть в одной из следующих форм:

1. A → a

2. A → Ba

3. A → ε

где

• заглавные буквы (A, B) обозначают нетерминалы из множества N

• строчные буквы (a, b) обозначают терминалы из множества Σ

• ε - пустая строка, т.е. строка длины 0

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

Ограниченность

Любая контекстно-свободная грамматика может быть легко преобразована в вид, в котором правила состоят только из лево-регулярных или право-регулярных . Следовательно, такие грамматики могут выразить все контекстно-свободные языки. Регулярные грамматики могут содержать либо лево-регулярные правила, либо право-регулярные, но не оба вида одновременно. Поэтому они могут описать лишь подмножество языков, называемых регулярными языками.

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

Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы:

• (пустое множество) ∅.

• (пустая строка) ε обозначает строку, не содержащую ни одного символа.

• (символьный литерал) «a», где a — символ алфавита Σ.

и следующие операции:

• (сцепление, конкатенация) RS обозначает множество {αβ | α ∈ R & β ∈ S}. Например, {«boy», «girl»}{«friend», «cott»} = {«boyfriend», «girlfriend», «boycott», «girlcott»}.

• (дизъюнкция, чередование) R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.^[4]

• (замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {«Go», «Russia»}* = {ε, «Go», «Russia», «GoGo», «GoRussia», «RussiaGo», «RussiaRussia», «GoGoGo», «GoGoRussia», «GoRussiaGo», …}.

Конечный автомат (КА) состоит из конечного множества состояний и переходов между ними, которые определяются считываемыми знаками из входной строки

Одно состояние определяется как начальное, а одно или более – как конечные

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

КА – это односторонний распознаватель без дополнительной памяти

Переходы оформляются в виде таблицы или графически, где для каждого состояния указывают следующее состояние и все возможные входные знаки

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего. Недетерминированный конечный автомат (НКА) является обобщением детерминированного.