Минимизация автомата

  • 06 сент. 2011 г.
  • 1335 Слова
1. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ

Исходными данными для курсового проекта являются две таблицы — табл. 1 и табл. 2 и правила вывода R.
Табл. 1 состоит из трех строк, первая из которых содержит перечисление 18 символов Ci.
Во вторую строку Si записываются первые 18 символов фамилии, имени и отчества студента с обязательными пробелами между фамилией и именем, именем и отчеством.В третью строку для каждой из 18 букв строки Si заносится символ из алфавита { x0, x1, x2, x3, x4, x5, x6, x7 } в соответствии с табл. 1.

|Ci |c1 |c2 |
|S(x7S3; |S3(x7S4; |S4(x4B; |
|S(x2C; |S(x5F;|A(x3D; |
|A(x0; |B(x3E; |B(x0; |
|C(x3E; |C(x0; |D(x6S; |
|D(x7; |E(x6S; |E(x7; |
|F(x5F1; |F1(x6F2;|F2(x3F3; |
|F3(x3; |F(x5F4; |F4(x6F5; |
|F5(x3F6; |F6(x3; |F(x0F7. |
|F7(x3F8; |F8(x3 ; | |

Следовательно, словарьнетерминальных символов V(N будет иметь вид
V"N = {S, S1 , S2, S3, S4, А, В, С, D, E, F, F1, F2, F3, F4, F5, F6, F7, F8,}.
В рассматриваемом примере нетерминальный словарь имеет 19 символов и его мощность (V"N (равна 19, мощность (V(T ( терминального словаря V(T равна 8.
3. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО
КОНЕЧНОГО АВТОМАТА

Недетерминированный конечный автомат — это пятерка
A=(Q, V, М, S, Z),где
Q - множество (алфавит) внутренних состояний;
V - входной алфавит;
М — функция переходов, представляющая отображение
V*Q (P(Q);
P(Q) — множество подмножеств из Q;
S (Q — множество начальных состояний;
Z ( Q — множество заключительных состояний;
S(Z.

Недетерминированный конечный автомат (в отличие от детерминированного) можетиметь несколько начальных состояний. Отличается он и функциями перехода.
Как правило, недетерминированные конечные автоматы порождаются регулярными грамматиками, которые содержат правила вывода вида
U::= TW R::= TW, что соответствует фрагменту диаграммы

U

T
W
T
R
Частичная функция переходов этого случая имеетвид:
M(W,T)={U,R}.
В рассматриваемом примере недетерминированный конечный автомат имеет одно начальное состояние S. Зададим этот автомат следующим образом. Поставим в соответствие символам нетерминального словаря V"N состояния из Q , в том числе нетерминалу S — начальное состояние qo . Добавим заключительное состояние Z, в котором автомат оказывается, если цепочка символов, поступающих наавтомат, принадлежит L (G").
Составим табл. 3, в которой нетерминальным символам из множества V"N соответствуют состояния автомата из множества Q.

Таблица 3

|S |

q16 | | | |q19 | | | | | | q17 | | | |q18 | | | | | | q18 | | | |q19 | || | | | q19 | | | | | | | | | |

[pic]

Цепочки:
1. x7x7x4x3x7
2. x7x7x4x0
3. x7x7x4x0
4. x2x3x7
5. x2x0
6. x5 x4x6x3x3
7. x5x5x6x3x3
8. x5x0x3x3

Циклические:
1. x7x7x4x3x6
2. x2x3x6
3. x7x7x4x3x6

4. ПРЕОБРАЗОВАНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА В ДЕТЕРМИНИРОВАННЫЙ КОНЕЧНЫЙ АВТОМАТ

Детерминированный конечный автомат — это пятерка...
tracking img