Автор работы: Пользователь скрыл имя, 11 Апреля 2014 в 11:17, курсовая работа
C# — объектно-ориентированный язык программирования. Разработан в 1998—2001 годах группой инженеров под руководством Андерса Хейлсберга в компании Microsoft как основной язык разработки приложений для платформы Microsoft .NET Framework и впоследствии был стандартизирован как ECMA-334 и ISO/IEC 23270. Компилятор C# входит в стандартную установку .NET Framework. C# относится к семье языков с C-подобным синтаксисом, из них его синтаксис наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, атрибуты, события, свойства, обобщённые типы и методы, итераторы, анонимные функции с поддержкой замыканий, LINQ, исключения, комментарии в формате XML.
C# — объектно-ориентированный язык программирования. Разработан в 1998—2001 годах группой инженеров под руководством Андерса Хейлсберга в компании Microsoft как основной язык разработки приложений
для платформы Microsoft .NET Framework и впоследствии был стандартизирован
как ECMA-334 и ISO/IEC 23270. Компилятор C# входит в стандартную установку .NET
Framework.
C# относится к семье языков с C-подобным синтаксисом, из них его синтаксис
наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, атри
Переняв многое от своих предшественников —
языков C++, Java, Delphi, Модула и Smallta
Все свои программы я разрабатывал в интегрированной среде программирования Visual Studio. Она удобно подходит как для начинающих, так и для опытных программистов.
Visual Studio - интегрированная среда, упрощающая создание, отладку и развертывание приложений. Дайте волю фантазии и реализуйте свое видение с помощью мощных редакторов и новейших методов координирования совместной деятельности разработчиков и дизайнеров. Работайте в персонализированной среде, создавайте приложения для любых платформ, включая Microsoft SharePoint® и Windows Azure, используйте для написания кода уже имеющиеся навыки, ускоряя тем самым процесс разработки. Интегрированная поддержка разработки через тестирование и новые инструменты отладки позволяют быстро и без труда находить и устранять ошибки, обеспечивая высокое качество решений.
Конечным автоматом (КА) называется система S={ A, Q, V, f, g }, в которой:
A называется входным алфавитом, V-выходным, а Q - алфавитом состояний. Если, кроме того, в автомате S выделено одно состояние, называемое начальным (q1), то полученный автомат называется инициальным и обозначается (S, q).
Поскольку функции f и g определены на конечных множествах, их можно задавать таблицами перехода (1.1) и выхода (1.2).
Таблица 1.1
Q \ A |
a1 |
a2 |
Q \A |
a1 |
a2 | |
q1 |
q2 |
q1 |
q1 |
v2 |
v1 | |
q2 |
q2 |
q1 |
q2 |
v1 |
v2 |
Обычно две таблицы сводятся в одну таблицу, называемую автоматной таблицей (1.3).
Таблица 1.3
a1 |
a2 |
||
q1 |
q2,v2 |
q1,v1 | |
q2 |
q2,v1 |
q1,v2 |
Другой способ задания КА - ориентированный мультиграф, называемый графом переходов или диаграммой переходов (рисунок 1.1). Вершины графа соответствуют состояниям. Если f(qi, aj)=qk и g(qi, aj)=vt, то из qi в qk ведет ребро, на котором написаны aj и vt. Кратные ребра не обязательны. При этом должны быть выполнены условия корректности:
Пусть у автомата S={A, Q, V, f, g} алфавиты A, Q, V содержат соответственно по M, N, K символов. Выберем такие m, n, k, чтобы удовлетворялись
соотношения (основание логарифма-2)
logM<m<logM+1,
logN<n<logN+1,
logK<k<logK+1.
Образуем M различных m-мерных
двоичных наборов и установим взаимно-однозначное
соответствие между этими двоичными наборами
и символами из алфавита A. В результате
каждому ai будет сопоставлен свой двоичный набор ai=(ai1,ai2,...,aim), где
каждый разряд набора можно
рассматривать как логическую переменную,
принимающую значения
{0, 1}.Поступая аналогичным образом с алфавитами
Q и V, получаем
qj=(qj1, qj2,..., qjn),
vl=(vl1, vl2,..., vlk).
Данный процесс сопоставления символов из алфавитов A, Q, V и двоичных наборов называется кодированием алфавитов автомата.
Поскольку алфавиты рассмотренного примера (таблица 1.3) имеют по две буквы, то число разрядов каждого символа в двоичном алфавите будет 1. Обозначим первые буквы - 0, а вторые - 1. Таблица в этом случае примет следующий вид (1.4):
Таблица 1.4
Q \ A |
0 |
1 |
Q \A |
0 |
1 | |
0 |
1, 1 |
0, 0 |
0 |
1, 1 |
-, 0 | |
1 |
1, 0 |
0, 1 |
1 |
1, - |
0, 1 |
В зависимости от способа задания функции выхода g различают конечные автоматы следующего вида:
1/ vt = g(qjt-1, ait) - автоматы 1-го рода (автоматы Мили),
2/ vt = g(qjt, ait) - автоматы 2-го рода,
3/ vt = g(qjt-1, qjt) - правильные автоматы,
4/ vt = g(qjt-1) - правильные автоматы 1-го рода,
5/ vt = g(qjt) - правильные автоматы 2-го рода (автоматы Мура),
6/ vt = qjt-1 - абстрактные автоматы 1-го рода,
7/ vt = qjt - абстрактные автоматы 2-го рода (автоматы Медведева),
8/ vlt = g(ait) - автоматы без памяти.
Самой общей моделью являются автоматы Мили, поскольку остальные автоматы либо являются их частным случаем, либо тривиально сводятся к ним при подстановке функции f в функцию g.
Если функции f и g определены всюду на множествах совокупностей значений своих аргументов, то автомат S называется вполне определенным.
Для КА его функции f и g могут быть определены не только на множестве А всех входных букв, но и на множестве всех входных слов.
Для любого входного слова u=a1 a2...ak и начального состояния КА qt можно найти обобщенную функцию перехода F(qt,u), используя функцию перехода f
qt+1 =f(qt, a1),
qt+2 =f(qt+1, a2)= f(f(qt, a1), a2),
qt+3 =f(qt+2, a3)= f(f(f(qt, a1), a2), a3),
…………………………………….
qt+k =f(qt+k-1, ak)= f(f…(f(f(qt, a1), a2),...ak)= F(qt,u).
Это традиционное определение обобщенной функции перехода.
Возможна и другая индуктивная форма определения обобщенной функции перехода.
Для любого слова u из множества U и любой буквы aj
F(qt,uaj)=f(F(qt,u), aj).
Таким образом, обобщенная функция перехода F(qt,u) определяет конечное состояние КА, в которое он перейдет под воздействием входного слова u.
Аналогично определяется расширенная функция выхода G(qt,u)
v1 =g(qt, a1),
v2 =g(qt+1, a2)= g(f(qt, a1), a2),
v3 =g(qt+2, a3)= g(f(f(qt, a1), a2), a3),
…………………………………….
vk =g(qt+k-1, ak)= g(f…(f(f(qt, a1), a2),...ak)= G(qt,u).
Таким образом, обобщенная функция выхода G(qt,u) определяет конечный символ vk выходного слова КА w=v1 v2 vk.
Зафиксируем в автомате S начальное состояние qt и каждому входному слову u=a1 a2...ak поставим в соответствие слово w=v1 v2 vk в выходном алфавите.
Это соответствие, отображающее входные слова в выходные слова, называется автоматным отображением, а также автоматным (или ограниченно детерминированным) оператором, реализуемым автоматом (S, qt). Иногда говорят кратко - оператор (S, qt) или оператор S (если автомат S -инициальный). Если результатом применения оператора к слову u является выходное слово w, то это будем обозначать S(qt, u)=w или S(u)=w.
Автоматное отображение также удобно определить индуктивно:
S(qt, aj)=g(qt, aj),
S(qt, uaj)=S(qt, u)g(F(qt, u), aj).
Число букв в слове u называется длинной u и обозначается IuI или l(u).
Автоматные отображения обладают двумя свойствами:
Это свойство отражает тот факт, что автоматные операторы - это операторы без предвосхищения, т.е. операторы, которые "не заглядывают вперед", перерабатывая слово слева направо: i-я буква выходного слова зависит только от первых i букв входного слова. Введенные определения наглядно интерпретируются на графе переходов.
Если зафиксирована вершина qt, то всякое слово u=a1 a2...ak однозначно определяет путь длины k из этой вершины (обозначим его (qt, u)), на k ребрах которого написаны соответственно буквы a1 a2...ak . Поэтому F(qt, u) это последняя вершина пути (qt, u); G(qt, u)- выходная буква, написанная на последнем ребре пути, а отображение S(qt, u) - слово, образованное k выходными буквами, написанными на k ребрах этого пути.
Из диаграммы (рисунок 1.1) следует, что
f(q1, a2 a1)=f(q1, a1)=q2; f(q1, a1 a2 a2)=q1; g(q2, a1 a2)=v2 ;
g(q1, a1 a1 a2 a2)=v1; S(q2, a1 a2 a1)=v1 v2 v2.
Рассмотрим основные свойства конечных автоматов.
Состояние qi называется достижимым из состояния qj, если существует входное слово u, такое, что f(qj, u)=qi.
Из диаграммы на рисунке 1.1 следует, что состояние q2 является достижимым, так как f(q1, a1)=q2, т.е. автомат из состояния q1 под действием входного сигнала а1 переходит в состояние q2.
Автомат S называется сильно связанным, если из любого его состояния достижимо любое другое состояние. Автомат, изображенный на рисунке 1.1, является сильно связанным, так как он имеет два состояния и каждое из состояний достижимо из другого состояния.
Автомат называется автономным, если его входной алфавит состоит из одной буквы A={a}. Все входные слова КА имеют вид ааа...аааа. При этом достаточно длинное входное слово автономного автомата (АА) с n состояниями является периодическим (возможно с предпериодом), причем длины периода и предпериода не превосходят n. Поскольку число состояний КА (рисунок 1.1) равно двум, то и период выходной последовательности так же равен n=2.
Автомат S называется частичным, или не полностью определенным, если хотя бы одна из его двух функций не полностью определена, т.е. для некоторых пар (состояние - вход) значения функций f и g не определены.
В автоматной таблице неполная определенность КА выражается в том, что некоторые ее клетки не заполнены - в них стоят прочерки.
Функции f и g неравноправны. Если f не определена на слове u, то она не определена и на всех его продолжениях. Для g это не обязательно, поскольку в этом случае в выходном слове будет прочерк, но работа КА не остановится.
Из таблицы 1.5 следует, что КА, находясь в состоянии q1, под действием сигнала а2=1 выдаст на выход сигнал v1=0 и не сможет перейти ни в одно из возможных состояний, т.е. автомат прекратит работу - "зависнет". В состоянии q2=1 не определена функция выхода v=g(q2, a1) при действии входного сигнала а1=0. Работа КА не прекратится, но выходной сигнал при этом будет отсутствовать.
Пусть S={ As, Qs, Vs, fs, gs } и T={ At, Qt, Vt, ft, gt } - два автомата. Тройка отображений: h1:As®At; h2:Qs®Qt; h3:Vs®Vt, устанавливающая однозначное соответствие между алфавитами автоматов S и T определяет гомоморфизм автоматов, если выполняются условия