Моделювання роботи кінцевого розпізнавача для послідовно-сті елементів типу дата в німецькому

Санкт-Петербурзький державний університет водного КОМУНІКАЦІЙ

Кафедра ВСіІ

Курсова робота

з дисципліни «Системне програмне забезпечення»

Моделювання роботи кінцевого розпізнавача для послідовності елементів типу «дата» в німецькому форматі, розділених комами і ув'язнених у фігурні дужки

Варіант № 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 ₀ 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 Побудова кінцевого автомата

Між кінцевими автоматами і автоматними граматиками існує тісний зв'язок: клас мов, що допускаються кінцевими автоматами, збігається з класом мов, породжуваних граматиками автоматними.

Для побудови кінцевого автомата складену граматику шляхом введення додаткових станів треба перетворити до автоматної увазі, в результаті вийде наступна таблиця переходів:

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 Приклади

Правильні рядки:

Неправильні рядки: