Скінченні автомати та регулярні вирази
Регулярні множини та регулярні вирази
Нехай Х – скінченний алфавіт. Регулярна множина у алфавіті Х визначається рекурсивно таким чином:
Æ – регулярна множина у алфавіті Х,
{e} – регулярна множина у алфавіті Х,
якщо аÎХ, то {а} – регулярна множина у алфавіті Х,
якщо P, Q – регулярні множини у алфавіті Х, то PÈQ – регулярна множина у алфавіті Х,
якщо P, Q – регулярні множини у алфавіті Х, то PQ – регулярна множина у алфавіті Х,
якщо P – регулярна множина у алфавіті Х, то Р* – регулярна множина у алфавіті Х,
інших регулярних множин немає.
Регулярний вираз у алфавіті Х визначається рекурсивно таким чином:
Æ – регулярний вираз, що означає регулярну множину Æ,
e – регулярний вираз, що означає регулярну множину {e},
якщо аÎХ, то а – регулярний вираз, що означає регулярну множину {а},
якщо p та q – регулярні вирази, що означають регулярні множини P та Q відповідно, то
а) (p+q) – регулярний вираз, що означає множину PÈQ;
б) (pq) – регулярний вираз, що означає множину PQ;
в) (p)* – регулярний вираз, що означає множину P*;
інших регулярних виразів немає.
Праволінійні граматики та регулярні вирази
Граматика G=(N,T,s,P) називається праволінійною, якщо кожне правило з множини P має вигляд A®xB або A®x, де А,ВÎN, xÎF(T).
Праволінійна граматика будується за регулярним виразом у алфавіті Х згідно з такими правилами:
1) за регулярним виразом Æ будується праволінійна граматика ({s},X,s,Æ),
2) за регулярним виразом e будується праволінійна граматика ({s},X,s,{s®e}),
3) за регулярним виразом а (аÎХ) будується праволінійна граматика ({s},X,s,{s®a}),
4) якщо G1=(N1,X,s1,P1) та G2=(N2,X,s2,P2) – праволінійні граматики, побудовані за регулярними виразами p та q відповідно (N1ÇN2=Æ), то:
а) за регулярним виразом p+q будується праволінійна граматика (N1ÈN2È{s}, X, s, P1ÈP2È{s®s1,s®s2}), де s Ï N1ÈN2,
б) за регулярним виразом pq будується праволінійна граматика (N1ÈN2, X, s1, P), де Р визначається таким чином:
якщо A®xB належить P1, то A®xB належить P,
якщо A®x належить P1, то A®xs2 належить P,
усі правила з P2 належать P,
в) за регулярним виразом p* будується праволінійна граматика (N1È{s}, X, s, P), де sÏN1, а P визначається таким чином:
якщо A®xB належить P1, то A®xB належить P,
якщо A®x належить P1, то A®xs та A®x належать P,
s®s1 та s®e належать P.
Приклад побудови праволінійної граматики за регулярним виразом
Побудуємо праволінійну граматику за регулярним виразом 00+1* у алфавіті Х={0,1}. Виділимо підвирази даного виразу й за кожним з них побудуємо праволінійну граматику.
Виділяємо підвирази: 0, 00, 1, 1*, 00+1*.
За регулярним виразом 0 побудуємо праволінійну граматику
G1=({s1},X,s1,{s1®0}) (правило 3).
Для побудови праволінійної граматики за регулярним виразом 00 використаємо праволінійні граматики G1=({s1},X,s1,{s1®0}) та G2=({s2},X,s2,{s2®0}) й побудуємо праволінійну граматику
G3=({s1, s2}, X, s1, {s1®0s2, s2®0}) (правило 4б).
За регулярним виразом 1 побудуємо праволінійну граматику
G4=({s3}, X, s3, {s3®1}) (правило 3).
Для побудови праволінійної граматики за регулярним виразом 1* використаємо праволінійну граматику G4 й побудуємо праволінійну граматику
G5=({s3,s4}, X, s4, {s4®e, s4®s3, s3®1, s3®1s4}) (правило 4в).
Для побудови праволінійної граматики за регулярним виразом 00+1* використаємо граматики G3 та G5 й побудуємо праволінійну граматику
G6=({s1,s2,s3,s4,s5}, X, s5, P)), (правило 4а)
де Р={s5®s1, s5®s4, s1®0s2, s2®0, s4®e, s4®s3, s3®1, s3®1s4}.
Праволінійна граматика за регулярним виразом 00+1* побудована.
Скінченні автомати та регулярні вирази
Скінченний налаштований ініціальний автомат без виходів (розпізнавач) будується за регулярним виразом у алфавіті Х згідно з такими правилами:
1) за регулярним виразом Æ будується розпізнавач з порожньою множиною заключних станів,
2) за регулярним виразом e будується розпізнавач ({a0}, X, f, a0, {a0}), де f(a0,х) не визначено для жодного символу х з алфавіту Х (тобто f =Æ),
3) за регулярним виразом х (хÎХ) будується розпізнавач ({a0,a1}, X, f, a0, {a1}), де f(a0,x)={a1}, а у інших випадках функція f не визначена,
4) якщо М1=(A1, X, f1, a0, F1) та М2=(A2, X, f2, b0, F2) – розпізнавачі, побудовані за регулярними виразами p та q відповідно (А1ÇА2=Æ), то:
а) за регулярним виразом p+q будується розпізнавач (A1ÈA2È{c0}, X, f, c0, F), де c0ÏA1ÈA2, F=F1ÈF2, якщо ані М1, ані М2 не допускають e, й F=F1ÈF2È{c0}, якщо М1 або М2 допускає e, а функція f визначається таким чином:
f(c0,x)=f(a0,x)Èf(b0,x) для усіх x з алфавіту X,
f(a,x)=f1(a,x) для усіх а з А1 та усіх х з алфавіту X,
f(a,x)=f2(a,x) для усіх а з А2 та усіх х з алфавіту X;
б) за регулярним виразом pq будується розпізнавач (A1ÈA2, X, f, a0, F), де F=F2, якщо b0ÏF2, й F=F1ÈF2, якщо b0ÎF2, а функція f визначається таким чином:
f(a,x)=f1(a,x) для усіх а з А1\F1 та усіх х з алфавіту X,
f(a,x)=f1(a,x)Èf2(b0,x) для усіх а з F1 та усіх х з алфавіту X,
f(a,x)=f2(a,x) для усіх а з А2 та усіх х з алфавіту X;
в) за регулярним виразом p* будується розпізнавач (A1È{c0}, X, f, c0, F1È{c0}), де c0ÏA1, а функція f визначається таким чином:
f(a,x)=f1(a,x) для усіх а з А1\F1 та усіх х з алфавіту X,
f(a,x)=f1(a,x)Èf1(a0,x) для усіх а з F1 та усіх х з алфавіту X,
f(c0,x)=f1(a0,x) для усіх х з алфавіту X.