Определить свойства ка. Изучить алгоритм преобразования ндка в дка.
3.1 Сгенерировать цепочку символов по заданному языку
L = {00ω1 + (1)*ω1 {0,1}*}
3.2 По заданному языку построить НДКА. Представить в виде диаграмм. Проектируем недетерминированный конечный автомат для грамматики L.
KA = {Q, ∑, δ, q0, F}
Q = { A, B, C } – состояния автомата. Q = V
∑ = {1, 0, +} – алфавит. ∑ = T
δ – правила перехода. δ = P
q0 – начальное состояние. q0 = S0
F – множество заключительных состояний. F = qf
Правила перехода.
δ(S0, 0) = {A}
δ(A, 0) = {B}
δ(B, 1) = {B}
δ(B, 0) = {B}
δ(B, +) = {C}
δ(C, 1 ) = {C, qf}
2.1 Таблица переходов и диаграмма переходов.
Таблица переходов.
|
0 |
+ |
1 |
S0 |
A |
- |
- |
A |
B |
- |
- |
B |
B |
C |
B |
C |
- |
- |
C,qf |
Диаграмма переходов.
S0
A
0
0
0 1
qf
C
B
0 + 1
0,1
НДКА с ε-переходами.
δ(S0, 0) = {1}
δ(1, 0) = {2}
δ(2, ε ) = {3}
δ(3, ε) = {4}
δ(3, ε) = {6}
δ(4, 1 ) = {5}
δ(6, 0) = {7}
δ(5, ε) = {8}
δ(7, ε ) = {8}
δ(8, ε) = {9}
δ(9, +) = {10}
δ(10, ε ) = {11}
δ(11, 1 ) = {12}
δ(12, 1) = {11}
δ(11, ε) = {qf}
δ(12, ε ) = {qf}
Диаграмма переходов.
ε
ε
5
4
ε ε
0
3
2
1
9
8
7
6
12
10
11
qf
ε 1 ε
1
3.3 Реализовать преобразование НДКА в ДКА.
Шаг 1.
ε-closure(0) = {0} = A
ε-closure(move(A, 1)) = Ø
Dtran[A, 1] = Ø
ε-closure(move(A, +)) = Ø
Dtran[A, +] = Ø
ε-closure(move(A, 0)) = ε-closure({1}) = {1} = B
Dtran[A, 0] = B
ε-closure(move(B, 1)) = Ø
Dtran[B, 1] = Ø
ε-closure(move(B, 0)) = ε-closure({2}) = {2, 3, 4, 6, 9} = C
Dtran[B, 0] = C
ε-closure(move(B, +)) = Ø
Dtran[B, +] = Ø
ε-closure(move(C, 1)) = ε-closure({5}) = {3, 4, 5, 6, 8, 9} = D
Dtran[C, 1] = D
ε-closure(move(C, 0)) = ε-closure({7}) = {3, 4, 6, 7, 8, 9} = E
Dtran[C, 0] = E
ε-closure(move(C, +)) = ε-closure({10}) = {11} = F
Dtran[C, +] = F
ε-closure(move(D, 1)) = Ø
Dtran[D, 1] = Ø
ε-closure(move(D, 0)) = ε-closure({7}) = {3, 4, 6, 7, 8, 9} = E
Dtran[D, 0] = E
ε-closure(move(D, +)) = ε-closure({10}) = {11} = F
Dtran[D, +] = F
ε-closure(move(E, 0)) = Ø
Dtran[E, 0] = Ø
ε-closure(move(E, 1)) = ε-closure({5}) = {3, 4, 5, 6, 8, 9} = D
Dtran[E, 1] = D
ε-closure(move(E, +)) = ε-closure({10}) = {11} = F
Dtran[E, +] = F
ε-closure(move(F, 0)) = Ø
Dtran[F, 0] = Ø
ε-closure(move(F, 1)) = ε-closure({11, 12}) = {qf} = K
Dtran[F, 1] = K
ε-closure(move(F, +)) = Ø
Dtran[F, +] = Ø
Шаг 2. Построение таблицы переходов Dtran.
Состояние |
Входной символ |
||
1 |
0 |
+ |
|
A |
- |
B |
- |
B |
- |
C |
- |
C |
D |
E |
F |
D |
- |
E |
F |
E |
D |
- |
F |
F |
K |
- |
- |
Диаграмма переходов ДКА.
Текст программы.
Класс ДКА.
public class DKAutomate
{
ArrayList Q = null; // множество вcех состояний
ArrayList Sigma = null; // конечный алфавит входных символов
ArrayList DeltaList = new ArrayList(); // множество вcех правил перехода
string Q0 = null; // начальное состояние
ArrayList F = null; // множество заключительных состояний
public ArrayList q { get { return Q; } set { Q = value; } }
public ArrayList sigma { get { return Sigma; } set { Sigma = value; } }
public ArrayList deltaList { get { return DeltaList; } set { DeltaList = value; } }
public string q0 { get { return Q0; } set { Q0 = value; } }
public ArrayList f { get { return F; } set { F = value; } }
public DKAutomate()
{
this.Q = new ArrayList();
this.Sigma = new ArrayList();
this.DeltaList = new ArrayList();
this.F = new ArrayList();
// this.Init();
}
//Определение правил перехода:
public struct Delta
{ // структура Delta для правил перехода
private string LeftNoTerm; //текущее состояние
private string LeftTerm; //символ, по которому осуществляется переход
private string Right; //новое состояние
public string leftNoTerm { get { return LeftNoTerm; } set { LeftNoTerm = value; } }
public string leftTerm { get { return LeftTerm; } set { LeftTerm = value; } }
public string right { get { return Right; } set { Right = value; } }
public Delta(string LeftNoTerm, string LeftTerm, string Right)
{
this.LeftNoTerm = LeftNoTerm;
this.LeftTerm = LeftTerm;
this.Right = Right;
}
}// end class Delta
private string DebugArrayList(ArrayList arraylist)
{
string arraylist_str = " ( ";
for (int i = 0; i < arraylist.Count; i++)
{
if (i == 0)
arraylist_str = arraylist_str + arraylist[i].ToString();
else
arraylist_str = arraylist_str + "," + arraylist[i].ToString();
}
arraylist_str = arraylist_str + " ) ";
return arraylist_str;
}
public string DebugDeltaList ()
{
string DebugDeltaList_str = "";
foreach (Delta dlt in this.DeltaList)
{
DebugDeltaList_str = DebugDeltaList_str + ("\n " + dlt.leftNoTerm + " , " + dlt.leftTerm + " -> " + dlt.right);
}
return DebugDeltaList_str;
}
public override string ToString()
{
string Info_str = " \n Сформирован ДКА : " +
" \n Алфавит : " + DebugArrayList(this.Sigma) +
" \n Множество состояний : " + DebugArrayList(this.Q) +
" \n Множество заключительных состояний : " + DebugArrayList(this.F) +
" \n Начальное состояние : " + Q0 +
" \n Функция переходов ДКА : \n" + DebugDeltaList();
return Info_str;
}
public void Init ()
{
Q.Add("S0'");
Q.Add("A'");
Q.Add("B'");
Sigma.Add("0");
Sigma.Add("1");
q0 = "S0'";
F.Add("B'");
Delta delta;
delta = new Delta("S0'", "0", "A'");
DeltaList.Add(delta);
delta = new Delta("S0'", "1", "B'");
DeltaList.Add(delta);
delta = new Delta("A'", "0", "A'");
DeltaList.Add(delta);
delta = new Delta("A'", "1", "B'");
DeltaList.Add(delta);
delta = new Delta("B'", "0", "A'");
DeltaList.Add(delta);
delta = new Delta("B'", "1", "B'");
DeltaList.Add(delta);
} // end Init
//Проверка цепочки на допустимость
public int Dop_String()
{
string chain;
bool t = false;//используется для проверки:
//нашли ли мы подходящее правило, для перехода в следующее состояние
Console.Write("\n Введите входную цепочку: \n\n");
chain = Console.ReadLine(); //ввод проверяемой цепочки
int i = 0;
string state = this.q0;
for (i = 0; i < chain.Length; i++) //проход по всем символам цепочки
{
t = false;
foreach (Delta d in this.DeltaList)//проход по всем правилам перехода
{
if (d.leftNoTerm == state && d.leftTerm == chain.Substring(i, 1))//если подходящее правило найдено,
//то переход в следующее состояние
{
state = d.right;
t = true;
break;
}
}
if (t != true) //если после просмотра всех правил мы не нашли нужное, то сообщение об ошибке
{
Console.Write("\n Не найдено правило перехода ");
return 1;
}
}
//если мы дошли до конца цепочки, проверяем
foreach (string finish in this.F) //состояние должно быть одним из заключительных
{
if (finish == state)
{
Console.Write("\n Цепочка допускается ДКА ");
return 0;
}
}
Console.Write("\n Цепочка не допускается ДКА "); //иначе, цепочка не допускается
return 1;
}
}
Класс НДКА.
class NKAutomate
{
// NDKA (Q,Sigma,deltaList,q0,F)
ArrayList Q = null; // множество вcех состояний
ArrayList Sigma = null; // конечный алфавит входных символов
ArrayList DeltaList = null; // множество вcех правил
string Q0 = null; // начальное состояние
ArrayList F = null; // заключительные состояния
// свойства
public ArrayList q { get { return Q; } set { Q = value; } }
public ArrayList sigma { get { return Sigma; } set { Sigma = value; } }
public ArrayList deltaList
{
get { return DeltaList; }
set { DeltaList = value; }
}
public string q0 { get { return Q0; } set { Q0 = value; } }
public ArrayList f { get { return F; } set { F = value; } }
public NKAutomate()
{
this.Q = new ArrayList();
this.Sigma = new ArrayList();
this.DeltaList = new ArrayList();
this.F = new ArrayList();
this.Init();
}
public NKAutomate(string aname)
{
System.Console.WriteLine(aname);
// сделать диалог, инициализирующий NDKA
// альтернативные состояния переходов хранить в массиве см. Test
//init();
Init();
}
class Delta
{ // структура Delta для правила перехода НКА
private string LeftNoTerm; // состояние
private string LeftTerm; // входной символ
private ArrayList Right; // подмножество состояний
public string leftNoTerm { get { return LeftNoTerm; } set { LeftNoTerm = value; } }
public string leftTerm { get { return LeftTerm; } set { LeftTerm = value; } }
public ArrayList right { get { return Right; } set { Right = value; } }
// delta( A, 1) = {qf}
// LeftNoTerm LeftTerm Right
public Delta(string LeftNoTerm, string LeftTerm, ArrayList Right)
{
this.LeftNoTerm = LeftNoTerm;
this.LeftTerm = LeftTerm;
this.Right = Right;
}
public string DebugDeltaRight()
{
string deltaright_str = " ( ";
for (int i = 0; i < this.right.Count; i++)
{
if (i == 0)
deltaright_str = deltaright_str + this.right[i].ToString();
else
deltaright_str = deltaright_str + "," + this.right[i].ToString();
}
deltaright_str = deltaright_str + ") ";
return deltaright_str;
}
} // end class Delta
public void AddRule(string LeftNoTerm, string LeftTerm, ArrayList Right)
{
this.DeltaList.Add(new Delta(LeftNoTerm, LeftTerm, Right));
}
public void Init()
{ // задание правил для тестирования (конструктор)
Q = new ArrayList() { "S0", "A", "B", "C", "D", "E", "F" }; // "C" для отладки
Sigma = new ArrayList() { "0", "1", "-", "+" };
q0 = "S0";
F = new ArrayList() { "F" };
}
private string DebugArrayList(ArrayList arraylist)
{
string arraylist_str = " ( ";
for (int i = 0; i < arraylist.Count; i++)
{
if (i == 0)
arraylist_str = arraylist_str + arraylist[i].ToString();
else
arraylist_str = arraylist_str + "," + arraylist[i].ToString();
}
arraylist_str = arraylist_str + " ) ";
return arraylist_str;
}
public string DebugDeltaList()
{
string DebugDeltaList_str = "";
foreach (Delta dlt in this.DeltaList)
{
DebugDeltaList_str = DebugDeltaList_str + ("\n " + dlt.leftNoTerm + " , " + dlt.leftTerm + " -> " + dlt.DebugDeltaRight());
}
return DebugDeltaList_str;
}
public override string ToString()
{
string Info_str = " \n Сформирован НКА : " +
" \n Алфавит : " + DebugArrayList(this.Sigma) +
" \n Множество состояний : " + DebugArrayList(this.Q) +
" \n Множество заключительных состояний : " + DebugArrayList(this.F) +
" \n Начальное состояние : " + Q0 +
" \n Функция переходов НКА : \n" + DebugDeltaList();
return Info_str;
}
}
Функция преобразования НДКА в ДКА.
class Dstate
{ // структура Dstate
private string Name; // новое имя состояния ДКА
private ArrayList State; // подмножество состояний НКА
public string name { get { return Name; } set { Name = value; } }
public ArrayList state { get { return State; } set { State = value; } }
public Dstate(string Name, ArrayList State)
{
this.Name = Name;
this.State = State;
}
public string DebugDstateState()
{
string newdstate_str = " ( ";
for (int i = 0; i < this.State.Count; i++)
{
if (i == 0)
newdstate_str = newdstate_str + this.State[i].ToString();
else
newdstate_str = newdstate_str + "," + this.State[i].ToString();
}
newdstate_str = newdstate_str + " ) ";
return newdstate_str;
}
public static bool operator !=(Dstate op1, Dstate op2)
{
if (op1.State.Count != op2.State.Count)
return true;
else
{
bool fl = true;
for (int i = 0; i < op1.State.Count; i++)
{
if ((string)op1.State[i] == (string)op2.State[i])
fl = false;
break;
}
if (fl == true)
return true;
else
return false;
}
}
public static bool operator ==(Dstate op1, Dstate op2)
{
if (op1.State.Count == op2.State.Count)
{
bool fl = true;
for (int i = 0; i < op1.State.Count; i++)
{
if ((string)op1.State[i] != (string)op2.State[i])
fl = false;
break;
}
if (fl == true)
return true;
else
return false;
}
else
return false;
}
} // end class Dstate
public DKAutomate Determ() // детерминизация HKA
{
ArrayList Dstates = new ArrayList(); // состояния ДКА
Dstate dstate1 = new Dstate("", new ArrayList()); //{ q0 }); непомеченное начальное состояние ДКА
dstate1.state.Add(q0);
dstate1.state.Sort();
Dstates.Add(dstate1);
Dstates.Sort();
DKAutomate dkaautomate_new = new DKAutomate();
dkaautomate_new.sigma.AddRange(Sigma); // сформирован входной алфавит ДКА
int kns = 1;
int nom = 0;
Console.WriteLine(" \n Преобразование НКА в ДКА \n ");
Console.WriteLine(" kns = " + kns + " Dstates.Count = " + Dstates.Count);
for (int i = 0; i < Dstates.Count; i++) // состояния ДКА
{
// считывание очередного состояния
Dstate dstate = (Dstate)Dstates[i];
// Если оно непомеченное
if (dstate.name == "")
{
// пометили непомеченное состояние
dstate.name = nom.ToString();
nom++;
Dstates[i] = dstate;
// уменьшение количества непомеченных состояний
kns--;
// формирование новых состояний и новых правил перехода для помеченного состояния и всех символов входного алфавита
for (int j = 0; j < Sigma.Count; j++) // проход по всем символам алфавита
{
// формирование нового состояния и нового правила перехода для очередного символа
string symbol = (string)Sigma[j];
// создание нового непомеченного состояния
Dstate newdstate = new Dstate("", new ArrayList());
// ищем возможные переходы для помеченного состояния
for (int k = 0; k < dstate.state.Count; k++)
{
// для каждого состояния, вxодящего в помеченное ищем возможные переходы
string statecur1 = (string)dstate.state[k]; //? без буфера
foreach (Delta delta in this.DeltaList)//проход по всем правилам перехода НКА
{
if (delta.leftNoTerm == statecur1 && delta.leftTerm == symbol) //statecur symbol //то переход в следующее состояние
{
// если переходы найдены, добавляем их в новое состояние
for (int n = 0; n < delta.right.Count; n++)
{
string statecur2 = (string)delta.right[n];
if (newdstate.state.BinarySearch(statecur2) < 0)
{
newdstate.state.Add(statecur2);
newdstate.state.Sort();
}
}
}
}
}
if (newdstate.state.Count != 0)
{
//сортируем newdstate
newdstate.state.Sort(); //
// вывод на экран
Console.WriteLine(" \n Сформировано правило: " + dstate.name + " , " + symbol + " -> " + newdstate.DebugDstateState());
// формирование таблицы переходов ДКА
DKAutomate.Delta DKAdelta = new DKAutomate.Delta(dstate.name, symbol, newdstate.DebugDstateState());
dkaautomate_new.deltaList.Add(DKAdelta);
// Если нового состояния нет в Dstates, то добавляем
bool fl = false;
foreach (Dstate dst in Dstates)
{
if (dst == newdstate)
{
fl = true;
break;
}
}
if (fl != true)
{
Dstates.Add(newdstate);// добавляем непомеченное новое состояние
kns++;
}
} //end if
} // цикл по входному алфавиту
} // если состояние непомеченное
} // цикл по состояния ДКА
Console.WriteLine(" \n Состояния ДКА \n");
dkaautomate_new.q0 = "0"; // сформировано начальное состояние ДКА
foreach (Dstate dst in Dstates)
{
dkaautomate_new.q.Add(dst.name); // формирование множества состояний ДКА
Console.WriteLine(" состояние " + dst.name + " : " + dst.DebugDstateState());
bool fl = false;
for (int i = 0; i < dst.state.Count; i++)
{
foreach (string f in F)
{
if ((string)dst.state[i] == f)
{
fl = true;
break;
}
}
if (fl == true) break;
}
if (fl == true) dkaautomate_new.f.Add(dst.name); // формирование множества заключительных состояний ДКА
}
Console.WriteLine(" \n Функция переходов ДКА : \n");
// переобозначаем правые части таблицы переходов ДКА
for (int i = 0; i < dkaautomate_new.deltaList.Count; i++)
{
DKAutomate.Delta dltbuf = (DKAutomate.Delta)dkaautomate_new.deltaList[i];
foreach (Dstate dst in Dstates)
{
Dstate dstbuf = dst;
if (dltbuf.right == dstbuf.DebugDstateState())
{
dltbuf.right = dstbuf.name; // !!!
Console.WriteLine(dltbuf.leftNoTerm + " , " + dltbuf.leftTerm + " -> " + dltbuf.right);
break;
}
}
dkaautomate_new.deltaList[i] = dltbuf; // сформирована функция переходов ДКА
}
Console.ReadLine();
return dkaautomate_new;
} // end determ ()