NFA to DFA to MFA Conversion Tool - Convert Regular Expressions to Finite Automata
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.IO; using System.Linq; using System.Reflection.Emit; using System.Security.Cryptography; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using System.Windows.Forms; using static System.Windows.Forms.VisualStyles.VisualStyleElement;
namespace byyljxfzxt { public partial class Form3 : Form { public Form3() { InitializeComponent(); }
string[] lines;
string startSymbol;
string endSymbol;
string[] symbolSet;
string[] endStates;
public bool rep(char x, string s)//判断是否重复
{
int i = 0;
if (s.Length == 0)
{
return true;
}
while (i < s.Length)
{
if (s[i] == x)
return false;
i++;
}
return true;
}
string s3 = "";
public int countap(string s)//统计字母个数
{
int i = 0;
while (i < s.Length)
{
if (s[i] <= 'z' && s[i] >= 'a')
{
if (rep(s[i], s3))
s3 = s3 + s[i];
}
i++;
}
return s3.Length;
}
private void listView1_SelectedIndexChanged(object sender, EventArgs e)
{
ListViewItem item = new ListViewItem();
item.Text = Convert.ToString(listView1.Items.Count + 1);
item.SubItems.Add("0");
item.SubItems.Add("1");
item.SubItems.Add("2");
listView1.Items.Add(item);
}
private void button1_Click(object sender, EventArgs e)
{
string s = richTextBox1.Text;
int i, count = 0;//count用来标记（和）
countap(s);
if (s == "")//如果输入为空白
{
MessageBox.Show("正确的输入");
return;
}
if (s[0] == '|' || s[0] == '*' || s[s.Length - 1] == '|' || s[s.Length - 1] == '(')//不能以|、*开头，也不能以|、（结尾
{
MessageBox.Show("错误的输入");
return;
}
for (i = 0; i < s.Length; i++)//做循环判断
{
if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z') || s[i] == '*' || s[i] == '|' || s[i] == '(' || s[i] == ')')
//当前为大写（小写）字母或者*、|、（、）
{
switch (s[i])
{
case '(':
if ((i + 1) < s.Length)
{
if (s[i + 1] == '*' || s[i + 1] == '|')//（）内开头也不可以是闭包
{
MessageBox.Show("错误的输入");
return;
}
if (s[i + 1] == ')')
{
MessageBox.Show("错误的输入");
return;
}
}
count++;
break;
case '|':
if ((i + 1) < s.Length)
{
if (s[i + 1] == '*' || s[i + 1] == '|' || s[i + 1] == ')')
{
MessageBox.Show("错误的输入");
return;
}
}
break;
case '*':
if ((i + 1) < s.Length)
{
if (s[i + 1] == '*')
{
MessageBox.Show("错误的输入");
return;
}
}
break;
case ')':
count--;
break;
}
}
else
{
MessageBox.Show("错误的输入");
return;
}
if (count < 0)//只要出现）数量大于（时，一定是错误情况
{
MessageBox.Show("错误的输入");
return;
}
}
if (count != 0)//最终循环结束时，count=0才是括号匹配
{
MessageBox.Show("错误的输入");
return;
}
//CreateNFA.Enabled = true;
button4.Enabled = true;
MessageBox.Show("正确的输入");
}
private void button2_Click(object sender, EventArgs e)
{
richTextBox1.Text = " ";
}
private void button3_Click(object sender, EventArgs e)//读入NFA文件显示在listView1容器中
{
OpenFileDialog openFileDialog1 = new OpenFileDialog();
openFileDialog1.Filter = "NFA Files|*.nfa";
openFileDialog1.Title = "Select an NFA File";
if (openFileDialog1.ShowDialog() == DialogResult.OK)
{
lines = File.ReadAllLines(openFileDialog1.FileName);
startSymbol = lines[0].Substring(lines[0].IndexOf(":") + 1).Trim();
endSymbol = lines[1].Substring(lines[1].IndexOf(":") + 1).Trim();
symbolSet = lines[2].Substring(lines[2].IndexOf(":") + 1).Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries);
for (int i = 3; i < lines.Length; i++)
{
string[] tokens = lines[i].Split(new char[] { '\t' }, StringSplitOptions.RemoveEmptyEntries);
string startState = tokens[0];
string inputSymbol = tokens[1];
string nextState = tokens[2];
ListViewItem item = new ListViewItem(startState);
item.SubItems.Add(inputSymbol);
item.SubItems.Add(nextState);
listView1.Items.Add(item);
}
}
label3.Text = "初始状态集:" + startSymbol;
label4.Text = "终止状态集:" + endSymbol;
button6.Enabled = false;
button7.Enabled = true;
}
private void button5_Click(object sender, EventArgs e)//保存NFA文件
{
SaveFileDialog saveFileDialog1 = new SaveFileDialog();
saveFileDialog1.Filter = "NFA Files|*.nfa";
saveFileDialog1.Title = "Save an NFA File";
if (saveFileDialog1.ShowDialog() == DialogResult.OK)
{
using (StreamWriter sw = new StreamWriter(saveFileDialog1.FileName))
{
sw.WriteLine("startSymbol: " + startSymbol);
sw.WriteLine("endSymbol: " + endSymbol);
sw.Write("symbolSet: ");
foreach (string symbol in symbolSet)
{
sw.Write(symbol + ";");
}
sw.WriteLine();
foreach (ListViewItem item in listView1.Items)
{
sw.WriteLine(item.SubItems[0].Text + "\t" + item.SubItems[1].Text + "\t" + item.SubItems[2].Text);
}
}
}
}
private void button6_Click(object sender, EventArgs e)//读入DFA文件显示在listView2容器中
{
OpenFileDialog openFileDialog1 = new OpenFileDialog();
openFileDialog1.Filter = "DFA文件|*.dfa";
openFileDialog1.Title = "选择DFA文件";
if (openFileDialog1.ShowDialog() == DialogResult.OK)
{
lines = File.ReadAllLines(openFileDialog1.FileName);
startSymbol = lines[0].Split(':').Last().Trim();
endStates = lines[1].Split(':').Last().Split(';').Select(x => x.Trim()).ToArray();
int maxState = int.Parse(lines[2].Split(':').Last().Trim());
string[] symbols = lines[3].Split(':').Last().Split(';').Select(x => x.Trim()).ToArray();
Dictionary<string, Dictionary<string, string>> transitions = new Dictionary<string, Dictionary<string, string>>();
for (int i = 4; i < lines.Length; i++)
{
string[] parts = lines[i].Split('\t');
string fromState = parts[0].Trim();
string symbol = parts[1].Trim();
string toState = parts[2].Trim();
if (!transitions.ContainsKey(fromState))
{
transitions[fromState] = new Dictionary<string, string>();
}
transitions[fromState][symbol] = toState;
}
listView2.Items.Clear();
foreach (string state in transitions.Keys)
{
foreach (string symbol in transitions[state].Keys)
{
string toState = transitions[state][symbol];
ListViewItem item = new ListViewItem(new[] { state, symbol, toState });
listView2.Items.Add(item);
}
}
}
label5.Text = "初始状态集:" + startSymbol;
label7.Text = "终止状态集:";
for (int i = 0; i < endStates.Length - 1 && !string.IsNullOrEmpty(endStates[i]); i++)
label7.Text = label7.Text + endStates[i] + ";";
button7.Enabled = false;
button9.Enabled = true;
}
private void button8_Click(object sender, EventArgs e)//保存DFA文件
{
SaveFileDialog saveFileDialog1 = new SaveFileDialog();
saveFileDialog1.Filter = "DFA Files|*.dfa";
saveFileDialog1.Title = "Save a DFA File";
if (saveFileDialog1.ShowDialog() == DialogResult.OK)
{
using (StreamWriter sw = new StreamWriter(saveFileDialog1.FileName))
{
sw.WriteLine("startSymbol: " + startSymbol);
sw.Write("endStates: ");
foreach (string endState in endStates)
{
sw.Write(endState + ";");
}
sw.WriteLine();
sw.WriteLine("maxState: " + listView2.Items.Count);
sw.Write("symbols: ");
foreach (string symbol in symbolSet)
{
sw.Write(symbol + ";");
}
sw.WriteLine();
foreach (ListViewItem item in listView2.Items)
{
sw.WriteLine(item.SubItems[0].Text + "\t" + item.SubItems[1].Text + "\t" + item.SubItems[2].Text);
}
}
}
}
private void button7_Click(object sender, EventArgs e)//生成DFA文件显示在listView2容器中
{
Dictionary<string, Dictionary<string, string>> nfaTransitions = new Dictionary<string, Dictionary<string, string>>();
foreach (ListViewItem item in listView1.Items)
{
string startState = item.SubItems[0].Text;
string inputSymbol = item.SubItems[1].Text;
string nextState = item.SubItems[2].Text;
if (!nfaTransitions.ContainsKey(startState))
{
nfaTransitions[startState] = new Dictionary<string, string>();
}
if (!nfaTransitions[startState].ContainsKey(inputSymbol))
{
nfaTransitions[startState][inputSymbol] = "";
}
nfaTransitions[startState][inputSymbol] += nextState + ";";
}
Dictionary<string, string> dfaStates = new Dictionary<string, string>();
List<string> dfaEndStates = new List<string>();
Queue<string> queue = new Queue<string>();
queue.Enqueue(startSymbol);
while (queue.Count > 0)
{
string currentState = queue.Dequeue();
if (!dfaStates.ContainsKey(currentState))
{
dfaStates[currentState] = "";
}
foreach (string symbol in symbolSet)
{
string[] nfaNextStates = nfaTransitions[currentState][symbol].Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries);
Array.Sort(nfaNextStates);
string nextState = string.Join(",", nfaNextStates);
if (!dfaStates.ContainsKey(nextState))
{
dfaStates.Add(nextState, "");
queue.Enqueue(nextState);
}
dfaStates[currentState] += symbol + ":" + nextState + ";";
}
if (Array.Exists(endSymbol.Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries), x => currentState.Contains(x)))
{
dfaEndStates.Add(currentState);
}
}
int dfaStateCount = dfaStates.Count;
string[] dfaSymbols = symbolSet;
string[] dfaEndStatesArray = dfaEndStates.ToArray();
listView2.Items.Clear();
foreach (string state in dfaStates.Keys)
{
foreach (string symbol in dfaSymbols)
{
string toState = dfaStates[state].Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries)
.Where(x => x.StartsWith(symbol + ":"))
.Select(x => x.Substring(x.IndexOf(":") + 1))
.FirstOrDefault();
ListViewItem item = new ListViewItem(new[] { state, symbol, toState });
listView2.Items.Add(item);
}
}
label5.Text = "初始状态集:" + startSymbol;
label7.Text = "终止状态集:";
for (int i = 0; i < dfaEndStatesArray.Length; i++)
{
label7.Text += dfaEndStatesArray[i] + ";";
}
button7.Enabled = false;
button8.Enabled = true;
}
private void button9_Click(object sender, EventArgs e)//生成MFA文件显示在listView3容器中
{
Dictionary<string, Dictionary<string, string>> dfaTransitions = new Dictionary<string, Dictionary<string, string>>();
foreach (ListViewItem item in listView2.Items)
{
string startState = item.SubItems[0].Text;
string inputSymbol = item.SubItems[1].Text;
string nextState = item.SubItems[2].Text;
if (!dfaTransitions.ContainsKey(startState))
{
dfaTransitions[startState] = new Dictionary<string, string>();
}
dfaTransitions[startState][inputSymbol] = nextState;
}
Dictionary<string, string> mfaStates = new Dictionary<string, string>();
List<string> mfaEndStates = new List<string>();
Queue<string> queue = new Queue<string>();
queue.Enqueue(startSymbol);
while (queue.Count > 0)
{
string currentState = queue.Dequeue();
if (!mfaStates.ContainsKey(currentState))
{
mfaStates[currentState] = "";
}
foreach (string symbol in symbolSet)
{
string nextState = dfaTransitions[currentState][symbol];
if (!mfaStates.ContainsKey(nextState))
{
mfaStates.Add(nextState, "");
queue.Enqueue(nextState);
}
mfaStates[currentState] += symbol + ":" + nextState + ";";
}
if (Array.Exists(endStates, x => currentState.Contains(x)))
{
mfaEndStates.Add(currentState);
}
}
int mfaStateCount = mfaStates.Count;
string[] mfaSymbols = symbolSet;
string[] mfaEndStatesArray = mfaEndStates.ToArray();
listView3.Items.Clear();
foreach (string state in mfaStates.Keys)
{
foreach (string symbol in mfaSymbols)
{
string toState = mfaStates[state].Split(new char[] { ';' }, StringSplitOptions.RemoveEmptyEntries)
.Where(x => x.StartsWith(symbol + ":"))
.Select(x => x.Substring(x.IndexOf(":") + 1))
.FirstOrDefault();
ListViewItem item = new ListViewItem(new[] { state, symbol, toState });
listView3.Items.Add(item);
}
}
label9.Text = "初始状态集:" + startSymbol;
label11.Text = "终止状态集:";
for (int i = 0; i < mfaEndStatesArray.Length; i++)
{
label11.Text += mfaEndStatesArray[i] + ";";
}
button9.Enabled = false;
button10.Enabled = true;
}
}
原文地址: https://www.cveoy.top/t/topic/kq9d 著作权归作者所有。请勿转载和采集!