Санкт-Петербурзький державний університет водного КОМУНІКАЦІЙ
Кафедра ВСіІ
Курсова робота
з дисципліни «Системне програмне забезпечення»
Моделювання роботи кінцевого розпізнавача для послідовності елементів типу «дата» в німецькому форматі, розділених комами і ув'язнених у фігурні дужки
Варіант № 15
Виконав:
студент групи ІВ-31
Мельников А.
Санкт-Петербург
2009
Зміст
Завдання на курсову роботу
Введення
1 Складання формальної граматики
2 Побудова кінцевого автомата
3 Програмне моделювання роботи кінцевого автомата
4 Граф детермінованого автомата
5 Блок-схема
6 Приклади розбору рядків
Завдання на курсову роботу
Моделювання роботи кінцевого розпізнавача для послідовності елементів типу «дата» в німецькому форматі (ДД.ММ.РРРР), розділених комами, при цьому значення дати повинно бути вміщено у фігурні дужки, а рік повинен відображатися чотирма символами, наприклад, ({01.12.2001 }, {05.07.2003});
Введення
Навчальна мета. Одержання практичних навичок побудови моделей кінцевих розпізнавачів.
Теоретичні відомості.
Недетермінірованние кінцевий автомат (НКА) - це п'ятірка M = (Q, T, D, q 0, F), де
Q - кінцеве безліч станів;
T - кінцеве безліч допустимих вхідних символів (вхідний алфавіт);
D - функція переходів (відображає безліч Q (T {E}) у безліч підмножин безлічі Q), що визначає поведінку керуючого пристрою;
q 0 Q - початковий стан керуючого пристрою;
F Q - безліч заключних станів.
Недетермінізму автомата полягає в тому, що, по-перше, перебуваючи в деякому стані і оглядаючи поточний символ, автомат може перейти в один з, взагалі кажучи, декількох можливих станів, і по-друге, автомат може робити переходи по e.
Нехай M = (Q, T, D, q 0, F) - НКА. Конфігурацією автомата M називається пара (q, w) Q T *, де q - поточний стан керуючого пристрою, а w - ланцюжок символів на вхідний стрічці, що складається з символу під головкою і всіх символів праворуч від нього. Конфігурація (q 0, w) називається початковою, а конфігурація (q, e), де q F - заключної (або допускає).
Нехай M = (Q, T, D, q 0, F) - НКА. Тактом автомата M називається бінарне відношення , Визначений на конфігураціях M наступним чином: якщо p D (q, a), де a T {E}, то (q, aw) (P, w) для всіх w T *.
Будемо позначати символом + ( *) Транзитивне (рефлексивно-транзитивне) замикання відносини .
Кажуть, що автомат M допускає ланцюжок w, якщо (q 0, w) * (Q, e) для деякого q F. Мовою, що допускається (розпізнаваним, визначеним) автоматом M, (позначається L (M)), називається безліч вхідних ланцюжків, що допускаються автоматом M. Тобто
Важливим окремим випадком недетермінірованного кінцевого автомата є детермінований кінцевий автомат, який на кожному такті роботи має можливість перейти не більше ніж в один стан і не може робити переходи по e.
Нехай M = (Q, T, D, q 0, F) - НКА. Будемо називати M детермінованим кінцевим автоматом (ДКА), якщо виконані такі дві умови:
D (q, e) = для будь-якого q Q, і
D (q, a) містить не більше одного елемента для будь-яких q Q і a T.
Так як функція переходів ДКА містить не більше одного елемента для будь-якої пари аргументів, для ДКА ми будемо користуватися записом D (q, a) = p замість D (q, a) = {p}.
Кінцевий автомат може бути зображений графічно у вигляді діаграми, що представляє собою орієнтований граф, в якому кожному станом відповідає вершина, а дуга, позначена символом a T {E}, з'єднує дві вершини p та q, якщо p D (q, a). На діаграмі виділяються початкова та заключні стану.
Кінцевий распознаватель - це модель пристрою з кінцевим числом станів, яке відрізняє правильно освічені, або «допустимі» ланцюжка, від «неприпустимих».
Прикладом завдання розпізнавання може служити перевірка непарності числа одиниць в довільній ланцюжку, що складається з нулів та одиниць. Відповідний кінцевий автомат буде допускати всі ланцюжки, що містять непарне число одиниць, і відкидати всі ланцюжки з парних їх числом. Назвемо його «контролером непарності».
На вхід кінцевого автомата подається ланцюжок символів з кінцевої множини, званого вхідним алфавітом автомата, і представляє собою сукупність символів, для роботи з якими він призначений. Як допущені, так і відкидаємо автоматом ланцюжка, складаються тільки з символів вхідного алфавіту. Символи, які не належать вхідного алфавітом, не можна подавати на вхід автомата. Вхідний алфавіт контролера непарності складається з двох символів: «0» і «1».
У кожний момент часу кінцевий автомат має справу лише з одним вхідним символом, а інформацію про попередні символах вхідний ланцюжка зберігає за допомогою кінцевого безлічі станів. Згідно з цим поданням, автомат пам'ятає про прочитаних раніше символах тільки те, що при їх обробці він перейшов у якийсь стан, яке і є пам'яттю автомата про минуле.
Роботу автомата можна описати математично за допомогою функції переходів, яка за поточним станом та поточного вхідного символу дає новий стан автомата . Символічно ця залежність описується так:
.
Деякі стану автомата вибираються як припускають, чи заключних. Якщо автомат, почавши роботу в початковому стані, при прочитанні всього ланцюжка переходить в одне з допускають станів, то говорять, що цей ланцюжок допускається автоматом. Якщо останній стан автомата не є допускає, то говорять, що автомат відкидає ланцюжок.
1 Складання формальної граматики
Фраза мови являє собою список, тому з початкового символу граматики повинен виводиться список:
R 0: <пропозицію >::==< фраза>
R 1: <фраза >::==< дата> | <дата>, <фраза>
Дата представляє собою лінійну структуру:
R 2: <дата >::=={< місяць>. <Рік>}
Аналогічно рік, місяць і день:
R 3: <рік >::==< цифра> <цифра> <цифра> <цифра>
R 4: <місяць>:: == <месяцб>. <Деньб> | <месяцм>. <Деньми> | <Лютий> <деньф>
R 5: <месяцб>:: = 01 | 03 | 05 | 07 | 08 | 10 | 12
R 6: <месяцм>:: = 04 | 06 | 09 | 11
R 7: <Лютий>:: = 02
R 8: <деньб >::==< ціфра2> <цифра> | 3 <ціфра1>
R 9: <деньми >::==< ціфра2> <цифра> | 30
R 10: <деньф >::==< ціфра1> <цифра> | 2 <ціфра3>
R 11: <цифра >::== 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
R 12: <ціфра1 >::== 0 | 1
R 13: <ціфра2 >::== 0 | 1 | 2
R 14: <ціфра3 >::== 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
Таким чином, необхідну граматику можна описати наступною структурою:
Безліч термінальних символів: {,},.,,, 0,1,2,3,4,5,6,7,8,9.
Безліч нетермінальних знаків: <фраза>, <дата>, <рік>, <місяць>, <день>, <цифра>, <ціфра1>, <ціфра2>.
Безліч правил виводу R 0, R 1, R 2, R 3, R 4, R 5, R 6, R 7, R 8, R 9, R 10, R 11, R 12, R 13, R 14.
2 Побудова кінцевого автомата
Між кінцевими автоматами і автоматними граматиками існує тісний зв'язок: клас мов, що допускаються кінцевими автоматами, збігається з класом мов, породжуваних граматиками автоматними.
Для побудови кінцевого автомата складену граматику шляхом введення додаткових станів треба перетворити до автоматної увазі, в результаті вийде наступна таблиця переходів:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | { | } | . | , | |
та | ||||||||||||||
немає | ||||||||||||||
день | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | денф | немає |
Денбей | ДБ1 | ДБ1 | ДБ1 | Цф1 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає |
ДБ1 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | немає | немає | немає | немає |
ДБ2 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | міс | немає |
Цф1 | ДБ2 | ДБ2 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає |
Денмен | ДБ1 | ДБ1 | ДБ1 | Цф0 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає |
Цф0 | ДБ2 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає |
денф | ДБ1 | ДБ1 | Цф3 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає |
Цф3 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | ДБ2 | немає | немає | немає | немає | немає | немає |
міс | Мес0 | Мес1 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає |
Мес0 | немає | Месбах | Лютий | Месбах | месм | Месбах | месм | Месбах | Месбах | месм | немає | немає | немає | немає |
Мес1 | Месбах | месм | Месбах | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає |
Месбах | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | Денбей | немає |
месм | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | Денмен | немає |
дата | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | рік | немає | немає | немає |
рік | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | немає | немає | немає | немає |
Цг1 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | немає | немає | немає | немає |
Цг2 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | немає | немає | немає | немає |
Цг3 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | немає | немає | немає | немає |
Цг4 | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | немає | та | немає | день |
3 Граф детермінованого автомата
Для того, щоб поліпшити зорове сприйняття і полегшити розуміння складних синтаксичних описів, часто застосовують уявлення правил граматики у вигляді синтаксичних діаграм.
Синтаксична діаграма являє собою орієнтований граф для кожного правила граматики.
4 Програмне моделювання роботи кінцевого автомата
# Include "iostream. H"
# Include "stdio.h"
# Include "conio.h"
int main ()
{Int i, j, kol, tsost, slsost, tsymb;
int tabl [24] [14] = {{0,0,0,0,0,0,0,0,0,0,0,0,0,0}, / / da
{1,1,1,1,1,1,1,1,1,1,1,1,1,1}, / / net
{1,1,1,1,1,1,1,1,1,1,3,1,1,1},
{4,4,4,5,1,1,1,1,1,1,1,1,1,1},
{1,6,6,6,6,6,6,6,6,6,1,1,1,1},
{8,9,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,20,1},
{16,16,16,16,16,16,16,16,16,16,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,10,1},
{1,1,1,1,1,1,1,1,1,1,1,1,11,1},
{12,13,1,1,1,1,1,1,1,1,1,1,1,1},
{14,15,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,23,1,23,1,1,23,1,1,1,1},
{23,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,23,1,23,1,23,1,23,23,1,1,1,1,1},
{23,1,23,1,1,1,1,1,1,1,1,1,1,1},
{17,17,17,17,17,17,17,17,17,17,1,1,1,1},
{18,18,18,18,18,18,18,18,18,18,1,1,1,1},
{19,19,19,19,19,19,19,19,19,19,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,0,1,2},
{21,22,1,1,1,1,1,1,1,1,1,1,1,1},
{1,23,23,23,23,23,23,23,23,23,1,1,1,1},
{23,23,23,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,7,1},
};
printf ("matrica \ n");
for (i = 0; i <24; i + +) {for (j = 0; j <14; j + +) printf ("% 4d", tabl [i] [j]); printf ("\ n");} ;
char ch, inpstr [80];
printf ("\ n ENTER STRING");
i = 0;
while ((ch = getch ())! = 13 & & i <80)
{Putch (ch);
inpstr [i + +] = ch;}
inpstr [i] = '\ 0';
kol = i-1;
printf ("\ n input string:");
printf (inpstr);
printf ("\ n");
tsost = 2;
for (i = 0; i <= kol; i = i +1)
{Tsymb = inpstr [i];
switch (tsymb)
{Case 0 ": slsost = tabl [tsost] [0]; break;
case '1 ': slsost = tabl [tsost] [1]; break;
case '2 ': slsost = tabl [tsost] [2]; break;
case '3 ': slsost = tabl [tsost] [3]; break;
case '4 ': slsost = tabl [tsost] [4]; break;
case '5 ': slsost = tabl [tsost] [5]; break;
case '6 ': slsost = tabl [tsost] [6]; break;
case '7 ': slsost = tabl [tsost] [7]; break;
case '8 ': slsost = tabl [tsost] [8]; break;
case '9 ': slsost = tabl [tsost] [9]; break;
case '{': slsost = tabl [tsost] [10]; break;
case '}': slsost = tabl [tsost] [11]; break;
case '.': slsost = tabl [tsost] [12]; break;
case ',': slsost = tabl [tsost] [13]; break;
default: slsost = 1;}
printf ("% 5d \ n", slsost);
tsost = slsost;
};
switch (slsost)
{Case 1: cout <<"\ n STRING is WRONG \ n"; break;
case 0: cout <<"\ n STRING is RIGHT \ n"; break;}
return 0;
};
5 Блок-схема
6 Приклади
Правильні рядки:
Неправильні рядки: