Міністерство освіти та науки України
Національний університет «Львівська політехніка»
кафедра прикладної математики
ЛАБОРАТОРНА РОБОТА №1
з системного програмування на тему:
«Скінченні автомати»
Мета: побудувати скінченний детермінований автомат за заданим варіантом, продумати організацію програми скінченного автомата. Написати програму яка отримуэ на вході – символьний ланцюжок (у вхідному файлі або з клавіатури), на виході – відповідь, чи даний ланцюжок розпізнається як правильний (у вихідному файлі або екрані).
Варіант №10.
Завдання:
Побудувати скінчений автомат для розпізнавання послідовності імен простих та індексованих змінних , що відокремлюються одне від одного комами. Ім'я простої змінної складається з довільної кількості букв, індексованої змінної − з довільної кількості букв, дужки [ , цілого числа без знаку , дужки ] .
Автомат:
a..z
0
1..9
,
[
]
з. с.
S
A
F
F
F
F
F
-
A
A
F
F
S
B
F
+
B
F
F
C
F
F
F
-
C
F
C
C
F
F
D
-
D
F
F
F
S
F
F
+
F
F
F
F
F
F
F
-
Код програми:
#include <iostream.h>
#include <string.h>
int M[6][6] = {{1, 5, 5, 5, 5, 5},
{1, 5, 5, 0, 2, 5},
{5, 5, 3, 5, 5, 5},
{5, 3, 3, 5, 5, 4},
{5, 5, 5, 0, 5, 5},
{5, 5, 5, 5, 5, 5}};
void main()
{
int state = 0;
int y;
char S[255], c;
cout<<"Vevdit' stri4ky sumvoliv - poslidovnosti leksem ta indeksovanuh leksem,"
<<"jaki rozdileni komamu."<<endl;
cin>>S;
for(unsigned int i = 0; i < strlen(S); i++)
{
c = S[i];
if ((c >= 'a') && (c <= 'z')) y = 0;
else
if (c == '0') y = 1;
else
if ((c >= '1') && (c <= '9')) y = 2;
else
if (c == '[') y = 4;
else
if (c == ']') y = 5;
else
if (c == ',') y = 3;
else
state = 5;
state = M[state][y];
}
cout<<state<<endl;
if (state == 5) cout<<"False";
if (state == 1 || state == 4) cout<<"True";
}
Контрольний приклад:
Vevdit' stri4ky sumvoliv - poslidovnosti leksem ta indeksovanuh leksem,jaki rozd
ileni komamu.
sdfw[234],sdfwe[433],c[23032]
True
Висновок:
На цій лабораторній я ознайомився з поняттям скінченного автомату, та зрозумів як за допомогою цієї простої структури можна аналізувати ланцюжки символів на предмет належності граматиці що описує даний автомат. Я написав програму, що аналізує вхідну стрічку та відповідно виводить True – якщо ця стрічка належить граматиці, і – False – якщо ні.
